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

final step (4) is required since, if we get to j = t − 1, with x ≡± 1 (mod n ) for

any j<t − 1, then simply invoking step (3) again would dismiss those values

of x 1 (mod n ), and this would not allow us to claim that n is composite in

those cases. Hence, it allows for more values of n to be deemed composite, with
certainty, than if we merely performed step (3) as with previous values of j .
The Miller-Selfridge-Rabin test is an example of a Monte Carlo algorithm
meaning a probabilistic algorithm F.5 that achieves a correct answer more than
50% of the time. More specifically, Miller-Selfridge-Rabin is a Monte Carlo
algorithm for compositeness, since it provides a proof that a given input is com-
posite, but only provides some probabilistic evidence of primality. Furthermore,
Miller-Selfridge-Rabin is a yes-biased Monte Carlo algorithm meaning that a
“yes” answer is always correct but a “no” answer may be incorrect. In this
case, the answer is to the decision problem: F.6 “Is n composite?” A yes-biased
Monte Carlo algorithm is said to have error probability α

≡±

+ with 0

α< 1,
provided that for any occurrence in which the answer is “yes”, the algorithm
will give the incorrect answer “no” with probability at most α , where the prob-
ability is computed over all possible random choices made by the algorithm for
a given input. Therefore, the Miller-Selfridge-Rabin algorithm is a yes-biased
Monte Carlo algorithm for the decision problem “Is n composite?” with error
probability α =(1 / 4) r .
There are many related algorithm that we have not discussed here, such
as the Solovay-Strassen test, because the Miller-Selfridge-Rabin test is compu-
tationally less expensive, easier to implement, and is at least as correct. For
information on such tests, the reader may consult [170, pp. 84-86], for instance.
There are several tests that are beyond the scope of this topic. Nevertheless,
they are worth mentioning as a segue to the next section. Among them is
one using Artin symbols, described by Lenstra in [147], which is also given a
presentation in [168, Section 4.5, pp. 264-270]. There have also been proofs of
the existence of a deterministic polynomial time algorithm for primality testing
under the assumption of the Extended Riemann Hypothesis (ERH). The ERH
has has not yet been verified, but is widely believed to be true (see [162]). There
is also the Goldwasser-Kilian test presented in [108], which is based on elliptic
curves. The Goldwasser-Killian test was motivated by a desire to prove that,
at least theoretically, it is possible to find a polynomial time primality testing
algorithm. Using Schoof's algorithm [243], this can be done, but the procedure
is impractical to implement and run. The idea was modified by Adleman and
Huang in [5], who presented a randomized algorithm that runs in expected
polynomial time on all inputs, as opposed to the restrictions in the Goldwasser-
Killian algorithm. There were other advances, but the goal of actually finding
an unconditional deterministic polynomial time algorithm for primality testing
has only recently been solved, and we present it in the next section.

∈ R ≤

(For a

history of primality testing, see [290].)

F.5 Seethediscussionofrandomizedalgorithmsonpage500inAppendixA,sinceprobabilistic
algorithms use random numbers.
F.6 See page 502.