galois.miller_rabin_primality_test

galois.miller_rabin_primality_test(n, a=None, rounds=1)[source]

Probabilistic primality test of \(n\).

This function implements the Miller-Rabin primality test. The test says that for an integer \(n\), select an integer \(a\) such that \(a < n\). Factor \(n - 1\) such that \(2^s d = n - 1\). Then, \(n\) is composite, if \(a^d \not\equiv 1 (\textrm{mod}\ n)\) and \(a^{2^r d} \not\equiv n - 1 (\textrm{mod}\ n)\) for \(1 \le r < s\).

Parameters

  • n (int) – A positive integer.

  • a (int, optional) – Initial composite witness value, \(1 \le a < n\). On subsequent rounds, \(a\) will be a different value. The default is a random value.

  • rounds (int, optinal) – The number of iterations attempting to detect \(n\) as composite. Additional rounds will choose new \(a\). Sufficient rounds have arbitrarily-high probability of detecting a composite.

Returns

False if \(n\) is known to be composite. True if \(n\) is prime or pseudoprime.

Return type

bool

References

Examples

# List of some primes
In [1]: primes = [257, 24841, 65497]

In [2]: for prime in primes:
   ...:     is_prime = galois.miller_rabin_primality_test(prime)
   ...:     p, k = galois.prime_factors(prime)
   ...:     print("Prime = {:5d}, Miller-Rabin Prime Test = {}, Prime factors = {}".format(prime, is_prime, list(p)))
   ...: 
Prime =   257, Miller-Rabin Prime Test = True, Prime factors = [257]
Prime = 24841, Miller-Rabin Prime Test = True, Prime factors = [24841]
Prime = 65497, Miller-Rabin Prime Test = True, Prime factors = [65497]

# List of some strong pseudoprimes with base 2
In [3]: pseudoprimes = [2047, 29341, 65281]

# Single round of Miller-Rabin, sometimes fooled by pseudoprimes
In [4]: for pseudoprime in pseudoprimes:
   ...:     is_prime = galois.miller_rabin_primality_test(pseudoprime)
   ...:     p, k = galois.prime_factors(pseudoprime)
   ...:     print("Psuedoprime = {:5d}, Miller-Rabin Prime Test = {}, Prime factors = {}".format(pseudoprime, is_prime, list(p)))
   ...: 
Psuedoprime =  2047, Miller-Rabin Prime Test = False, Prime factors = [23, 89]
Psuedoprime = 29341, Miller-Rabin Prime Test = False, Prime factors = [13, 37, 61]
Psuedoprime = 65281, Miller-Rabin Prime Test = False, Prime factors = [97, 673]

# 7 rounds of Miller-Rabin, never fooled by pseudoprimes
In [5]: for pseudoprime in pseudoprimes:
   ...:     is_prime = galois.miller_rabin_primality_test(pseudoprime, rounds=7)
   ...:     p, k = galois.prime_factors(pseudoprime)
   ...:     print("Psuedoprime = {:5d}, Miller-Rabin Prime Test = {}, Prime factors = {}".format(pseudoprime, is_prime, list(p)))
   ...: 
Psuedoprime =  2047, Miller-Rabin Prime Test = False, Prime factors = [23, 89]
Psuedoprime = 29341, Miller-Rabin Prime Test = False, Prime factors = [13, 37, 61]
Psuedoprime = 65281, Miller-Rabin Prime Test = False, Prime factors = [97, 673]