Deterministic Construction of Primes in Subexponential TimeResearch Paper
With randomness, finding an -bit prime is easy: sample integers and test each with the polynomial-time test of Agrawal, Kayal and Saxena. Deterministically, the problem is a standard example of an explicit construction: the property is dense and decidable in polynomial time, yet no fast procedure was known to produce a member of it. It is Open Problem…