11+ digit ints not working

Question

I'm using python 3 for a small extra credit assignment to write an RSA cracker. The teacher has given us a fairly large (large enough to require more than 32 bits) int and the public key. My code works for primes < 32 bits. One of the reasons I chose python 3 is because I heard it can handle arbitrarily large integers. In the python terminal I tested this by doing small things such as 2**35 and factorial(70). This stuff worked fine.

Now that I've written the code, I'm running in to problems with overflow errors etc. Why is it that operations on large numbers seem to work in the terminal but won't work in my actual code? The errors state that they cannot be converted to their C types, so my first guess would be that for some reason the stuff in the python interpreter is not being converter to C types while the coded stuff is. Is there anyway to get this working?

As a first attempt, I tried calculating a list of all primes between 1 and n (the large number). This sort of worked until I realized that the list indexers [ ] only accept ints and explode if the number is higher than int. Also, creating an array that is n in length won't work if n > 2**32. (not to mention the memory this would take up)

Because of this, I switched to using a function I found that could give a very accurate guess as to whether or not a number was prime. These methods are pasted below.

As you can see, I am only doing , *, /, and % operations. All of these seem to work in the interpreter but I get "cannot convert to c-type" errors when used with this code.

def power_mod(a,b,n):
if b < 0:
    return 0
elif b == 0:
    return 1
elif b % 2 == 0:
    return power_mod(a*a, b/2, n) % n
else:
    return (a * power_mod(a,b-1,n)) % n

Those last 3 lines are where the cannot convert to c-type appears.

The below function estimates with a very high degree of certainty that a number is prime. As mentioned above, I used this to avoid creating massive arrays.

def rabin_miller(n, tries = 7):
if n == 2:
    return True

if n % 2 == 0 or n < 2:
    return False

p = primes(tries**2)

if n in p:
    return True

s = n - 1
r = 0
while s % 2 == 0:
    r = r+1
    s = s/2
for i in range(tries):
    a = p[i]

    if power_mod(a,s,n) == 1:
        continue
    else:
        for j in range(0,r):
            if power_mod(a, (2**j)*s, n) == n - 1:
                break
        else:
            return False
        continue
return True

Perhaps I should be more specific by pasting the error: line 19, in power_mod return (a * power_mod(a,b-1,n)) % n OverflowError: Python int too large to convert to C double

This is the type of error I get when performing arithmetic. Int errors occur when trying to create incredibly large lists, sets etc

Answer 1

Your problem (I think) is that you are converting to floating point by using the / operator. Change it to // and you should stay in the int domain.

Answer 2

Many C routines still have C int limitations. Do your work using Python routines instead.