Finding primes

From Polymath1Wiki
Revision as of 14:10, 28 July 2009 by WikiSysop (Talk | contribs)

Jump to: navigation, search

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:


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. There is a deterministic algorithm to find primes if P=NP
  2. Problem is true if Cramer's conjecture holds (explain!)
  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] \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.

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