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 \geq 3$ .
a: int | None = None¶: An integer in $2 \leq a \leq 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.

Notes

Fermat’s theorem says that for prime $p$ and $1 \leq a \leq p - 1$ , the congruence $a^{p - 1} \equiv 1 (mod p)$ holds. Fermat’s primality test of $n$ computes $a^{n - 1} mod n$ for some $1 \leq a \leq n - 1$ . If $a$ is such that $a^{p - 1} ≢ 1 (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 (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 \leq a \leq n - 2$ .

References

Section 4.2.1 from https://cacr.uwaterloo.ca/hac/about/chap4.pdf

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, True]

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, True]