Appendix F: Recognizing Primes - Codes: The Guide to Secrecy from Ancient to Modern Times - page 552

(4) If j = t − 1, then go to step (5). Otherwise, go to step (3).

(5) Compute

a 2 t − 1 m (mod n ) . x ≡

If x ≡− 1 (mod n ), then terminate the algorithm with

“ n is definitely composite.”

If x ≡− 1 (mod n ), then terminate the algorithm with

“ n is probably prime.”

If n is declared to be “probably prime” with base a by the Miller-Selfridge-
Rabin test, then

n is said to be a strong pseudoprime to base a .

Thus, the above test is often called the strong pseudoprime test F.4 in the liter-
ature. The set of all pseudoprimes to base a is denoted by spsp( a ).
Let us look a little closer at the above test to see why it it is possible to
declare that “ n is definitely composite” in step (3). If x ≡ 1 (mod n ) in step

(3), then for some j with 1 ≤ j<t − 1:

a 2 j m 1 (mod n ), but a 2 j − 1 m

≡ ≡± 1 (mod n ) .

Thus, it can be shown that gcd( a 2 j − 1 m 1 ,n ) is a nontrivial factor of n . Hence,

if the Miller-Selfridge-Rabin test declares in step (3) that “ n is definitely com-
posite”, then indeed it is. Another way of saying this is that if n is prime, then
Miller-Selfridge-Rabin will declare it to be so. However, if n is composite, then
it can be shown that the test fails to recognize n as composite with probability
at most (1 / 4). This is why the most we can say is that “ n is probably prime”.
However, if we perform the test r times for r large enough, this probability
(1 / 4) r can be brought arbitrarily close to zero. Moreover, at least in practice,
using the test with a single choice of a base a is usually suGcient.
Also, in step (5), notice that we have not mentioned the possibility that

−

a 2 t − 1 m

≡ 1 (mod n )

specifically. However, if this did occur, then that means that in step (3), we
would have determined that

a 2 t − 2 m ≡± 1 (mod n ) ,

from which it follows that n cannot be prime. Furthermore, by the above

method, we can factor n since gcd( a 2 t − 2 m − 1 ,n ) is a nontrivial factor. This

F.4 The term “strong pseudoprime” was introduced by Selfridge in the mid-1970s, but he did
not publish this reference. However, it did appear in a paper by Williams [289] in 1978.