Editing Primality test (section)

=== Fermat primality test ===
The simplest probabilistic primality test is the [[Fermat primality test]] (actually a compositeness test). It works as follows:

:Given an integer ''n'', choose some integer ''a'' coprime to ''n'' and calculate ''a<sup>n</sup>''<sup> − 1</sup> [[modular arithmetic|modulo]] ''n''. If the result is different from 1, then ''n'' is composite. If it is 1, then ''n'' may be prime.

If ''a<sup>n</sup>''<sup>−1</sup> (modulo ''n'') is 1 but ''n'' is not prime, then ''n'' is called a
[[pseudoprime]] to base ''a''. In practice, if
''a<sup>n</sup>''<sup>−1</sup> (modulo ''n'')
is 1, then ''n'' is usually prime. But here is a counterexample:
if ''n'' = 341 and ''a'' = 2, then
: <math>2^{340} \equiv 1\pmod{341}</math>
even though 341 = 11·31 is composite. In fact, 341 is the smallest pseudoprime base 2 (see Figure 1 of
<ref name="PSW">{{cite journal |last1=Pomerance |first1=Carl |author1-link=Carl Pomerance |last2=Selfridge |first2=John L. |author2-link=John Selfridge |last3=Wagstaff |first3=Samuel S. Jr. |author3-link=Samuel S. Wagstaff Jr. |date=July 1980 |title=The pseudoprimes to 25·10<sup>9</sup> |journal=Mathematics of Computation |volume=35 |issue=151 |pages=1003–1026 |url=https://www.math.dartmouth.edu/~carlp/PDF/paper25.pdf |doi=10.1090/S0025-5718-1980-0572872-7 |doi-access=free}}</ref>).

There are only 21853 pseudoprimes base 2 that are less than 2.5{{e|10}} (see page 1005 of <ref name="PSW"/>). This means that, for ''n'' up to 2.5{{e|10}}, if ''2<sup>n</sup>''<sup>−1</sup> (modulo ''n'') equals 1, then ''n'' is prime, unless ''n'' is one of these 21853 pseudoprimes.

Some composite numbers ([[Carmichael number]]s) have the property that ''a<sup>n</sup>''<sup> − 1</sup> is 1 (modulo ''n'') for every ''a'' that is coprime to ''n''. The smallest example is ''n'' = 561 = 3·11·17, for which ''a<sup>560</sup>'' is 1 (modulo 561) for all ''a'' coprime to 561. Nevertheless, the Fermat test is often used if a rapid screening of numbers is needed, for instance in the key generation phase of the [[RSA (algorithm)|RSA public key cryptographic algorithm]].