| Topics | Register • News • History • How to • Sequences statistics • Template prototypes |
Fermat pseudoprimality test
The Fermat pseudoprimality test is based on the Fermat Little Theorem that states:
- [math]\displaystyle{ a^{p-1}\equiv 1\,\pmod{p} }[/math]
where p is a prime number and a is not multiple of [math]\displaystyle{ p }[/math].
When testing the number N, we perform [math]\displaystyle{ a^{N-1}\equiv 1\,\pmod{N} }[/math]. If the result is not 1, the number must be composite. Otherwise the number is either a prime or a Fermat pseudoprime with respect to base [math]\displaystyle{ a }[/math].
In the last case several tests are performed in order to increase the confidence that the number is not composite. But there are some numbers, known as Carmichael numbers, for which the result is 1 whenever the numbers a and N are coprime. The smallest Carmichael number is 561.
At any rate, it is much better to perform the Miller-Rabin pseudoprimality test which run in the same computational complexity, and which does not have the equivalent of Carmichael numbers.
