1
$\begingroup$

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?

$\endgroup$
3
  • 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$ Commented Jan 19, 2014 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
    Commented Jan 19, 2014 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$ Commented Jan 19, 2014 at 16:01

1 Answer 1

4
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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