Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

The following is an excerpt from the Wikipedia article on the Miller-Rabin primality test:

It can be shown that for any odd composite $n$, at least $\frac{3}{4}$ of the bases $a$ are witnesses for the compositeness of $n$.

In the Fermat primality test, if $n$ is not a Carmichael number, at least half of the bases $a$ are Fermat witnesses. Testing for non-trivial roots in the Miller-Rabin primality test however increases the minimum number of witnesses to $\frac{3}{4}$.

share|improve this question
3  
There are two references for this fact given in the Wikipedia article, both online, and to me it doesn't look like either is behind a paywall. You could look at them. They'll probably be better than any answer you're likely to get here. –  Peter Shor Oct 22 '12 at 21:56
    
The correct comparison is to the Solovay-Strassen test. The Fermat test is no test at all, since as you mention, some composites pass the test. –  Yuval Filmus Oct 23 '12 at 3:38

1 Answer 1

up vote 11 down vote accepted

Here are the three tests you're (implicitly) considering:

  • Fermat: test whether $a^{n-1} \equiv 1 \pmod{n}$
  • Solovay-Strassen: test whether $a^{(n-1)/2} \equiv \left( \dfrac{a}{n} \right) \pmod{n}$ (where $\left( \dfrac{a}{n} \right)$ is a Jacobi symbol, which can be calculated using quadratic reciprocity via a GCD-like algorithm)
  • Miller-Rabin: suppose $n-1 = 2^k m$. Test whether the list $a^m,a^{2m},\ldots,a^{2^km} \pmod{n}$ consists of a (possibly empty) string of $-1$s followed by a string of $1$s

Each test is stronger than the previous one: if $a$ passes Fermat's test, it will satisfy Solovay-Strassen, and if it passes Solovay-Strassen then it passes Miller-Rabin. In the first two tests, the set of $a$ which pass the test form a group. Therefore, unless all $a$s pass the test, at most half of them do. For Solovay-Strassen, one can show that if $n$ is composite, then some $a$ (which can be constructed explicitly) doesn't pass the test.

For Miller-Rabin, the argument is more complicated. The most difficult case turns out to be $n = pq$, where $p,q$ are different primes. The argument uses the Chinese Remainder Theorem to consider what happens modulo $p$ and modulo $q$ separately. For $a$ to pass the test, it must behave in exactly the same way under both primes, and that's the intuitive reason that makes it harder to pass the test. For a proof, check Schoof's paper, for example.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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