1

I'm studying cryptography. According to Fermat's theorem... $$a^{p-1} \pmod p = 1$$ .. when $p$ is a prime number. The above should prove whether a number is prime or not yet it doesn't work for simple primes like $7$...

Having ran through a routine to show all values up to $50$ it seems to indicate that only $17$ passes the primality test as being probably (or in this case definitely) a prime. Had I picked random values for $a$, every other prime number from $1$ to $50$ would have failed the test.

Result of prime modulus $7$

$$8 = (2^{6}) \mod 7$$ $$8 = (3^{6}) \mod 7$$ $$8 = (4^{6}) \mod 7$$ $$8 = (5^{6}) \mod 7$$ $$1 = (6^6) \mod 7$$

Result of prime modulus $17$ $$1 = (2^{16}) \mod 17$$ $$1 = (3^{16}) \mod 17$$ $$1 = (4^{16}) \mod 17$$ $$1 = (5^{16}) \mod 17$$ $$1 = (6^{16}) \mod 17$$ $$1 = (7^{16}) \mod 17$$ $$1 = (8^{16}) \mod 17$$ $$1 = (9^{16}) \mod 17$$ $$1 = (10^{16}) \mod 17$$ $$1 = (11^{16}) \mod 17$$ $$1 = (12^{16}) \mod 17$$ $$1 = (13^{16}) \mod 17$$ $$1 = (14^{16}) \mod 17$$ $$1 = (15^{16}) \mod 17$$ $$1 = (16^{16}) \mod 17$$

Have I misunderstood the use of the theorem as a primality tester?

Alex M.
  • 35,207
user3168961
  • 219

2 Answers2

2

All prime numbers satisfy the equation. However, certain non-primes, called Carmichael numbers, also do. Therefore, we cannot use it to tell a prime from a composite number.

Amey Joshi
  • 1,084
2

It is necessary but not sufficient to determine primality. That is, you wrote "...when p is a prime number" which says the equation holds for prime p, but says nothing about non-prime p. It turns out to not hold for many composites, which makes it a nice compositeness test. If we run an arbitrary number $n$ through the test with some $a$, either it does not hold, in which case we are certain that $n$ is composite, or it does hold in which case all we know is that $n$ might be prime (but could very well not be).

As Amey pointed out, there is a class of composite $n$ values where the equation holds for all $a$ values: the Carmichael numbers. Adding just a little more work yields the Miller-Rabin test which doesn't have this issue. However it still leaves one with the situation from the paragraph above where the results are "definitely composite" and "maybe prime". Run the M-R test enough times with different $a$ values and we can bump that to "probably prime" (note the handwaving about what "enough" and "probably" mean). There are also deterministic versions for "small" numbers, as well as the BPSW probable prime test, and various proof methods.

DanaJ
  • 2,999