Infinite sets of primes with fast primality tests and quick generation of large primes

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.