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

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]**R. A. Mollin,*Recognizing primes*, Int. J. Algebra**1**(2007), no. 9-12, 469–476. MR**2380976**, https://doi.org/10.12988/ija.2007.07050**[2]**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**, https://doi.org/10.2307/2006975**[3]**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**0171766**, https://doi.org/10.4064/aa-9-4-375-390**[4]**John Brillhart, D. H. Lehmer, and J. L. Selfridge,*New primality criteria and factorizations of 2^{𝑚}±1*, Math. Comp.**29**(1975), 620–647. MR**0384673**, https://doi.org/10.1090/S0025-5718-1975-0384673-1**[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. N. Huxley and M. Jutila,*Large values of Dirichlet polynomials. IV*, Acta Arith.**32**(1977), no. 3, 297–312. MR**0485728**, https://doi.org/10.4064/aa-32-3-297-312**[7]**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****[8]**Gary L. Miller,*Riemann’s hypothesis and tests for primality*, J. Comput. System Sci.**13**(1976), no. 3, 300–317. Working papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N.M., 1975). MR**0480295**, https://doi.org/10.1016/S0022-0000(76)80043-8**[9]**Hugh L. Montgomery,*Topics in multiplicative number theory*, Lecture Notes in Mathematics, Vol. 227, Springer-Verlag, Berlin-New York, 1971. MR**0337847****[10]**Carl Pomerance,*Very short primality proofs*, Math. Comp.**48**(1987), no. 177, 315–322. MR**866117**, https://doi.org/10.1090/S0025-5718-1987-0866117-4**[11]**Michael O. Rabin,*Probabilistic algorithm for testing primality*, J. Number Theory**12**(1980), no. 1, 128–138. MR**566880**, https://doi.org/10.1016/0022-314X(80)90084-0**[12]**A. Schönhage and V. Strassen,*Schnelle Multiplikation grosser Zahlen*, Computing (Arch. Elektron. Rechnen)**7**(1971), 281–292 (German, with English summary). MR**0292344****[13]**H. C. Williams,*Primality testing on a computer*, Ars Combin.**5**(1978), 127–185. MR**504864**

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