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.
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.
- There is a deterministic algorithm to find primes if P=NP
- Problem is true if Cramer's conjecture holds (explain!)
- Problem is true if strong pseudorandom number generators exist (explain!)
- k-digit primes can be found with high probability using O(k) random bits (explain!)
Easier versions of the problem
- Subexponential time rather than polynomial
- Equivalently, find primes with superlogarithmically many digits ([math] \gg \log k[/math]) in poly(k) time
- Find k-digit primes using o(k) random bits
- Assume complexity conjectures such as P=BPP, P=BQP, etc.
- Complexity classes
- Pseudo-random number generators (PRG)
- Expander graphs
- Cramer's random model for the primes
- Prime gaps
- existence of PRG
- existence of one-way functions
- whether DTIME(2^n) has subexponential circuits
- the Hardy-Littlewood prime tuples conjecture
- the ABC conjecture
- Cramer’s conjecture
- discrete log in P
- factoring in P.
(These conjectures should have their own links at some point.)
- Impazzaglio-Wigderson (reference?)
- O. Goldreich, A. Wigderson, Derandomization that is rarely wrong from short advice that is typically good
- K. Soundararajan, The distribution of the primes (survey)