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?)

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