galois.fermat_primality_test

galois.fermat_primality_test(n: int, a: int | None = None, rounds: int = 1) → bool

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

Parameters
n: int

An odd integer \(n \ge 3\).

a: int | None = None

An integer in \(2 \le a \le n - 2\). The default is None which selects a random \(a\).

rounds: int = 1

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 a probable prime.

See also

is_prime, miller_rabin_primality_test

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]
Last update: Apr 21, 2022