galois.fermat_primality_test

galois.fermat_primality_test(n, a=None, rounds=1)

Determines if \(n\) is composite using Fermat’s primality test.

Parameters
  • n (int) – An odd integer \(n \ge 3\).

  • a (int, optional) – An integer in \(2 \le a \le n - 2\). The default is None which selects a random \(a\).

  • rounds (int, optional) – The number of iterations attempting to detect \(n\) as composite. Additional rounds will choose a new \(a\). The default is 1.

Returns

False if \(n\) is shown to be composite. True if \(n\) is probable prime.

Return type

bool

Notes

Fermat’s theorem says that for prime \(p\) and \(1 \le a \le p-1\), the congruence \(a^{p-1} \equiv 1\ (\textrm{mod}\ p)\) holds. Fermat’s primality test of \(n\) computes \(a^{n-1}\ \textrm{mod}\ n\) for some \(1 \le a \le n-1\). If \(a\) is such that \(a^{p-1} \not\equiv 1\ (\textrm{mod}\ p)\), then \(a\) is said to be a Fermat witness to the compositeness of \(n\). If \(n\) is composite and \(a^{p-1} \equiv 1\ (\textrm{mod}\ p)\), then \(a\) is said to be a Fermat liar to the primality of \(n\).

Since \(a = \{1, n-1\}\) are Fermat liars for all composite \(n\), it is common to reduce the range of possible \(a\) to \(2 \le a \le n - 2\).

References

Examples

Fermat’s primality test will never mark a true prime as composite.

In [1]: primes = [257, 24841, 65497]

In [2]: [galois.is_prime(p) for p in primes]
Out[2]: [True, True, True]

In [3]: [galois.fermat_primality_test(p) for p in primes]
Out[3]: [True, True, True]

However, Fermat’s primality test may mark a composite as probable prime. Here are pseudoprimes base 2 from A001567.

# List of some Fermat pseudoprimes to base 2
In [4]: pseudoprimes = [2047, 29341, 65281]

In [5]: [galois.is_prime(p) for p in pseudoprimes]
Out[5]: [False, False, False]

# The pseudoprimes base 2 satisfy 2^(p-1) = 1 (mod p)
In [6]: [galois.fermat_primality_test(p, a=2) for p in pseudoprimes]
Out[6]: [True, True, True]

# But they may not satisfy a^(p-1) = 1 (mod p) for other a
In [7]: [galois.fermat_primality_test(p) for p in pseudoprimes]
Out[7]: [False, True, False]

And the pseudoprimes base 3 from A005935.

# List of some Fermat pseudoprimes to base 3
In [8]: pseudoprimes = [2465, 7381, 16531]

In [9]: [galois.is_prime(p) for p in pseudoprimes]
Out[9]: [False, False, False]

# The pseudoprimes base 3 satisfy 3^(p-1) = 1 (mod p)
In [10]: [galois.fermat_primality_test(p, a=3) for p in pseudoprimes]
Out[10]: [True, True, True]

# But they may not satisfy a^(p-1) = 1 (mod p) for other a
In [11]: [galois.fermat_primality_test(p) for p in pseudoprimes]
Out[11]: [True, False, False]