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.

Partial results

1. P=NP implies a deterministic algorithm to find primes
2. An efficient algorithm exists if Cramer's conjecture holds
3. Problem is true if strong pseudorandom number generators exist (explain!)
4. k-digit primes can be found with high probability using O(k) random bits (explain!)

Easier versions of the problem

1. Subexponential time rather than polynomial
   1. Equivalently, find primes with superlogarithmically many digits ([math]\displaystyle{ \gg \log k }[/math]) in poly(k) time
2. Find k-digit primes using o(k) random bits
3. Assume complexity conjectures such as P=BPP, P=BQP, etc.
4. Function field version: can one find a degree k irreducible polynomial over a fixed finite field deterministically and quickly?

Variants of the problem

1. Can one derandomise factoring of polynomials over finite fields? Note that if one could do this even in the quadratic case, this would allow for efficient location of quadratic non-residues, which is not known.

Relevant concepts

1. Complexity classes
   1. P
   2. NP
   3. BPP
   4. promise-BPP
   5. BQP
   6. DTIME(f(n))
2. Pseudo-random 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 results

1. Brun-Titchmarsh inequality
2. Erdos-Kac theorem

Relevant papers

1. Adelman, Lenstra, "Finding irreducible polynomials over finite fields"
2. R. C. Baker and G. Harman, “The difference between consecutive primes,” Proc. Lond. Math. Soc., series 3, 72 (1996) 261–280.
3. P. Dusart, Autour de la fonction qui compte le nombre de nombres premiers
4. O. Goldreich, A. Wigderson, Derandomization that is rarely wrong from short advice that is typically good
5. R. Impagliazzo, A. Wigderson, P = BPP unless E has sub-exponential circuits. In Proceedings of the 29th ACM Symposium on Theory of Computing, pages 220–229, 1997.
6. K. Soundararajan, The distribution of the primes (survey)
7. L. Trevisan, Pseudorandomness and Combinatorial Constructions

External links

1. Complexity Zoo