Finding primes

This is the main blog page for the "Deterministic way to find primes" project, which will be started in within a few weeks.

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.

Please add and develop this wiki; in order to maximise participation in the project when it launches, we will need as much expository material on this project as we can manage.

Relevant concepts

1. Complexity classes
   1. P
   2. NP
   3. BPP
   4. promise-BPP
   5. BQP
   6. DTIME
2. Pseudo-random number generators (PRG)
3. Expander graphs
4. Cramer's random model for the primes
5. Prime gaps

Relevant conjectures

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

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

Relevant papers

1. Impazzaglio-Wigderson (reference?)
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)

External links

1. Complexity Zoo