3

What would be the fastest way to check if a given large number is prime? I'm talking about numbers the size of around 10^32. I've tried the algorithm from the great answer by @MarcoBonelli which is:

from math import sqrt; from itertools import count, islice

def isPrime(n):
    return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))

but it gives the error of Stop argument for islice() must be None or an integer: 0 <= x <= sys.maxsize when used against such large numbers. What would be a different, fast way to do it then?

Community
  • 1
  • 1
Straightfw
  • 2,143
  • 5
  • 26
  • 39

2 Answers2

8

Here is my implementation of the Miller-Rabin primality test; it defaults to 5 random trials, but you can adjust that as desired. The loop on p is a quick return for small primes.

def isPrime(n, k=5): # miller-rabin
    from random import randint
    if n < 2: return False
    for p in [2,3,5,7,11,13,17,19,23,29]:
        if n % p == 0: return n == p
    s, d = 0, n-1
    while d % 2 == 0:
        s, d = s+1, d/2
    for i in range(k):
        x = pow(randint(2, n-1), d, n)
        if x == 1 or x == n-1: continue
        for r in range(1, s):
            x = (x * x) % n
            if x == 1: return False
            if x == n-1: break
        else: return False
    return True
user448810
  • 17,381
  • 4
  • 34
  • 59
5

For a moderately large number I would use Miller-Rabin's Primality test. You can find Python code for it here: https://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test#Python

Note that the algorithm is probabilistic in nature, but applying it a number of time will guarantee correct answers with very high probability.

If you are absolutely set on using a trial division based method, I would recommend you multiply a large number of small primes and store the resulting composite number. Then you can take the Greatest Common Divisor (GCD) using a standard algorithm (such as 'fraction.gcd'). If the answer is not 1, then the number tested is definitely not prime. Usually you would then apply the Miller-Rabin test above to determine whether it is prime.

gdanezis
  • 619
  • 4
  • 7