Editing Fermat's little theorem (section)

== Miller–Rabin primality test ==
The [[Miller–Rabin primality test]] uses the following extension of Fermat's little theorem:<ref>{{Cite book|contribution=4.5.1. Lemma (Roots of unity modulo a prime)|contribution-url=https://books.google.com/books?id=nQVZAgAAQBAJ&q=The+Miller%E2%80%93Rabin+primality+test+uses+the+following+extension+of+Fermat's+little+theorem&pg=PA144|title=Primality Testing for Beginners|title-link=Primality Testing for Beginners|last1=Rempe-Gillen|first1=Lasse|last2=Waldecker|first2=Rebecca|author2-link= Rebecca Waldecker |date=2013-12-11|publisher=American Mathematical Soc.|isbn=9780821898833|language=en}}</ref> 
<blockquote>If {{mvar|p}} is an [[parity (mathematics)|odd]] prime and {{math|1=''p'' − 1 = 2<sup>''s''</sup>''d''}} with {{math|s > 0}} and {{mvar|d}} odd > 0, then for every {{mvar|a}} coprime to {{mvar|p}}, either {{math|''a''<sup>''d''</sup> ≡ 1 (mod ''p'')}} or there exists {{mvar|r}} such that {{math|0 ≤ ''r'' < ''s''}} and {{math|''a''<sup>2<sup>''r''</sup>''d''</sup> ≡ −1 (mod ''p'')}}.</blockquote>

This result may be deduced from Fermat's little theorem by the fact that, if {{mvar|p}} is an odd prime, then the integers modulo {{mvar|p}} form a [[finite field]], in which 1 modulo {{mvar|p}} has exactly two square roots, 1 and −1 modulo {{mvar|p}}.

Note that {{math|''a''<sup>''d''</sup> ≡ 1 (mod ''p'')}} holds trivially for {{math|''a'' ≡ 1 (mod ''p'')}}, 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 ''p'')}} holds trivially for {{math|''a'' ≡ −1 (mod ''p'')}} since {{mvar|d}} is odd, for the same reason. That is why one usually chooses a random {{mvar|a}} in the interval {{math|1 < ''a'' < ''p'' − 1}}.

The Miller–Rabin test uses this property in the following way: given an odd integer {{mvar|p}} for which primality has to be tested, write {{math|1=''p'' − 1 = 2<sup>''s''</sup>''d''}} with {{math|s > 0}} and {{mvar|d}} odd > 0, and choose a random {{mvar|a}} such that {{math|1 < ''a'' < ''p'' − 1}}; then compute {{math|1=''b'' = ''a''<sup>''d''</sup> mod ''p''}}; if {{mvar|b}} is not 1 nor −1, then square it repeatedly modulo {{mvar|p}} until you get −1 or have squared {{math|''s'' − 1}} times. If {{math|''b'' ≠ 1}} and −1 has not been obtained by squaring, then {{mvar|p}} is a [[Composite number|''composite'']] and {{mvar|a}} is a [[Witness (mathematics)|witness]] for the compositeness of {{mvar|p}}. Otherwise, {{mvar|p}} is a ''strong [[probable prime]] to base a''; that is, it may be prime or not. If {{mvar|p}} is composite, the probability that the test declares it a strong probable prime anyway is at most {{frac|1|4}}, in which case {{mvar|p}} is a ''[[strong pseudoprime]]'', and {{mvar|a}} is a ''strong liar''. Therefore after {{mvar|k}} non-conclusive random tests, the probability that {{mvar|p}} is composite is at most 4<sup>−''k''</sup>, and may thus be made as low as desired by increasing {{mvar|k}}.

In summary, the test either proves that a number is composite or asserts that it is prime with a probability of error that may be chosen as low as desired. The test is very simple to implement and computationally more efficient than all known deterministic tests. Therefore, it is generally used before starting a proof of primality.