Finding primes

From Polymath Wiki
Revision as of 07:16, 4 August 2009 by Teorth (talk | contribs)
Jump to navigationJump to search

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 to resolve the following conjecture:

(Strong) conjecture. There exists 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.

Since primality is known to be in P by the AKS algorithm, we may assume a primality oracle that decides whether any given number is prime in unit time. Weaker versions of the strong conjecture are proposed below.

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.

Easier versions of the problem

Semi-weak conjecture: There exists a probabilistic algorithm which, when given an integer k, has probability at least 1/2 (say) of finding a prime of at least k digits in length in time polynomial in k, using o(k) random bits. (Note that it is known that one can do this with O(k) random bits; and if one can use just [math]\displaystyle{ O(\log k) }[/math] random bits, one is done by exhausting over the random bits.)

One way to solve the semi-weak conjecture would be to find an "explorable" set of size [math]\displaystyle{ \exp(o(k)) }[/math] of integers, a significant fraction (at least [math]\displaystyle{ k^{-O(1)} }[/math]) of which are primes at least k digits in length. By explorable, we mean that one has a quick way to produce a reasonably uniformly distributed element of that set using o(k) random bits (e.g. the set might be an interval, arithmetic progression, or other explicitly parameterisable set, or one might have an explicit expander graph on this set).

Weak conjecture: There exists a deterministic algorithm, which, when given an integer k, is guaranteed to find a prime of at least [math]\displaystyle{ \omega(\log k) }[/math] digits in length in time polynomial in k, where [math]\displaystyle{ \omega(\log k) }[/math] grows faster than [math]\displaystyle{ \log k }[/math] as [math]\displaystyle{ k \to \infty }[/math]. (Equivalently, find a deterministic algorithm which, when given k, is guaranteed to find a prime of at least k digits in time [math]\displaystyle{ \exp(o(k)) }[/math]. Note that the semi-weak conjecture implies the weak conjecture).
Strong conjecture with factoring: Same as the original conjecture, but assume that factoring is in P (i.e. given a k-digit number, one can compute all of its factors in time polynomial in k). This is more or less equivalent to assuming one has a factoring oracle that will return the factors of any number given to it (as a stream of bits) in unit time.
Semi-weak conjecture with factoring: Same as the semi-weak conjecture, but with factoring in P.
Weak conjecture with factoring: Same as the weak conjecture, but with factoring in P.

The weak conjecture with factoring is the easiest of the six, and so perhaps one should focus on that one first.

It is also of interest to see whether the conjecture becomes easier to solve assuming that P=BPP or P=BQP.

Partial results

  1. P=NP implies a deterministic algorithm to find primes
  2. An efficient algorithm exists if Cramer's conjecture holds
  3. k-digit primes can be found with high probability using O(k) random bits
    1. If pseudorandom number generators exist, the conjecture holds, as one can derandomise the above algorithm by substituting the pseudorandom number generator for the random string of bits.
  4. The function field analogue (i.e. finding degree k irreducible polynomials over a finite field) is known (see Adelman-Lenstra)
    1. The analogue over the rationals is even easier: Eisenstein's criterion provides plenty of irreducible polynomials of degree k, e.g. [math]\displaystyle{ x^k-2 }[/math].
  5. It's easy to deterministically find large square-free numbers; just multiply lots of small primes together
  6. If a fast algorithm to find primes exists, then an explicit fast algorithm to find primes exists: simply run all algorithms of size at most A simultaneously for time [math]\displaystyle{ k^A }[/math], then increment A from 1 onward, until one gets a hit.

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. For the conjecture with factoring, 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 (or [math]\displaystyle{ \log^{O(1)} N }[/math] smooth, if one only wants to solve the weak conjecture with factoring). 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. If one can make A arbitrarily large, one has solved the baby problem with factoring.
  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.

Negative results and other obstructions

  1. Using sieve theory to find a non-smooth number in a short interval runs into the difficulty that most sieve theory methods are insensitive to the starting point of an interval. Given that every integer in [1,n] is n-smooth, this implies that sieve theory is unlikely to establish the existence of a non-n-smooth number in any interval of length n, and in particular to find a non-[math]\displaystyle{ O(k^O(1)) }[/math] smooth integer in any interval that can be searched in polynomial time.
  2. Average-case results for the primes cannot be used directly, because one could delete all constructible integers from the set of primes (a negligible set) without significantly impacting the average case results, while causing the conjecture to fail for this modified set of primes.

How could the conjecture be false?

A world in which the conjecture is negative would be very strange, especially with factoring or if the weak conjecture fails also. 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 the conjecture fails with factoring, then these numbers are furthermore [math]\displaystyle{ \exp(\varepsilon k) }[/math] smooth for any fixed [math]\displaystyle{ \varepsilon \gt 0 }[/math]; if even the weak conjecture with factoring fails, 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. In particular, this implies that one-way functions do not exist.
  4. [math]\displaystyle{ P \neq NP }[/math]. More specifically, the decision problem "Does there exist a prime in a given interval?" is in NP, but cannot lie in P if the conjecture fails.

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. one-way function
  4. Impagliazzo's five worlds: Algorithmica, Heuristica, Pessiland, Minicrypt, Cryptomania
  5. Kolmogorov complexity
  6. Oracles
  7. Expander graphs
  8. Cramer's random model for the primes
  9. Prime gaps
  10. Smooth number
  11. The W-trick
  12. Asymptotic notation

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
  2. "Finding Primes", Lance Fortnow, August 4 2009