Finding primes

This is the main blog page for the "Deterministic way to find primes" project, which is currently fairly active already, and should be formally launched 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!)
5. The function field analogue (i.e. finding degree k irreducible polynomials over a finite field) is known (see Adelman-Lenstra)
6. It's easy to deterministically find large square-free numbers; just multiply lots of small primes together

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. Can one find a degree k irreducible polynomial over the rationals 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.

Observations and strategies

1. If factoring is easy, then it would suffice to show that every polylog(N)-length interval in [N,2N] contains a number which is not [math]\displaystyle{ N^\varepsilon }[/math]-smooth. One way to start approaching this sort of problem is to take iterated product sets of sets of medium sized primes and show that they spread out to fill all short intervals in [N,2N].
   1. One can combine this with the "W-trick". For instance, if one lets W be the product of all the primes less than k, and if one can show that not every element of the progression [math]\displaystyle{ \{ Wn+1: 1 \leq n \leq k^{100} \} }[/math] (say) is [math]\displaystyle{ k^A }[/math]-smooth, then one has found a prime with at least [math]\displaystyle{ A \log k }[/math] digits in polynomial time. Can one make A arbitrarily large?
2. If a primality test can be expressed as a constant-degree polynomial over a finite field from the digits of the number-under-test to {0,1}, then known pseudorandom generators for polynomials can be used to derandomize finding primes the same way as under the full P=BPP assumption. So, instead of requiring a general PRG, the proposal is trying to put the primality test into a fully derandomizable subclass of P.

How could the problem be false?

A world in which the answer to the above question is negative would be very strange. In particular, the following would have to be true:

1. All numbers with at least k digits that are "constructible" in the sense that they are the output of a Turing machine program of length [math]\displaystyle{ O(\log k) }[/math] that runs in time [math]\displaystyle{ k^{O(1)} }[/math], are composite. [If factoring is in P or we have a factoring oracle, then these numbers are furthermore [math]\displaystyle{ \exp(\varepsilon k) }[/math] smooth for any fixed [math]\displaystyle{ \varepsilon \gt 0 }[/math]; if even the weakest version of the problem is false, they are [math]\displaystyle{ k^{O(1)} }[/math]-smooth.]
2. In fact, all constructible numbers are not only composite/smooth, but they sit inside intervals of length [math]\displaystyle{ k^{100} }[/math], all of whose elements are composite/smooth. (One can replace 100 by any other fixed number.)
   1. In particular, Cramer's conjecture fails; the gaps between adjacent k-digit primes exceeds [math]\displaystyle{ k^{100} }[/math] around every constructible number.
3. No pseudorandom number generators exist.
4. [math]\displaystyle{ P \neq NP }[/math].

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
6. Smooth number
7. The W-trick

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
3. Bertrand's postulate ("For every positive integer N, there is a prime between N and 2N" : it gives determinism, but not a polynomial algorithm.)

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. A. Granville, "Harald Cramér and the distribution of prime numbers", Scandinavian Actuarial J. 1 (1995), 12—28.
6. 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.
7. K. Soundararajan, The distribution of the primes (survey)
8. L. Trevisan, Pseudorandomness and Combinatorial Constructions

External links

1. Complexity Zoo