Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

DOI: http://dx.doi.org/10.1090/S0025-5718-1989-0968154-X
PII: S 0025-5718(1989)0968154-X
Article copyright: © Copyright 1989 American Mathematical Society