Editing Miller–Rabin primality test (section)

== Mathematical concepts ==
Similarly to the Fermat and Solovay–Strassen tests, the Miller–Rabin primality test checks whether a specific property, which is known to hold for prime values, holds for the number under testing.

=== Strong probable primes ===
The property is the following. For a given odd integer <math>n>2</math>, let’s write <math>n-1</math> as <math>2^sd</math> where <math>s</math> is a positive integer and <math>d</math> is an odd positive integer. Let’s consider an integer <math>a</math>, called a ''base'', which is [[Coprime integers|coprime]] to <math>n</math>.
Then, <math>n</math> is said to be a '''strong [[probable prime]] to base ''a''''' if one of these [[modular arithmetic|congruence relations]] holds:
* <math>a^d \equiv 1 \!\!\!\pmod n</math>, or
* <math>a^{2^r d} \equiv -1 \!\!\!\pmod n</math> for some <math>0
\leq r<s</math>.
This simplifies to first checking for <math>a^d \bmod n = 1</math> and then <math>a^{2^r d} = n-1  </math> for successive values of <math>r</math>. For each value of <math>r</math>, the value of the expression may be calculated using the value obtained for the previous value of <math>r</math> by squaring under the modulus of <math>n</math>.

The idea beneath this test is that when <math>n</math> is an odd prime, it passes the test because of two facts:
* by [[Fermat's little theorem]], <math>a^{n-1} \equiv 1 \pmod{n}</math> (this property alone defines the weaker notion of ''probable prime to base'' <math>a</math>, on which the Fermat test is based);
* the only [[modular square root|square roots]] of 1 modulo <math>n</math> are 1 and −1.

Hence, by [[contraposition]], if <math>n</math> is not a strong probable prime to base <math>a</math>, then <math>n</math> is definitely composite, and <math>a</math> is called a '''[[witness (mathematics)|witness]]''' for the compositeness of <math>n</math>.

However, this property is not an exact characterization of prime numbers. If <math>n</math> is composite, it may nonetheless be a strong probable prime to base <math>a</math>, in which case it is called a '''[[strong pseudoprime]]''', and <math>a</math> is a '''strong liar'''.

=== Choices of bases ===
No composite number is a strong pseudoprime to all bases at the same time (contrary to the Fermat primality test for which Fermat pseudoprimes to all bases exist: the [[Carmichael number]]s). However no simple way of finding a witness is known. A naïve solution is to try all possible bases, which yields an inefficient deterministic algorithm. The Miller test is a more efficient variant of this (see [[#Miller test|section ''Miller test'' below]]).

Another solution is to pick a base at random. This yields a fast [[primality test#Probabilistic tests|probabilistic test]]. When ''n'' is composite, most bases are witnesses, so the test will detect ''n'' as composite with a reasonably high probability (see [[#Accuracy|section ''Accuracy'' below]]). We can quickly reduce the probability of a [[false positive]] to an arbitrarily small rate, by combining the outcome of as many independently chosen bases as necessary to achieve the said rate. This is the Miller–Rabin test. There seems to be diminishing returns in trying many bases, because if ''n'' is a pseudoprime to some base, then it seems more likely to be a pseudoprime to another base.{{r|PSW}}{{rp|§8}}

Note that {{math|''a''<sup>''d''</sup> ≡ 1 (mod ''n'')}} holds trivially for {{math|''a'' ≡ 1 (mod ''n'')}}, because the congruence relation is [[Modular arithmetic#Properties|compatible with exponentiation]]. And {{math|1=''a''<sup>''d''</sup> = ''a''<sup>2<sup>0</sup>''d''</sup> ≡ −1 (mod ''n'')}} holds trivially for {{math|''a'' ≡ −1 (mod ''n'')}} since {{mvar|d}} is odd, for the same reason. That is why random {{mvar|a}} are usually chosen in the interval {{math|1 < ''a'' < ''n'' − 1}}.

For testing arbitrarily large {{mvar|n}}, choosing bases at random is essential, as we don't know the distribution of witnesses and strong liars among the numbers 2, 3, ..., {{math|''n'' − 2}}.{{efn|
For instance, in 1995, Arnault gives a 397-digit composite number for which all bases less than 307 are strong liars; this number was reported to be prime by the [[Maple (software)|Maple]] <code>isprime()</code> function, because it implemented the Miller–Rabin test with the specific bases 2, 3, 5, 7 and 11.<ref name="Arnault397Digit">{{cite journal|title=Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases |journal=Journal of Symbolic Computation|date=August 1995|volume=20|issue=2|pages=151–161 |author=F. Arnault |doi=10.1006/jsco.1995.1042|doi-access=free}}</ref>
}}

However, a pre-selected set of a few small bases guarantees the identification of all composites up to a pre-computed maximum. This maximum is generally quite large compared to the bases. This gives very fast deterministic tests for small enough ''n'' (see [[#Testing against small sets of bases|section ''Testing against small sets of bases'' below]]).

=== Proofs ===
Here is a proof that, if ''n'' is a prime, then the only square roots of 1 modulo ''n'' are 1 and −1.
{{math proof|
Certainly 1 and −1, when squared modulo ''n'', always yield 1. It remains to show that there are no other square roots of 1 modulo ''n''. This is a special case, here applied with the [[polynomial]] {{nowrap|X<sup>2</sup> − 1}} over the [[finite field]] {{nowrap|'''Z'''/''n'''''Z'''}}, of the more general fact that a polynomial over some [[field (mathematics)|field]] has no more [[Root of a polynomial|roots]] than its degree (this theorem follows from the existence of an [[Euclidean division of polynomials|Euclidean division for polynomials]]). Here follows a more elementary proof. Suppose that ''x'' is a square root of 1 modulo ''n''. Then:
: <math> (x - 1)(x + 1) = x^2 - 1 \equiv 0 \pmod{n}.</math>
In other words, ''n'' divides the product {{nowrap|(''x'' − 1)(''x'' + 1)}}. By [[Euclid's lemma]], since ''n'' is prime, it divides one of the factors {{nowrap|''x'' − 1}} or {{nowrap|''x'' + 1,}} implying that ''x'' is congruent to either 1 or −1 modulo ''n''.
}}

Here is a proof that, if ''n'' is an odd prime, then it is a strong probable prime to base ''a''.
{{math proof|
If ''n'' is an odd prime and we write {{nowrap|1=''n'' − 1= 2<sup>''s''</sup>''d''}} where ''s'' is a positive integer and ''d'' is an odd positive integer, by Fermat's little theorem:
: <math>a^{2^s d} \equiv 1 \pmod{n}.</math>
Each term of the sequence <math>a^{2^s d}, a^{2^{s-1} d}, \dots, a^{2d}, a^d</math> is a square root of the previous term. Since the first term is congruent to 1, the second term is a square root of 1 modulo ''n''. By the previous [[lemma (mathematics)|lemma]], it is congruent to either 1 or −1 modulo ''n''. If it is congruent to −1, we are done. Otherwise, it is congruent to 1 and we can [[mathematical induction|iterate the reasoning]]. At the end, either one of the terms is congruent to −1, or all of them are congruent to 1, and in particular the last term, ''a''<sup>''d''</sup>, is.
}}