Recent developments in primality testing

Research exposition (monographs, survey articles) pertaining to number theory (11-02) Power residues, reciprocity (11A15) Factorization; primality (11A51) Primality (11Y11) Analysis of algorithms and problem complexity (68Q25)

Review text

These three papers [Zbl 0476.10005 and Zbl 0476.10006] are largely expository and are listed decreasing in order of readability. They describe resurgent techniques for determining if \(n\) is prime. By virtue of current applications, e.g., in cryptography [see \textit{G. J. Simmons}, Math. Intell. 1, 233--246 (1979; Zbl 0411.94009)], two new aspects of the problem are important. First of all the concept of an ``algorithm now includes range and time of computation. Second, the concept of ``probabilistically prime is practical. The first aspect is illustrated by an algorithm for testing all numbers \(n\) up to \(25\cdot 10^9\) in a few seconds on any machine of suitable capacity to handle the size [see \textit{C. Pomerance}, \textit{J. L. Selfridge}, and \textit{S. S.Wagstaff jun.}, Math. Comput. 35, 1003--1026 (1980; Zbl 0444.10007)]. The main definition is that \(n\) is a strong pseudoprime to the base \(a\) when \(a^{n-1}\equiv 1 \bmod n\), and if \(m\) is the odd part of \(n - 1\) then either \(a^m\equiv 1\) or else the first element of the sequence \(a^m, a^{2m}, a^{4m}, a^{8m},\ldots\) which is \(\equiv 1\) is preceded by a term \(z -1\). In that range of \(n\) only \(n= 3215031751=151.751.28351\) is a composite passing the test of strong pseudoprimality for all the bases \(2,3,5,7\). The ``true algorithm (for variable \(n\)) would be found in polynomial time (bounded by \((\log n)^6)\) under the generalized Riemann hypothesis. There are viable algorithms for larger numbers up to about \(10^{100}\) by improvements of classical methods going back in principle to the above criterion. They are due to L. M. Adleman, C. Pomerance, R. S. Rumely, with improvements due to H. W. Lenstra and H. Cohen (but most of this is detailed elsewhere). The methods are in algebraic number theory using reciprocity properties of Gauss and Jacobi sums. The classical background work is detailed in [\textit{H. C. Williams}, Ars Comb. 5, 127--185 (1978; Zbl 0406.10008)]. The probabilistic criteria are largely due to \textit{M. O. Rabin} [J. Number Theory 12, 128--138 (1980; Zbl 0426.10006)], and are based on the observation that with a random choice of \(b\) bases a strong pseudoprime would be mistaken for a prime falsely with probability \(4^{-b}\). Thus any degree of probability of primeness can be established in polynomial time.

Recommendations

Cites work

Cited in

(44)

This page was built for publication: Recent developments in primality testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1160213)