[Solved]: In the Miller-Rabin primality test, for a composite number, why are at least $\frac{3}{4}$ of the bases witnesses of compositeness?

Problem Detail: 

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}$.

Asked By : Farhad Yusufali

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6241