There're a lot of examples of code for checking if a number is prime. Why don't people use Fermat's little theorem, i.e. this simple formula

$\qquad a^{p-1} \equiv 1 \pmod p$,

to check if a number is prime?

  • 4
    $\begingroup$ They do. But there exist non prime $p$ which satisfy that equation for some $a$, which needs to be worked around. It's all explained in wikipedia. $\endgroup$ – Karolis Juodelė Jan 19 '14 at 14:35
  • $\begingroup$ @KarolisJuodelė I think you should make this an answer (or close-vote since we don't strive to copy Wikipedia). $\endgroup$ – Raphael Jan 19 '14 at 15:30
  • $\begingroup$ In fact there are certain composite numbers, the co-called Carmichael numbers, which satisfy $a^{c-1}\equiv 1\pmod c$ for every $a$. The smallest example is 561. $\endgroup$ – Mark Dominus Jan 19 '14 at 16:01

Expanding on Karolis's answer, the probabilistic primality tests used in practices, the Miller-Rabin test and the Solovay-Strassen test, are both based on modifications of the test you suggest, also known as the Fermat primality test. (Same for the less common Baillie-PSW test.) The problem with the Fermat test is that it is fooled by some composites known as Carmichael numbers.

The Solovay-Strassen test replaces the test $a^{n-1} \equiv 1 \pmod{n}$ with the similar formula $a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod{n}$. Here $\left(\frac{a}{n}\right)$ is a Jacobi symbol, which for prime $n$ and $a \nmid n$ is equal to $1$ if $a$ is a quadratic residue modulo $n$ (i.e. has a square root modulo $n$) and to $-1$ if $a$ is a quadratic non-residue modulo $n$. There is a GCD-like algorithm for computing the Jacobi symbol, which makes the test feasible. It can be shown that if $n$ is an odd composite, then at least half the $a$s fail this test.

The Miller-Rabin test relies on the (similar) property that $1$ has two square roots modulo a prime, but more modulo composites. The idea is to check that $a^{n-1} \equiv 1 \pmod{n}$ and $a^{(n-1)/2} \equiv \pm 1 \pmod{n}$. If $a^{(n-1)/2} \equiv 1 \pmod{n}$, then we check that $a^{(n-1)/4} \equiv \pm 1 \pmod{n}$. And so on. The test fails if for some $k$, $a^{(n-1)/2^k} \equiv 1 \pmod{n}$ but $a^{(n-1)/2^{k+1}} \not\equiv \pm 1 \pmod{n}$. It can be shown that if $n$ is an odd composite, then at least three quarters of the $a$s fail this test (and so less iterations are needed compared to the Solovay-Strassen test).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.