Cryptography Reference
In-Depth Information
Loop over the number
iterations
of test iterations.
while ((--iterations > 0) && isprime);
return isprime;
}
}
For the cases in which definitive test results are required, the APRCL test,
published in 1981 by its developers L. Adleman, C. Pomerance, R. Rumely, H.
Cohen, and A. K. Lenstra, shows the direction of development of such tests. H.
Riesel praised this test as a breakthrough, proving that fast, generally applicable,
definitive primality tests were possible (see [Ries], page 131). The test determines
the primality property of an integer
n
in time of order
O
(ln
n
)
C
ln ln ln
n
for a suitable constant
C
. Since the exponent
ln ln ln
n
behaves like a constant
for all practical purposes, it can be considered a polynomial-time procedure,
and integers with several hundreds of decimal digits can have their primality or
lack thereof determined definitively in times that are otherwise achieved only
by probabilistic tests.
11
The algorithm, which uses analogues of Fermat's little
theorem for higher algebraic structures, is theoretically complicated and difficult
to implement. For further information see [Cohe], Chapter 9, or the original
article cited therein, as well as the extensive explication in [Ries].
One might also ask whether one would obtain a definitive proof of primality
by testing sufficiently many bases with the Miller-Rabin test. In fact, G. Miller
has proved, on the assumption of the extended Riemann hypothesis (see
page 200) that an odd natural number
n
is prime if and only if for all bases
a
,
1
≤ a ≤ C ·
ln
2
n
, the Miller-Rabin test indicates the primality of
n
(the constant
C
is specified in [Kobl], Section 5.2, as
2
). Used in this way the Miller-Rabin test is
a deterministic polynomial-time primality test that uses about
10
6
iterations, for
primes of about 1024 binary digits, to produce a definitive answer. If we suppose
10
−
3
seconds for each iteration (this is the order of magnitude for the time
required for an exponentiation on a fast PC; cf. Appendix D), then a definitive test
would take about an hour. Considering that there is an unproven hypothesis to be
reckoned with, this theoretical result will satisfy neither the mathematical purists
nor the computational pragmatists interested in fast procedures.
A surprising mathematical breakthrough occurred in 2002, when Maninda
Agrawal, Neeraj Kayal, and Nitin Saxena, of the Indian Institute of Technology,
in Kanpur, published an algorithm that provided a definitive proof of primality
in polynomial time, thereby proving that the problem of recognizing a number
11
Cohen suggests in this connection that the practicably implementable variant of the APRCL al-
gorithm is again probabilistic, but that nonetheless a less practical, but deterministic, version
exists (see [Cohe], Chapter 9).
