Pseudoprime
A number with cannot be prime, since prime values satisfy ; such a is called a pseudoprime.
Proposition 4.38 (Fermat's Criterion [Non-Examinable])
When , Fermat’s little theorem (Theorem 4.31) can be read as
Another way is to state that if , then there is a good chance that is prime. If not, then is called a pseudoprime.
Related
Stated in
- Proposition 4.38 (Fermat's Criterion [Non-Examinable])§4.8 Public Key Cryptography