Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Infinite sets of primes with fast primality tests and quick generation of large primes
HTML articles powered by AMS MathViewer

by János Pintz, William L. Steiger and Endre Szemerédi PDF
Math. Comp. 53 (1989), 399-406 Request permission


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.
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC: 11Y11, 11Y16
  • Retrieve articles in all journals with MSC: 11Y11, 11Y16
Additional Information
  • © Copyright 1989 American Mathematical Society
  • Journal: Math. Comp. 53 (1989), 399-406
  • MSC: Primary 11Y11; Secondary 11Y16
  • DOI:
  • MathSciNet review: 968154