Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
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.

References [Enhancements On Off] (What's this?)

  • [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 $ {2^n} \pm 1$," 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)

Similar Articles

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

American Mathematical Society