Infinite sets of primes with fast primality tests and quick generation of large primes

Authors:
János Pintz, William L. Steiger and Endre Szemerédi

Journal:
Math. Comp. **53** (1989), 399-406

MSC:
Primary 11Y11; Secondary 11Y16

DOI:
https://doi.org/10.1090/S0025-5718-1989-0968154-X

MathSciNet review:
968154

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Infinite sets *P* and *Q* of primes are described, $P \subset Q$. For any natural number *n* it can be decided if $n \in P$ in (deterministic) time $O({(\log n)^9})$. This answers affirmatively the question of whether there exists an infinite set of primes whose membership can be tested in polynomial time, and is a main result of the paper. Also, for every $n \in Q$, we show how to randomly produce a proof of the primality of *n*. The expected time is that needed for $1\frac {1}{2}$ exponentiations $\bmod n$. We also show how to randomly generate *k*-digit integers which will be in *Q* with probability proportional to ${k^{ - 1}}$. Combined with the fast verification of $n \in Q$ just mentioned, this gives an $O({k^4})$ expected time algorithm to generate and certify primes in a given range and is probably the fastest method to generate large certified primes known to belong to an infinite subset. Finally, it is important that *P* and *Q* are relatively dense (at least $c{n^{2/3}}/\log n$ elements less than *n*). Elements of *Q* in a given range may be generated quickly, but it would be costly for an adversary to search *Q* in this range, a property that could be useful in cryptography.

- R. A. Mollin,
*Recognizing primes*, Int. J. Algebra**1**(2007), no. 9-12, 469–476. MR**2380976**, DOI https://doi.org/10.12988/ija.2007.07050 - Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely,
*On distinguishing prime numbers from composite numbers*, Ann. of Math. (2)**117**(1983), no. 1, 173–206. MR**683806**, DOI https://doi.org/10.2307/2006975 - M. B. Barban, Yu. V. Linnik, and N. G. Tshudakov,
*On prime numbers in an arithmetic progression with a prime-power difference*, Acta Arith.**9**(1964), 375–390. MR**171766**, DOI https://doi.org/10.4064/aa-9-4-375-390 - John Brillhart, D. H. Lehmer, and J. L. Selfridge,
*New primality criteria and factorizations of $2^{m}\pm 1$*, Math. Comp.**29**(1975), 620–647. MR**384673**, DOI https://doi.org/10.1090/S0025-5718-1975-0384673-1
S. Goldwasser & J. Kilian, - M. N. Huxley and M. Jutila,
*Large values of Dirichlet polynomials. IV*, Acta Arith.**32**(1977), no. 3, 297–312. MR**485728**, DOI https://doi.org/10.4064/aa-32-3-297-312 - H. W. Lenstra Jr.,
*Primality testing*, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 55–77. MR**700258** - Gary L. Miller,
*Riemann’s hypothesis and tests for primality*, J. Comput. System Sci.**13**(1976), no. 3, 300–317. MR**480295**, DOI https://doi.org/10.1016/S0022-0000%2876%2980043-8 - Hugh L. Montgomery,
*Topics in multiplicative number theory*, Lecture Notes in Mathematics, Vol. 227, Springer-Verlag, Berlin-New York, 1971. MR**0337847** - Carl Pomerance,
*Very short primality proofs*, Math. Comp.**48**(1987), no. 177, 315–322. MR**866117**, DOI https://doi.org/10.1090/S0025-5718-1987-0866117-4 - Michael O. Rabin,
*Probabilistic algorithm for testing primality*, J. Number Theory**12**(1980), no. 1, 128–138. MR**566880**, DOI https://doi.org/10.1016/0022-314X%2880%2990084-0 - A. Schönhage and V. Strassen,
*Schnelle Multiplikation grosser Zahlen*, Computing (Arch. Elektron. Rechnen)**7**(1971), 281–292 (German, with English summary). MR**292344**, DOI https://doi.org/10.1007/bf02242355 - H. C. Williams,
*Primality testing on a computer*, Ars Combin.**5**(1978), 127–185. MR**504864**

*Almost All Primes Can Be Quickly Certified*, Proc. 18th Ann. ACM Sympos. on Theory of Computing, 1986, pp. 316-329.

Retrieve articles in *Mathematics of Computation*
with MSC:
11Y11,
11Y16

Retrieve articles in all journals with MSC: 11Y11, 11Y16

Additional Information

Article copyright:
© Copyright 1989
American Mathematical Society