Issue with longs dividing and then modding correctly in Python

Question

I'm trying to implement a primality test for an RSA implementation I'm writing as an excercise. I'm mainly using Rabin-Miller, but I do have a Sieve of Eratosthenes formulating a list of all the primes under a thousand to use for a quick test to determine if a candidate has one of them as a prime factor.

The relevant function is:

def comp_test(to_test, primeList):
    for i in primeList:
        if (to_test / float(i)) % 1 == 0:
            return False
    return True

Where primeList is the list of primes generated by the Sieve. This works perfectly up to to_test values of 2^55 or so, but beyond that point the

(to_test / float(i)) % 1

statement always evaluates to 0.0, even when I hand it a to_test that the Rabin-Miller determined to be prime. I'm not sure what this could be. I'm not that clear on how Python handles very large numbers, but to my knowledge 2^55 doesn't seem like it would be any sort of overflow border. With the Sieve the function is substantially faster, and generating keys for the 2048-bit implementation I'm going for takes a while, so even though this is an exercise I'd like to see if I can get the Sieve working.

Thanks in advance.

Answer 1

Python handles only 53 bits of precision for floating point numbers (about 16 decimal places), so using floats that large won't work very well.

Use the modulo operator instead:

>>> (2**80 / float(3)) % 1  # Doesn't work
    0.0
>>> 2**80 % 3  # Works
    1L
>>> 2**80 % 2  # Works
    0L

It's also quite a bit faster than division:

>>> %timeit (2**40 / float(2)) == 0
1000000 loops, best of 3: 224 ns per loop
>>> %timeit 2**40 % 2 == 0        
10000000 loops, best of 3: 53.5 ns per loop

If i is a factor of n, then n % i == 0 (n is congruent to 0 modulo i).

Answer 2

I'd recommend using GMP for your large-number needs.

Here are some of the prime-related projects I've done in Python in the past:

http://stromberg.dnsalias.org/svn/primes-below
http://stromberg.dnsalias.org/svn/big-prime
http://stromberg.dnsalias.org/svn/huge-prime
http://stromberg.dnsalias.org/svn/sieve