Editing Miller–Rabin primality test (section)

=== 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'''.