galois.fermat_primality_test¶

galois.fermat_primality_test(n)[source]¶

Probabilistic primality test of \(n\).

This function implements Fermat’s primality test. The test says that for an integer \(n\), select an integer \(a\) coprime with \(n\). If \(a^{n-1} \equiv 1 (\textrm{mod}\ n)\), then \(n\) is prime or pseudoprime.

Parameters: n (int) – A positive integer.
Returns: False if \(n\) is known to be composite. True if \(n\) is prime or pseudoprime.
Return type: bool

Examples

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

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

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

In [4]: for pseudoprime in pseudoprimes:
   ...:     is_prime = galois.fermat_primality_test(pseudoprime)
   ...:     p, k = galois.prime_factors(pseudoprime)
   ...:     print("Psuedoprime = {:5d}, Fermat's Prime Test = {}, Prime factors = {}".format(pseudoprime, is_prime, list(p)))
   ...: 
Psuedoprime =  2047, Fermat's Prime Test = True, Prime factors = [23, 89]
Psuedoprime = 29341, Fermat's Prime Test = True, Prime factors = [13, 37, 61]
Psuedoprime = 65281, Fermat's Prime Test = True, Prime factors = [97, 673]