Editing Primality test (section)

=== Miller–Rabin and Solovay–Strassen primality test===
The [[Miller–Rabin primality test]] and [[Solovay–Strassen primality test]] are more sophisticated variants, which detect all composites (once again, this means: for ''every'' composite number ''n'', at least 3/4 (Miller–Rabin) or 1/2 (Solovay–Strassen) of numbers ''a'' are witnesses of compositeness of ''n''). These are also compositeness tests.

The Miller–Rabin primality test works as follows:
Given an integer ''n'', choose some positive integer ''a''&nbsp;<&nbsp;''n''. Let 2<sup>''s''</sup>''d'' = ''n''&nbsp;−&nbsp;1, where ''d'' is odd. If

:<math>
a^{d} \not\equiv \pm 1\pmod{n}
</math>
and
:<math>
a^{2^rd} \not\equiv -1\pmod{n}</math> for all <math>0 \le r \le s - 1,
</math>

then ''n'' is composite and ''a'' is a witness for the compositeness. Otherwise, ''n'' may or may not be prime.
The Miller–Rabin test is a [[strong pseudoprime|strong probable prime]] test (see PSW<ref name="PSW"/> page 1004).

The Solovay–Strassen primality test uses another equality: Given an odd number ''n'', choose some integer ''a''&nbsp;<&nbsp;''n'', if

:<math> a^{(n-1)/2} \not\equiv \left(\frac{a}{n}\right) \pmod n</math>, where <math>\left(\frac{a}{n}\right)</math> is the [[Jacobi symbol]],

then ''n'' is composite and ''a'' is a witness for the compositeness. Otherwise, ''n'' may or may not be prime.
The Solovay–Strassen test is an [[Euler pseudoprime|Euler probable prime]] test (see PSW<ref name="PSW"/> page 1003).

For each individual value of ''a'', the Solovay–Strassen test is weaker than the Miller–Rabin test. For example, if ''n'' = 1905 and ''a'' = 2, then the Miller-Rabin test shows that ''n'' is composite, but the Solovay–Strassen test does not. This is because 1905 is an Euler
pseudoprime base 2 but not a strong pseudoprime base 2 (this is illustrated in Figure 1 of PSW<ref name="PSW"/>).