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, . For any natural number *n* it can be decided if in (deterministic) time . 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 , we show how to randomly produce a proof of the primality of *n*. The expected time is that needed for exponentiations . We also show how to randomly generate *k*-digit integers which will be in *Q* with probability proportional to . Combined with the fast verification of just mentioned, this gives an 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 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.

**[1]**L. M. Adleman & M. A. Huang,*Recognizing Primes in Random Polynomial Time*, Proc. 19th Ann. ACM Sympos. on Theory of Computing, 1987, pp. 462-469. MR**2380976 (2008m:11242)****[2]**L. M. Adleman, C. Pomerance & R. S. Rumely, "On distinguishing prime numbers from composite numbers,"*Ann. of Math.*, v. 117, 1983, pp. 173-206. MR**683806 (84e:10008)****[3]**M. B. Barban, Ju. V. Linnik & N. G. Tshudakov, "On prime numbers in an arithmetic progression with a prime-power difference,"*Acta Arith.*, v. 9, 1964, pp. 375-390. MR**0171766 (30:1993)****[4]**J. Brillhart, D. H. Lehmer & J. L. Selfridge, "New primality criteria and factorization of ,"*Math. Comp.*, v. 29, 1975, pp. 620-647. MR**0384673 (52:5546)****[5]**S. Goldwasser & J. Kilian,*Almost All Primes Can Be Quickly Certified*, Proc. 18th Ann. ACM Sympos. on Theory of Computing, 1986, pp. 316-329.**[6]**M. Huxley & M. Jutila, "Large values of Dirichlet polynomials IV",*Acta Arith.*, v. 32, 1977, pp. 297-312. MR**0485728 (58:5550)****[7]**H. W. Lenstra, Jr., "Primality testing,"*Computational Methods in Number Theory*, Math. Centrum Tracts, no. 154, Math. Centrum, Amsterdam, 1982, pp. 55-77. MR**700258 (85g:11117)****[8]**G. L. Miller, "Riemann's hypothesis and tests for primality,"*J. Comput. System Sci.*, v. 13, 1976, pp. 300-317. MR**0480295 (58:470a)****[9]**H. L. Montgomery,*Topics in Multiplicative Number Theory*, Lecture Notes in Math., Vol. 227, Springer-Verlag, Berlin, 1971. MR**0337847 (49:2616)****[10]**C. Pomerance, "Very short primality proofs,"*Math. Comp.*, v. 48, 1987, pp. 315-322. MR**866117 (88b:11088)****[11]**M. Rabin, "Probabilistic algorithms for testing primality,"*J. Number Theory*, v. 12, 1980, pp. 128-138. MR**566880 (81f:10003)****[12]**A. Schönhage & V. Strassen, "Schnelle Multiplikation grosser Zahlen,"*Computing*, v. 7, 1971, pp. 281-292. MR**0292344 (45:1431)****[13]**H. C. Williams, "Primality testing on a computer,"*Ars Combin.*v. 5, 1978, pp. 127-185. MR**504864 (80d:10002)**

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

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

Additional Information

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

Article copyright:
© Copyright 1989
American Mathematical Society