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