galois.fermat_primality_test(n: int, a: = 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: = 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.

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]: [False, False, False]