Finding primes

This is the main blog page for the "Deterministic way to find primes" project.

The main aim of the project is as follows:

Problem. Find a deterministic algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in k. You may assume as many standard conjectures in number theory (e.g. the generalised Riemann hypothesis) as necessary, but avoid powerful conjectures in complexity theory (e.g. P=BPP) if possible.

Here is the proposal for the project, which is also the de facto research thread for that project. Here is the discussion thread for the project.

Relevant conjectures

1. P=NP
2. P=BPP
3. P=promise-BPP
4. existence of PRG
5. existence of one-way functions
6. whether DTIME(2^n) has subexponential circuits
7. GRH
8. the Hardy-Littlewood prime tuples conjecture
9. the ABC conjecture
10. Cramer’s conjecture
11. discrete log in P
12. factoring in P.

(These conjectures should have their own links at some point.)

Relevant papers

1. Impazzaglio-Wigderson
2. O. Goldreich, A. Wigderson, Derandomization that is rarely wrong from short advice that is typically good
3. K. Soundararajan, The distribution of the primes (survey)