Editing Miller–Rabin primality test (section)

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