1

I want to multiply an integer with all the numbers in a list I generate until a value of 65 is reached. I am starting off at 2(first prime) and multiply up to 63(again all primes) until I reach 65. If a value is not reached with 2 I then want it to try with 3, and so on until the correct value us reached. I am doing this in python, which I am new too aswell so I apologise if this is basic. I then want to print out the numbers which multiplied together to give me that value, i.e. I know 5 and 13 would give me 65. Here is some of my code below:

from __future__ import division
import fractions
ml = []
nl = []
p = 5
q = 17
d = 0
x = 2
y = 2

z = (p-1)*(q-1)
print z
n = p*q
print n

for x in range(z):
    if (fractions.gcd(x, z) == 1):
        ml.append(x)
    ##print ml

s = 1
for x in ml:
    t = s * x 
    if t == 65:
        print s
        print x
        break
    else:
        s = s + 1
thefourtheye
  • 233,700
  • 52
  • 457
  • 497
Andrew Stewart
  • 279
  • 7
  • 16
  • 2
    I think I can tell what your problem is, but you'll get better answers if you explain what you're unsure about. As it is I have to guess what you might need to know. – Peter DeGlopper Dec 13 '13 at 01:21
  • I need to know how to get it to calculate for each integer in the list, but I only want it to output when the value of the calculation is 65. That is what I have tried to do with the last section of code but it does not seem to work, or "do anything". Thankyou for replying to the question. – Andrew Stewart Dec 13 '13 at 01:27
  • As general advice, listing both your expected output and your actual output is a good guideline for asking a clear question. It doesn't make sense for every question, but in this case the question would be improved by saying something like "I expect this to print 6 and 15. However, my `for` loop exits with no output." Not that the exact wording is important, but describing the reason you think there is a problem is. – Peter DeGlopper Dec 13 '13 at 01:41

1 Answers1

2

You're incrementing s and moving to the next element in ml in each stage of the loop. So you only try 1 * ml[0], 2 * ml[1], etc. I think you want two nested for loops, so that you try every element of ml with every possible value of s. You can get this behaviour a bit more cleanly with itertools:

for s,x in itertools.product(range(65),ml):
    t = s * x 
    if t == 65:
        print s
        print x
        break
happydave
  • 7,127
  • 1
  • 26
  • 25
  • Thanks, error code saying 'itertools' is not defined, what is the import code? – Andrew Stewart Dec 13 '13 at 01:44
  • 1
    You're right about the cause of the problem. I might have a different implementation of the correct algorithm, but I don't see anything wrong here except that having 65 present as the cap of the range - while not wrong - seems more dependent on the input setup than I would like. To use `itertools`, add `import itertools` to your program. – Peter DeGlopper Dec 13 '13 at 01:44
  • I agree that this is a relatively inefficient algorithm. Given that you know what you're looking for, it seems like the simple linear alternative would be to just compute s=65/x in each iteration of the loop. – happydave Dec 13 '13 at 01:48
  • I think this is one of those questions that is either a pure learning exercise or is simplified sufficiently from the actual situation that it's hard to figure out what the best solution is. – Peter DeGlopper Dec 13 '13 at 01:50
  • Just to clarify, in this case I know what I am looking for, this script is working with RSA, calculating public and private keys where the numbers can be considerably larger, so I have changed 65, to be z+1, I agree this script when dealing with large numbers will be very slow in calculating those values. – Andrew Stewart Dec 13 '13 at 02:02
  • I'd need to remind myself of the algorithms used, but I hope you're not looking for something that can factor sufficiently large numbers into their prime factors. The difficulty of that task is the basis of such cryptography. If you know either key, you can just use simple division to find the other. If you know neither key, Python will not help you find either key for real RSA values. – Peter DeGlopper Dec 13 '13 at 02:06
  • Maybe see this answer if the keys are short enough: http://stackoverflow.com/questions/4078902/cracking-short-rsa-keys – Peter DeGlopper Dec 13 '13 at 02:12