Primes and cryptography · Definition

Fermat primality test

elementary number theoryprimes and cryptography

Before you start you need to know

This test uses Fermat's little theorem to detect composites quickly. Its main weakness is that some composites pass the check for certain bases.

Definition

The Fermat primality test is a probabilistic criterion for an integer \(n>1\): it declares \(n\) composite if, for some base \(a\) coprime to \(n\), the power \(a^{n-1}\) is not congruent to 1 modulo \(n\).

\[a^{n-1} \equiv 1 \pmod{n}\]

If n is prime and gcd(a, n) = 1, then \( a^{n-1} \equiv 1 \pmod{n} \). Hence, if for some base a with gcd(a, n) = 1 we have \( a^{n-1} \not\equiv 1 \pmod{n} \), then n is composite. The converse does not hold in general: satisfying the congruence for one base does not guarantee primality. Powers modulo n are computed by fast exponentiation, so each test costs \( O(\log n) \) modular multiplications.

Worked example: for n = 15 and a = 2, we have \( 2^{14} = 16384 \), and \( 16384 \bmod 15 = 4 \neq 1 \). Since the congruence fails, 15 is composite. Without computing the full power, reduce: \( 2^4 \equiv 1 \pmod{15} \), so \( 2^{14} = 2^{12} \cdot 2^2 \equiv 4 \pmod{15} \).

Typical error: concluding that n is prime because \( a^{n-1} \equiv 1 \pmod{n} \) for a single base. The number 341 = 11·31 satisfies \( 2^{340} \equiv 1 \pmod{341} \) yet is composite; therefore several bases must be tested.

Think about it

Why is one base not enough to conclude that n is prime?

Because some composites, such as 341, satisfy the congruence for one base; several bases must be tested.

Exercises 10

  1. What does \( a^{n-1} \not\equiv 1 \pmod{n} \) with gcd(a, n) = 1 tell you?
  2. What is \( 2^{4} \bmod 15 \)?
  3. What is the name of the test that uses \( a^{n-1} \equiv 1 \pmod{n} \) to detect composites?
  4. What condition must the base a satisfy in the Fermat test?
  5. If n is prime and gcd(a, n) = 1, what holds?
  6. Compute \( 3^{6} \bmod 7 \) and state whether the test with base 3 concludes that 7 is prime or composite.
  7. Use the test with base 2 for n = 9. What do you conclude?
  8. For n = 13 and a = 5, what is the remainder of \( 5^{12} \bmod 13 \)?
  9. For n = 21 and a = 2, what result does the Fermat test give?
  10. Show with the base-2 test whether 341 is composite, or explain why it cannot detect it and which base reveals it.

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 5 y 16
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2