http://michaelnielsen.org/polymath1/api.php?action=feedcontributions&user=Asdf&feedformat=atomPolymath1Wiki - User contributions [en]2019-10-20T15:48:23ZUser contributionsMediaWiki 1.23.5http://michaelnielsen.org/polymath1/index.php?title=Finding_primesFinding primes2009-08-29T13:27:59Z<p>Asdf: </p>
<hr />
<div>This is the main wiki page for the Polymath4 project "[http://en.wordpress.com/tag/finding-primes/ Finding primes]".<br />
<br />
The main aim of the project is to resolve the following conjecture:<br />
<br />
:'''(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.<br />
<br />
Since primality is known to be in [[The complexity class P|P]] by the [[wikipedia:AKS_primality_test|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.<br />
<br />
Contributions and corrections to this wiki page (and its subpages) are very welcome.<br />
<br />
== Threads ==<br />
<br />
# [http://polymathprojects.org/2009/07/27/proposal-deterministic-way-to-find-primes/ Proposal for the project and initial research thread] Opened July 27. Inactive.<br />
# [http://polymathprojects.org/2009/08/09/research-thread-ii-deterministic-way-to-find-primes/ Research thread II] Opened Aug 9. Inactive.<br />
# [http://polymathprojects.org/2009/08/13/research-thread-iii-determinstic-way-to-find-primes/ Research thread III] Opened Aug 13. Inactive.<br />
# [http://polymathprojects.org/2009/08/28/research-thread-iv-determinstic-way-to-find-primes/ Research thread IV] Opened Aug 28. Active.<br />
# [http://polymathprojects.org/2009/07/28/deterministic-way-to-find-primes-discussion-thread/ The current discussion thread] Opened July 28. Active.<br />
<br />
== Easier versions of the problem ==<br />
<br />
:'''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 [[Finding primes with O(k) random bits|one can do this with O(k) random bits]]; and if one can use just <math>O(\log k)</math> random bits, one is done by exhausting over the random bits.)<br />
<br />
One way to solve the semi-weak conjecture would be to find an "explorable" set of size <math>\exp(o(k))</math> of integers, a significant fraction (at least <math>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).<br />
<br />
:'''Weak conjecture''': There exists a deterministic algorithm, which, when given an integer k, is guaranteed to find a prime of at least <math>\omega(\log k)</math> digits in length in time polynomial in k, where <math>\omega(\log k)</math> grows faster than <math>\log k</math> as <math>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>\exp(o(k))</math>. Note that the semi-weak conjecture implies the weak conjecture).<br />
<br />
:'''Strong conjecture with factoring''': Same as the original conjecture, but assume that one has a ''factoring oracle'' will return the factors of any number given to it (as a stream of bits) in unit time. (This oracle can be given "for free" if factoring is in P, but we can also assume the existence of this oracle even if factoring is not in P.)<br />
<br />
:'''Semi-weak conjecture with factoring''': Same as the semi-weak conjecture, but with a factoring oracle.<br />
<br />
:'''Weak conjecture with factoring''': Same as the weak conjecture, but with a factoring oracle. (Note that there are deterministic sieve algorithms, such as the quadratic sieve, which are believed to run in subexponential time <math>\exp(o(k))</math>, so this oracle is in some sense available "for free" for this problem assuming this belief.)<br />
<br />
The weak conjecture with factoring is the easiest of the six, and so perhaps one should focus on that one first.<br />
<br />
It is also of interest to see whether the conjecture becomes easier to solve assuming that P=BPP or P=BQP.<br />
<br />
== Partial results ==<br />
<br />
# [[P=NP implies a deterministic algorithm to find primes]]<br />
# [[An efficient algorithm exists if Cramer's conjecture holds]]<br />
# [[Finding primes with O(k) random bits|k-digit primes can be found with high probability using O(k) random bits]]<br />
## If [[Pseudo-random generators (PRG)|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.<br />
# The function field analogue (i.e. finding degree k irreducible polynomials over a finite field) is known [AL1986]<br />
## The analogue over the rationals is even easier: Eisenstein's criterion provides plenty of irreducible polynomials of degree k, e.g. <math>x^k-2</math>.<br />
# Assuming a suitably quantitative version of [[Schinzel's hypothesis H]] (namely, the Bateman-Horn conjecture), the weak conjecture is true, as one can simply search over all k-digit numbers of the form <math>n^d-2</math> (say) for any fixed d to give an algorithm that works in time <math>O(10^{k/d})</math>. By randomly sampling such integers, one also establishes the semi-weak conjecture (assuming that one has the expected density for primes in hypothesis H).<br />
# It's easy to deterministically find large square-free numbers; just multiply lots of small primes together. However, it is not known how to test a number for square-freeness deterministically and quickly (unless one has a factoring oracle, in which case it is trivial).<br />
## However, it's not so obvious how to find large pairs <math>n,n+1</math> of consecutive square-free numbers, though such pairs must exist by counting arguments (the density of square-free numbers is <math>6/\pi^2 \approx 60\%</math>). This could be a good variant problem.<br />
### It is conjectured that every element of [[Sylvester's sequence]] is square-free. If so, this solves the above problem.<br />
# 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>k^A</math>, then increment A from 1 onward, until one gets a hit.<br />
<br />
Here are the current "world records" for the fastest way to deterministically (and provably) obtain a k-digit prime (ignoring errors of <math>\exp(o(k))</math> in the run time):<br />
<br />
# <math>O(10^k)</math>: The trivial algorithm of testing each of the k-digit numbers in turn until one gets a hit.<br />
# <math>O(10^k)^{3/4}</math>: Test the k-digit numbers of the form <math>a^2+b^4</math> for primality (the [[Friedlander-Iwaniec theorem]] guarantees a hit for k large enough).<br />
# <math>O(10^k)^{2/3}</math>: Test the k-digit numbers of the form <math>a^3+2b^3</math> for primality (a hit is guaranteed for large k by a result of Heath-Brown).<br />
# <math>O(10^k)^{2/3}</math>: Use the [[Meissel-Lehmer method]] for computing <math>\pi(x)</math><br />
# <math>O(10^{k})^{6/11+\epsilon} (\approx O(10^{k})^{.5454})</math>assuming factoring oracle: Factor each number in the interval <math>[x^{12/11},x^{12/11}+x^{6/11+\epsilon}]</math>, one will find a prime prime factor of order x by [HB1995]. <br />
# <math>O(10^k)^{0.525}</math>: Test the k-digit numbers from, say, <math>10^k</math> onwards until one gets a hit (here we use the [BHP2001] bound on [[prime gaps]]).<br />
# <math>O(10^k)^{1/2}</math> assuming RH: Test the k-digit numbers from, say, <math>10^k</math> onwards until one gets a hit (here we use the RH bound on [[prime gaps]]).<br />
# <math>O(10^k)^{1/2}</math> using [[Odlyzko's method]].<br />
<br />
Note that if one can get <math>O(10^k)^{\varepsilon}</math> for each fixed <math>\varepsilon > 0</math>, then one has established the weak conjecture.<br />
<br />
A slight variant of the problem: assuming a factoring oracle, given an algorithm that runs in k steps, how large a prime is the algorithm ''guaranteed'' to produce in the ''worst-case'' scenario? (Note that this is very different from what the algorithm is ''heuristically'' predicted to produce in the ''average-case'' scenario.)<br />
<br />
Here is a simple algorithm that produces a prime larger than about <math>k \log k</math> in k steps, based on Euclid's proof of the infinitude of primes:<br />
<br />
* Initialise <math>p_1=2</math>.<br />
* Once <math>p_1,\ldots,p_{k-1}</math> are computed, define <math>p_k</math> to be the largest prime factor of <math>p_1 \ldots p_{k-1}+1</math>.<br />
<br />
This generates k distinct primes; the prime number theorem tells us that the k^th prime has size about <math>k \log k</math>, so at least one of the primes produced here has size at least <math>k \log k</math>.<br />
<br />
If one instead works with [[Sylvester's sequence]] <math>a_k = a_1 \ldots a_{k-1}+1</math>, then it is known [O1985] that the number of primes less than n that can divide any one of the <math>a_k</math> is <math>O( n / \log n \log \log \log n )</math> rather than <math>O(n/\log n)</math> (the prime number theorem bound). If we then factor the first k elements of this sequence, we must get a prime of size at least <math>k \log k \log \log \log k</math> or so.<br />
<br />
One can do better still by working with the Fermat numbers, <math>F_n = 2^{2^n}+1</math>. It is known [KLS2002] that the number of primes dividing any of the <math>F_n</math> is <math>O(\sqrt{n}/\log n)</math>, so in particular if we factor the first k Fermat numbers, we get a prime almost of size <math>k^2</math>. In fact, it's a classical result of Euler that the prime divisors of <math>F_n</math> are all at least <math>2^{n+2}+1</math>, so we can obtain a large prime simply by factoring a Fermat number.<br />
<br />
Assuming RH, one can find a prime larger than <math>k^2</math> in about k steps by the method indicated earlier (start at <math>k^2</math> and increment until one hits a prime). Unconditionally, one gets a prime larger than <math>k^{1/0.525}</math> by this method. Currently this is the world record.<br />
<br />
== Variants of the problem ==<br />
<br />
# 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.<br />
<br />
=== Finding consecutive (or nearby) square-free integers ===<br />
<br />
:'''Toy problem''' Is there an efficient algorithm to find consecutive square-free integers n, n+1 of at least k digits in length assuming an oracle to determine whether a number is square free (a special case of the factoring oracle)? Or just square-free integers that are close together (e.g. polylog(n)).<br />
<br />
Note that finding one large square-free number is easy: just multiply lots of distinct small primes together. Also, as the density of square-free numbers is <math>6/\pi^2 \approx 0.6</math>, a counting argument shows that pairs of consecutive square-free numbers exist in abundance, and are thus easy to find probabilistically. The density can be increased to arbitrarily close to 1 using the [[W-trick]], so one could also ask for, say, long arithmetic progressions of square-free numbers also.<br />
<br />
If [[Sylvester's sequence]] is square-free, then this solves the problem.<br />
<br />
Testing a number for square-freeness is trivial with a factoring oracle. No unconditional polynomial-time deterministic algorithm for square-freeness seems to be known. (It is listed as an open problem in [http://portal.acm.org/citation.cfm?id=749544 this paper from 1994].)<br />
<br />
Unconditionally, there are asymptotics for the number of square-free numbers in [1,N] with an error term of <math>O(N^{1/2})</math>, which leads to a <math>O(10^k)^{1/2}</math> algorithm (just search an interval of this length for square-freeness). This is the current unconditional world record. Assuming RH, this can be improved to <math>O(10^k)^{17/54+\varepsilon}</math>. <br />
<br />
There is an asymptotic [HB1984] for the number of consecutive square free numbers with an error term of <math>O(N^{7/11})</math>, leading to a <math>O(10^k)^{7/11+\varepsilon}</math>, though this is inferior to the above bounds.<br />
<br />
It is known [FT1992] that the interval <math>[N, N+N^{1/5+\epsilon}]</math> contains at least one square-free number; Granville [G1998] improved this to <math>[N,N+N^{\varepsilon}]</math> assuming the [[ABC conjecture]]. If the density in such intervals can be made to exceed 50% (perhaps after first applying the [[W-trick]]) then we would have solved the weak version of this toy problem assuming ABC.<br />
<br />
=== Finding pseudoprimes ===<br />
<br />
:'''Problem:''' How quickly can one find a solution to the congruence <math>2^{n-1}=1 \hbox{ mod } n</math> with n at least k digits in length? (a pseudoprime)?<br />
<br />
It is conjectured that the largest gap between k-digit pseudoprimes is poly(k) (this is weaker than [[Cramer's conjecture]], and would imply a polynomial time solution to the above problem).<br />
<br />
It is conjectured that the number <math>\mathcal{P}_a(x)</math> of pseudoprimes to any base <math>a \neq \pm1</math> satisfies<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) = \log(x) - \log(x)\frac{\log\log\log(x)}{\log\log(x)}(1+o(1)).</math><br />
<br />
However, the best known bounds seem to be<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) \leq \log(x) - \frac{1}{2}\log(x)\frac{\log\log\log(x)}{\log\log(x)}(1+o(1)),</math><br />
<br />
and<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) \geq (\frac{\log(x)}{\log a})^{E/(E+1)-o(1)},</math><br />
<br />
where E is a constant which is conjectured to equal 1, but is only known to have value at least 1-1/(2\sqrt{e}). These results can be found in [P1981], [P1982], [P1989]. Better bounds are known to hold on average [EP1986].<br />
<br />
If n is a pseudoprime, then <math>2^n-1</math> is also a pseudoprime (because <math>2^n = 1 \hbox{ mod } 2^n - 1 </math>, and <math>2^n-2</math> is a multiple of n). This, technically, solves the problem, but can we find denser sets of pseudoprimes? What if we want <math>2^{n-1}=1 \hbox{ mod } n</math> and <math>3^{n-1} = 1 \hbox{ mod } n</math> simultaneously?<br />
<br />
=== Finding Almost Primes===<br />
<br />
An almost primes is a number that is the product of at most two primes (counted with multiplicity). <br />
<br />
:'''problem''' How fast can we deterministically write down a <math>k</math> digit almost prime?<br />
<br />
Clearly this is a relaxation of the prime problem, so we expect to get better results. In [L1996] it is shown that the interval <math>[x,x+x^{.436}]</math> contains an almost prime. This gives us a <math>O(10^{k})^{.436}</math> algorithm. Assuming a factoring oracle, the problems of deterministically finding a <math>k</math> digit almost prime and a <math>k</math> digit prime in polynomial time are equivalent. If we can find an almost prime in polynomial time we can factor it and get (a slightly smaller) prime. Conversely, if we can find a prime in polynomial time we can square it to find (a slightly larger) almost prime. Using our prime technology this should give a <math>O(10^{k})^{.262}</math> algorithm.<br />
<br />
== Observations and strategies ==<br />
<br />
# 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>N^\varepsilon</math>-smooth (or <math>\log^{O(1)} N</math> smooth, if one only wants to solve the weak conjecture with factoring). <br />
## 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>\{ Wn+1: 1 \leq n \leq k^{100} \}</math> (say) is <math>k^A</math>-smooth, then one has found a prime with at least <math>A \log k</math> digits in polynomial time. If one can make A arbitrarily large, one has solved the baby problem with factoring.<br />
## One way to proceed is to analyse [[iterated sumsets of log-primes]].<br />
## Another is to analyse [[signed sums of prime reciprocals]].<br />
## Probably the best known bound along these lines is given in [HB1995] and states that the interval <math>[x,x+x^{.5+\epsilon}]</math> contains an integer with a prime factor at least <math>x^{11/12 -\epsilon}</math>. This only leads to a <math>O(10^{k})^{.5455}</math> algorithm.<br />
# Another approach is to accurately compute the [[prime counting function]].<br />
# If one can find explicitly enumerable sets of k-digit numbers of size <math>O(10^{\varepsilon k})</math> for any fixed <math>\varepsilon > 0</math> that are guaranteed to contain a prime, then one has solved the weak conjecture. If instead one can find randomly samplable sets of k-digit numbers of size <math>O(10^{\varepsilon k})</math> that contain a large fraction (e.g. <math>\exp(-o(k))</math> of primes), one has solved the semi-weak conjecture. If one can find explicit sets of poly(k) size that are guaranteed to contain a prime, one has solved the strong conjecture.<br />
# 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 [[wikipedia:Pseudorandom_generators_for_polynomials|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.<br />
# If one can find a sequence of easily constructible, mutually coprime integers whose prime factors are contained in a sparse subset of the primes, this generates (with the aid of a factoring oracle) a sparse set of primes. So far the sparsest set of this type has come from factoring the Fermat numbers.<br />
<br />
== Negative results and other obstructions ==<br />
<br />
# 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>O(k^O(1))</math> smooth integer in any interval that can be searched in polynomial time. Indeed, there are heuristic arguments that suggest that even augmented with basic Fourier analysis and assuming RH, this method is unlikely to work, although they haven't yet been fully formalized.<br />
# 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.<br />
## In a similar spirit, one cannot hope to find non-smooth numbers in a short interval by analysing the iterated sumset of the log-primes and using average-case information about that set), because if one deletes all the primes arising from factors of that interval, one still captures most of the primes (and thus most of the average-case behaviour of the log-primes) while losing the information about that interval. <br />
# It is not possible to prove the conjecture purely by "soft" (i.e. relativisable) complexity theory methods which do not use any additional information on the primes rather than their density. Details are at [[Oracle counterexample to finding pseudoprimes]].<br />
<br />
== How could the conjecture be false? ==<br />
<br />
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:<br />
<br />
# 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>O(\log k)</math> that runs in time <math>k^{O(1)}</math>, are composite. [If the conjecture fails with factoring, then these numbers are furthermore <math>\exp(\varepsilon k)</math> smooth for any fixed <math>\varepsilon > 0</math>; if even the weak conjecture with factoring fails, they are <math>k^{O(1)}</math>-smooth.]<br />
# In fact, all constructible numbers are not only composite/smooth, but they sit inside intervals of length <math>k^{100}</math>, all of whose elements are composite/smooth. (One can replace 100 by any other fixed number.)<br />
## In particular, Cramer's conjecture fails; the gaps between adjacent k-digit primes exceeds <math>k^{100}</math> around every constructible number.<br />
# No pseudorandom number generators exist. In particular, this implies that one-way functions do not exist.<br />
# <math>P \neq NP</math>. More specifically, the decision problem "Does there exist a prime in a given interval?" is in [[The complexity class NP|NP]], but cannot lie in [[The complexity class P|P]] if the conjecture fails.<br />
<br />
== Relevant concepts ==<br />
<br />
Complexity theory concepts:<br />
<br />
# Complexity classes<br />
## [[The complexity class P|P]]<br />
## [[The complexity class NP|NP]]<br />
## [[The complexity class BPP|BPP]]<br />
## [[The complexity class promise-BPP|promise-BPP]]<br />
## [[The complexity class BQP|BQP]]<br />
## [[The complexity class DTIME|DTIME(f(n))]]<br />
# [[Pseudo-random generators (PRG)]]<br />
# [http://blog.computationalcomplexity.org/2006/07/full-derandomization.html Full derandomization]<br />
# [[wikipedia:One-way_function|one-way function]]<br />
# [http://cseweb.ucsd.edu/~russell/average.ps Impagliazzo's five worlds]: Algorithmica, Heuristica, Pessiland, Minicrypt, Cryptomania<br />
# [[Kolmogorov complexity]]<br />
# [[wikipedia:Oracle_machine|Oracles]]<br />
<br />
Number theory concepts:<br />
<br />
# [[Cramer's random model for the primes]]<br />
# [[Prime gaps]]<br />
# [[Generic prime]]<br />
# [[Smooth number]]<br />
# The [[W-trick]]<br />
# [[Sylvester's sequence]]<br />
# [[wikipedia:Siegel_zero|Siegel zero]]<br />
# [[wikipedia:Big_O_notation|Asymptotic notation]]<br />
# [[wikipedia:Fermat_number|Fermat number]]<br />
# [[Pseudoprimes]]<br />
<br />
Other:<br />
<br />
# [[wikipedia:Expander_graph|Expander graphs]]<br />
<br />
Note: articles with external links should eventually be replaced by in-house pages that can provide information that is more dedicated to this project.<br />
<br />
== Relevant conjectures ==<br />
<br />
# [[The complexity class NP|P=NP]]<br />
# [[The complexity class BPP|P=BPP]]<br />
# [[The complexity class promise-BPP|P=promise-BPP]]<br />
# [[The complexity class BQP|P=BQP]]<br />
# [[Pseudo-random generators (PRG)|existence of PRG]]<br />
# [[wikipedia:One-way_function|existence of one-way functions]]<br />
# whether [[The complexity class DTIME|DTIME(2^n)]] has subexponential circuits<br />
# [[wikipedia:Riemann_hypothesis|The Riemann Hypothesis (RH)]]<br />
## [[wikipedia:Generalized_Riemann_hypothesis|The generalised Riemann Hypothesis (GRH)]]<br />
# the [[Hardy-Littlewood prime tuples conjecture]]<br />
# the [[ABC conjecture]]<br />
# [[Cramer's conjecture]]<br />
# [[Schinzel's hypothesis H]]<br />
# [[discrete logarithm|discrete log in P]]<br />
# [[factoring|factoring in P]]<br />
<br />
== Relevant results ==<br />
<br />
# [[Brun-Titchmarsh inequality]]<br />
# [[Erdos-Kac theorem]]<br />
# [[Bertrand's postulate]]<br />
# [[Friedlander-Iwaniec theorem]]<br />
# [[List of results implied by the Riemann Hypothesis|Conditional on the Riemann hypothesis]]<br />
<br />
== Relevant papers ==<br />
<br />
* [AMcC1994] L. Adelman, K. McCurley, [http://portal.acm.org/citation.cfm?id=749544 Open problems in number theoretic complexity, II], Lecture Notes In Computer Science; Vol. 877, Proceedings of the First International Symposium on Algorithmic Number Theory 291 - 322 (1994)<br />
* [AL1986] L. Adelman, H. Lenstra, [http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf Finding irreducible polynomials over finite fields], Proc. 18th Annual ACM Symp. on Theory of Computing (STOC), Berkeley, May 28–30, 350–355.<br />
* [B1990] E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), 355-380], <br />
* [BH1996] R. C. Baker and G. Harman, “The difference between consecutive primes,” Proc. Lond. Math. Soc., series 3, 72 (1996) 261–280. <br />
*[BH1998] R. C. Baker, G. Harman, Shifted primes without large prime factors, Acta Arith. 83 (1998), no. 4, 331–361<br />
* [BHP2001] R. C. Baker, G. Harman and J. Pintz, The difference between consecutive primes, II, Proceedings of the London Mathematical Society 83, (2001), 532–562.<br />
* [BH1998] A. Balog, T. Wooley, “[http://www.austms.org.au/Publ/JAustMS/V64P2/abs/c30/ On strings of consecutive integers with no large prime factors]”, J. Austral. Math. Soc. Ser. A 64 (1998), no. 2, 266–276<br />
* [C2006] T. H. Chan, [http://arxiv.org/abs/math/0502199 Finding almost squares]. Acta Arith. 121 (2006), no. 3, 221--232.<br />
* [D1998] P. Dusart, [http://www.unilim.fr/laco/theses/1998/T1998_01.html Autour de la fonction qui compte le nombre de nombres premiers], 1998<br />
* [E1949] P. Erdős, [http://www.math-inst.hu/~p_erdos/1949-07.pdf On The Converse of Fermat's Theorem]<br />
* [EP1986] P. Erdős and C. Pomerance, On the number of false witnesses for a composite number, Math. Comp. 46 (1986), 259-279.<br />
* [FT????] M. Filaseta, O. Trifonov, [http://books.google.com/books?id=G02moOmuOX4C&pg=PA235&dq=squarefree+numbers#v=onepage&q=squarefree%20numbers&f=false On gaps between squarefree numbers], Analytic number theory: Proceedings of a conference in honor of Paul Bateman <br />
* [FT1992] M. Filaseta and O. Trifonov, On gaps between squarefree numbers. II, J. London Math. Soc. (2), 45 (1992), no. 2, 215-221. <br />
* [GW2002] O. Goldreich, A. Wigderson, [http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GW02/gw02.pdf Derandomization that is rarely wrong from short advice that is typically good]<br />
* [G1998] A. Granville, ABC allows us to count squarefrees, Internat. Math. Res. Notices (1998), no. 19, 991–1009.<br />
* [G1995] A. Granville, [http://www.dartmouth.edu/~chance/chance_news/for_chance_news/Riemann/cramer.pdf "Harald Cramér and the distribution of prime numbers"], Scandinavian Actuarial J. 1 (1995), 12—28. <br />
* [HB1984] D.R. Heath-Brown, The square sieve and consecutive square-free numbers, Math. Ann. 266 (1984), 251-259<br />
* [HB1995] D.R. Heath-Brown, The largest prime factor of integers in an interval, Science in China ???<br />
* [IW1997] 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.<br />
* [J2006] R. Jones, [http://arxiv.org/abs/math/0612415 The density of prime divisors in the arithmetic dynamics of quadratic polynomials]<br />
* [KLS2002] Křížek, Luca and Somer, On the convergence of series of reciprocals of primes related to the Fermat numbers, J. Number Theory 97(2002), 95–112<br />
* [LMO???] J. Lagarias, V. Miller, A. Odlyzko, [http://www.dtc.umn.edu/~odlyzko/doc/arch/meissel.lehmer.pdf Computing <math>\pi(x)</math>: the Meissel-Lehmer method]<br />
* [L1979] H.W. Lenstra, [https://openaccess.leidenuniv.nl/bitstream/1887/3801/1/346_036.pdf Miller's Primality Test], Information Processing Letters, 1979<br />
* [L1996] H. Liu, Almost primes in short intervals. J. Number Theory 57 (1996), no. 2, 303--322.<br />
* [LW1999] H. Liu, J. Wu, Numbers with a large prime factor, Acta Arith. 89 (1999), no. 2, 163–187.<br />
* [M1994] U. Maurer, [http://eprints.kfupm.edu.sa/40655/ Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters], Journal of Cryptology 8 (1994), 123-155<br />
* [O1993] A. Odlyzko, Analytic computations in number theory, Mathematics of Computation 1943–1993: a half-century of computational mathematics (Vancouver, BC, 1993), 451–463.<br />
* [O1985] Odoni, On the prime divisors of the sequence <math>w_n+1 = 1+ w_1 \ldots w_n</math>. J. London Math. Soc. (2), 32(1):1–11, 1985. <br />
* [P????] F. Pappalardi, [http://www.mat.uniroma3.it/users/pappa/papers/allahabad2003.pdf A survey on k-freeness]<br />
* [P1981] C. Pomerance, [http://math.dartmouth.edu/~carlp/PDF/paper32.pdf On the distribution of pseudoprimes, Math. Comp. 37 (1981), 587-593.]<br />
* [P1982] C. Pomerance, [http://math.dartmouth.edu/~carlp/PDF/lower.pdf A new lower bound for the pseudoprime counting function, Illinois J. Math. 26 (1982), 4-9.]<br />
* [P1989] C. Pomerance, Two methods in elementary analytic number theory, Number theory and applications, R. A. Mollin, ed., Kluwer Academic Publishers, Dordrecht, 1989, pp. 135-161.<br />
<br />
* [S2006] K. Soundararajan, [http://arxiv.org/abs/math/0606408 The distribution of the primes] (survey)<br />
* [S2006b] K. Soundararajan, [http://arxiv.org/abs/math/0605696 Small gaps between prime numbers: The work of Goldston-Pintz-Yildirim]<br />
* [T2006] L. Trevisan, [http://arxiv.org/abs/cs.CC/0601100 Pseudorandomness and Combinatorial Constructions]<br />
<br />
Please help out by adding links or completing references, or adding further references to the list above!<br />
<br />
== External links ==<br />
<br />
# [http://qwiki.stanford.edu/wiki/Complexity_Zoo Complexity Zoo]<br />
# "[http://blog.computationalcomplexity.org/2009/08/finding-primes.html Finding Primes]", Lance Fortnow, August 4 2009</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Cramer%27s_conjectureCramer's conjecture2009-08-20T01:10:57Z<p>Asdf: </p>
<hr />
<div>'''Cramér's conjecture''' asserts that the largest gap between adjacent primes of size N should be <math>O(\log^2 N)</math>. This is compatible with [[Cramer's random model for the primes]], and specifically with the belief that the number of primes in <math>[n,n+\log n]</math> should resemble a Poisson distribution asymptotically.<br />
<br />
If this conjecture is true, one has an [[An efficient algorithm exists if Cramer's conjecture holds|easy positive answer]] to the [[finding primes]] project in the strongest form; one simply searches an interval of the form <math>[N, N+O(\log^2 N)]</math> for primes, where N is your favourite k-digit number.<br />
<br />
# [[wikipedia:Cramér's_conjecture|Wikipedia entry on Cramér's conjecture]]</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=An_efficient_algorithm_exists_if_Cramer%27s_conjecture_holdsAn efficient algorithm exists if Cramer's conjecture holds2009-08-20T01:09:00Z<p>Asdf: </p>
<hr />
<div>[[Cramer's conjecture]] asserts that for sufficiently large n there is a prime between n and <math>n+C(\log n)^2</math>. This conjecture is plausible if you believe that when you pick a random integers m near n, then the events "m is prime" are roughly independent. In that case, the number of primes between n and <math>n+C(\log n)^2</math> should have a Poisson distribution with mean <math>C\log n</math> (by the prime number theorem), which means that the probability of getting no prime will be around <math>\exp(-C\log n)</math>. If we take C to be greater than 2, then the sum <math>\sum_{n=N}^\infty n\exp(-C\log n)=\sum_{n=N}^\infty n^{1-C}</math> converges to around <math>N^{2-C}</math>, so we expect there to be no values of n greater than N for which Cramer's conjecture fails.<br />
<br />
Unfortunately, nobody knows how to prove independence of this kind (even after adjusting for obvious dependences, such as the fact that if n is a prime greater than 2, then n+1 is not prime). If they did, then the twin prime conjecture would follow easily, for instance.<br />
<br />
If Cramer's conjecture is true, then from that and the fact that primality testing is in [[The complexity class P|P]] it follows instantly that there is a polynomial-time algorithm for finding a k-digit prime. You just search through all the integers from <math>10^{k-1}</math> to <math>10^{k-1}+Ck^2</math>, testing each one for primality in time p(k). This interval is guaranteed to contain a prime, so the algorithm terminates after at most <math>Ck^2p(k)</math> steps.<br />
<br />
This is interesting, and shows that there is a deterministic algorithm for finding k-digit primes that probably works. The trouble is, we don't know how to prove that it works, and are basing our belief that it works on a very strong conjecture. This makes our belief less secure than it would be if we based it on a conjecture such as GRH that has rather more evidence in its favour.<br />
<br />
Needless to say, we could increase the security of the above approach by using the weaker conjecture that there is a prime between n and <math>n+(\log n)^{1000}</math>. Unexpected phenomena do sometimes occur in the distribution of primes ''[reference needed to Maier's work here]'', so using a higher power would make the conjecture more robust. But it would still be way beyond what anyone knows how to prove.</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Cramer%27s_conjectureCramer's conjecture2009-08-20T01:05:05Z<p>Asdf: </p>
<hr />
<div>'''Cramér's conjecture''' asserts that the largest gap between adjacent primes of size N should be <math>O(\log^2 N)</math>. This is compatible with [[Cramer's random model for the primes]], and specifically with the belief that the number of primes in <math>[n,n+\log n]</math> should resemble a Poisson distribution asymptotically.<br />
<br />
If this conjecture is true, one has an easy positive answer to the [[finding primes]] project in the strongest form; one simply searches an interval of the form <math>[N, N+O(\log^2 N)]</math> for primes, where N is your favourite k-digit number.<br />
<br />
# [[wikipedia:Cramér's_conjecture|Wikipedia entry on Cramér's_conjecture]]</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Cramer%27s_conjectureCramer's conjecture2009-08-20T01:04:47Z<p>Asdf: </p>
<hr />
<div>'''Cramér's_conjecture''' asserts that the largest gap between adjacent primes of size N should be <math>O(\log^2 N)</math>. This is compatible with [[Cramer's random model for the primes]], and specifically with the belief that the number of primes in <math>[n,n+\log n]</math> should resemble a Poisson distribution asymptotically.<br />
<br />
If this conjecture is true, one has an easy positive answer to the [[finding primes]] project in the strongest form; one simply searches an interval of the form <math>[N, N+O(\log^2 N)]</math> for primes, where N is your favourite k-digit number.<br />
<br />
# [[wikipedia:Cramér's_conjecture|Wikipedia entry on Cramér's_conjecture]]</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Schinzel%27s_hypothesis_HSchinzel's hypothesis H2009-08-20T00:49:22Z<p>Asdf: </p>
<hr />
<div>'''Hypothesis H''' is a variant of the [[Hardy-Littlewood prime tuples conjecture]]. It asserts that a non-constant polynomial f(n) with integer coefficients will take infinitely many prime values as long as there is no "obvious" reason for it not to, for instance if it is not coprime to a fixed modulus q for all n, or if it is only positive for finitely many n, or if it factors into polynomials of smaller degree.<br />
<br />
It is known for linear polynomials (Dirichlet's theorem), but is open for higher degree (most notably for <math>n^2+1</math>).<br />
<br />
A stronger version of this hypothesis (the ''Bateman-Horn conjecture'') would assert that there is a k-digit prime of the form f(n) for all sufficiently large n. If this is the case, one can solve the weak version of the [[finding primes]] project by searching the k-digit values of a degree d irreducible polynomial, such as <math>n^d-2</math>, to find a prime in <math>O( (10^k)^{1/d} )</math> steps for any given d.<br />
<br />
# [[wikipedia:Schinzel's_hypothesis_H|Wikipedia page for this hypothesis]]<br />
# [[wikipedia:Bateman-Horn_conjecture|Wikipedia page for the Bateman-Horn conjecture]]</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Smooth_numberSmooth number2009-08-20T00:39:12Z<p>Asdf: </p>
<hr />
<div>An integer is ''S-smooth'' if it does not contain any prime factors less than or equal to S. The relevance of this concept to the [[finding primes]] project is that if one inserts a non-S-smooth number into a [[factoring|factoring oracle]], one will obtain a prime of size greater than S. So it would suffice to find a small (and enumerable) set which is guaranteed to contain at least one non-S-smooth number for some large S.<br />
<br />
* [[wikipedia:Smooth_number|The Wikipedia entry on smooth numbers]]</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Finding_primesFinding primes2009-08-20T00:37:17Z<p>Asdf: </p>
<hr />
<div>This is the main wiki page for the Polymath4 project "[http://en.wordpress.com/tag/finding-primes/ Finding primes]".<br />
<br />
The main aim of the project is to resolve the following conjecture:<br />
<br />
:'''(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.<br />
<br />
Since primality is known to be in [[The complexity class P|P]] by the [[wikipedia:AKS_primality_test|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.<br />
<br />
Contributions and corrections to this wiki page (and its subpages) are very welcome.<br />
<br />
== Threads ==<br />
<br />
# [http://polymathprojects.org/2009/07/27/proposal-deterministic-way-to-find-primes/ Proposal for the project and initial research thread] (Inactive)<br />
# [http://polymathprojects.org/2009/08/09/research-thread-ii-deterministic-way-to-find-primes/ Research thread II] (Inactive)<br />
# [http://polymathprojects.org/2009/08/13/research-thread-iii-determinstic-way-to-find-primes/ Research thread III] (Active)<br />
# [http://polymathprojects.org/2009/07/28/deterministic-way-to-find-primes-discussion-thread/ The current discussion thread] (Active)<br />
<br />
== Easier versions of the problem ==<br />
<br />
:'''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 [[Finding primes with O(k) random bits|one can do this with O(k) random bits]]; and if one can use just <math>O(\log k)</math> random bits, one is done by exhausting over the random bits.)<br />
<br />
One way to solve the semi-weak conjecture would be to find an "explorable" set of size <math>\exp(o(k))</math> of integers, a significant fraction (at least <math>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).<br />
<br />
:'''Weak conjecture''': There exists a deterministic algorithm, which, when given an integer k, is guaranteed to find a prime of at least <math>\omega(\log k)</math> digits in length in time polynomial in k, where <math>\omega(\log k)</math> grows faster than <math>\log k</math> as <math>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>\exp(o(k))</math>. Note that the semi-weak conjecture implies the weak conjecture).<br />
<br />
:'''Strong conjecture with factoring''': Same as the original conjecture, but assume that one has a ''factoring oracle'' will return the factors of any number given to it (as a stream of bits) in unit time. (This oracle can be given "for free" if factoring is in P, but we can also assume the existence of this oracle even if factoring is not in P.)<br />
<br />
:'''Semi-weak conjecture with factoring''': Same as the semi-weak conjecture, but with a factoring oracle.<br />
<br />
:'''Weak conjecture with factoring''': Same as the weak conjecture, but with a factoring oracle. (Note that there are deterministic sieve algorithms, such as the quadratic sieve, which are believed to run in subexponential time <math>\exp(o(k))</math>, so this oracle is in some sense available "for free" for this problem assuming this belief.)<br />
<br />
The weak conjecture with factoring is the easiest of the six, and so perhaps one should focus on that one first.<br />
<br />
It is also of interest to see whether the conjecture becomes easier to solve assuming that P=BPP or P=BQP.<br />
<br />
== Partial results ==<br />
<br />
# [[P=NP implies a deterministic algorithm to find primes]]<br />
# [[An efficient algorithm exists if Cramer's conjecture holds]]<br />
# [[Finding primes with O(k) random bits|k-digit primes can be found with high probability using O(k) random bits]]<br />
## If [[Pseudo-random generators (PRG)|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.<br />
# The function field analogue (i.e. finding degree k irreducible polynomials over a finite field) is known [AL1986]<br />
## The analogue over the rationals is even easier: Eisenstein's criterion provides plenty of irreducible polynomials of degree k, e.g. <math>x^k-2</math>.<br />
# Assuming a suitably quantitative version of [[Schinzel's hypothesis H]] (namely, the Bateman-Horn conjecture), the weak conjecture is true, as one can simply search over all k-digit numbers of the form <math>n^d-2</math> (say) for any fixed d to give an algorithm that works in time <math>O(10^{k/d})</math>. By randomly sampling such integers, one also establishes the semi-weak conjecture (assuming that one has the expected density for primes in hypothesis H).<br />
# It's easy to deterministically find large square-free numbers; just multiply lots of small primes together. However, it is not known how to test a number for square-freeness deterministically and quickly (unless one has a factoring oracle, in which case it is trivial).<br />
## However, it's not so obvious how to find large pairs <math>n,n+1</math> of consecutive square-free numbers, though such pairs must exist by counting arguments (the density of square-free numbers is <math>6/\pi^2 \approx 60\%</math>). This could be a good variant problem.<br />
### It is conjectured that every element of [[Sylvester's sequence]] is square-free. If so, this solves the above problem.<br />
# 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>k^A</math>, then increment A from 1 onward, until one gets a hit.<br />
<br />
Here are the current "world records" for the fastest way to deterministically (and provably) obtain a k-digit prime (ignoring errors of <math>\exp(o(k))</math> in the run time):<br />
<br />
# <math>O(10^k)</math>: The trivial algorithm of testing each of the k-digit numbers in turn until one gets a hit.<br />
# <math>O(10^k)^{3/4}</math>: Test the k-digit numbers of the form <math>a^2+b^4</math> for primality (the [[Friedlander-Iwaniec theorem]] guarantees a hit for k large enough).<br />
# <math>O(10^k)^{2/3}</math>: Test the k-digit numbers of the form <math>a^3+2b^3</math> for primality (a hit is guaranteed for large k by a result of Heath-Brown).<br />
# <math>O(10^{k})^{6/11+\epsilon} (\approx O(10^{k})^{.5454})</math>assuming factoring oracle: Factor each number in the interval <math>[x^{12/11},x^{12/11}+x^{6/11+\epsilon}]</math>, one will find a prime prime factor of order x by [HB1995]. <br />
# <math>O(10^k)^{0.525}</math>: Test the k-digit numbers from, say, <math>10^k</math> onwards until one gets a hit (here we use the [BHP2001] bound on [[prime gaps]]).<br />
# <math>O(10^k)^{1/2}</math> assuming RH: Test the k-digit numbers from, say, <math>10^k</math> onwards until one gets a hit (here we use the RH bound on [[prime gaps]]).<br />
<br />
Note that if one can get <math>O(10^k)^{\varepsilon}</math> for each fixed <math>\varepsilon > 0</math>, then one has established the weak conjecture.<br />
<br />
A slight variant of the problem: assuming a factoring oracle, given an algorithm that runs in k steps, how large a prime is the algorithm ''guaranteed'' to produce in the ''worst-case'' scenario? (Note that this is very different from what the algorithm is ''heuristically'' predicted to produce in the ''average-case'' scenario.)<br />
<br />
Here is a simple algorithm that produces a prime larger than about <math>k \log k</math> in k steps, based on Euclid's proof of the infinitude of primes:<br />
<br />
* Initialise <math>p_1=2</math>.<br />
* Once <math>p_1,\ldots,p_{k-1}</math> are computed, define <math>p_k</math> to be the largest prime factor of <math>p_1 \ldots p_{k-1}+1</math>.<br />
<br />
This generates k distinct primes; the prime number theorem tells us that the k^th prime has size about <math>k \log k</math>, so at least one of the primes produced here has size at least <math>k \log k</math>.<br />
<br />
If one instead works with [[Sylvester's sequence]] <math>a_k = a_1 \ldots a_{k-1}+1</math>, then it is known [O1985] that the number of primes less than n that can divide any one of the <math>a_k</math> is <math>O( n / \log n \log \log \log n )</math> rather than <math>O(n/\log n)</math> (the prime number theorem bound). If we then factor the first k elements of this sequence, we must get a prime of size at least <math>k \log k \log \log \log k</math> or so.<br />
<br />
One can do better still by working with the Fermat numbers, <math>F_n = 2^{2^n}+1</math>. It is known [KLS2002] that the number of primes dividing any of the <math>F_n</math> is <math>O(\sqrt{n}/\log n)</math>, so in particular if we factor the first k Fermat numbers, we get a prime almost of size <math>k^2</math>. In fact, it's a classical result of Euler that the prime divisors of <math>F_n</math> are all at least <math>2^{n+2}+1</math>, so we can obtain a large prime simply by factoring a Fermat number.<br />
<br />
Assuming RH, one can find a prime larger than <math>k^2</math> in about k steps by the method indicated earlier (start at <math>k^2</math> and increment until one hits a prime). Unconditionally, one gets a prime larger than <math>k^{1/0.525}</math> by this method. Currently this is the world record.<br />
<br />
== Variants of the problem ==<br />
<br />
# 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.<br />
<br />
=== Finding consecutive (or nearby) square-free integers ===<br />
<br />
:'''Toy problem''' Is there an efficient algorithm to find consecutive square-free integers n, n+1 of at least k digits in length assuming an oracle to determine whether a number is square free (a special case of the factoring oracle)? Or just square-free integers that are close together (e.g. polylog(n)).<br />
<br />
Note that finding one large square-free number is easy: just multiply lots of distinct small primes together. Also, as the density of square-free numbers is <math>6/\pi^2 \approx 0.6</math>, a counting argument shows that pairs of consecutive square-free numbers exist in abundance, and are thus easy to find probabilistically. The density can be increased to arbitrarily close to 1 using the [[W-trick]], so one could also ask for, say, long arithmetic progressions of square-free numbers also.<br />
<br />
If [[Sylvester's sequence]] is square-free, then this solves the problem.<br />
<br />
Testing a number for square-freeness is trivial with a factoring oracle. No unconditional polynomial-time deterministic algorithm for square-freeness seems to be known. (It is listed as an open problem in [http://portal.acm.org/citation.cfm?id=749544 this paper from 1994].)<br />
<br />
Unconditionally, there are asymptotics for the number of square-free numbers in [1,N] with an error term of <math>O(N^{1/2})</math>, which leads to a <math>O(10^k)^{1/2}</math> algorithm (just search an interval of this length for square-freeness). This is the current unconditional world record. Assuming RH, this can be improved to <math>O(10^k)^{17/54+\varepsilon}</math>. <br />
<br />
There is an asymptotic [HB1984] for the number of consecutive square free numbers with an error term of <math>O(N^{7/11})</math>, leading to a <math>O(10^k)^{7/11+\varepsilon}</math>, though this is inferior to the above bounds.<br />
<br />
It is known [FT1992] that the interval <math>[N, N+N^{1/5+\epsilon}]</math> contains at least one square-free number; Granville [G1998] improved this to <math>[N,N+N^{\varepsilon}]</math> assuming the [[ABC conjecture]]. If the density in such intervals can be made to exceed 50% (perhaps after first applying the [[W-trick]]) then we would have solved the weak version of this toy problem assuming ABC.<br />
<br />
=== Finding pseudoprimes ===<br />
<br />
:'''Problem:''' How quickly can one find a solution to the congruence <math>2^{n-1}=1 \hbox{ mod } n</math> with n at least k digits in length? (a pseudoprime)?<br />
<br />
It is conjectured that the largest gap between k-digit pseudoprimes is poly(k) (this is weaker than [[Cramer's conjecture]], and would imply a polynomial time solution to the above problem).<br />
<br />
It is conjectured that the number <math>\mathcal{P}_a(x)</math> of pseudoprimes to any base <math>a \neq \pm1</math> satisfies<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) = \log(x) - \log(x)\frac{\log\log\log(x)}{\log\log(x)}(1+o(1)).</math><br />
<br />
However, the best known bounds seem to be<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) \leq \log(x) - \frac{1}{2}\log(x)\frac{\log\log\log(x)}{\log\log(x)}(1+o(1)),</math><br />
<br />
and<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) \geq (\frac{\log(x)}{\log a})^{E/(E+1)-o(1)},</math><br />
<br />
where E is a constant which is conjectured to equal 1, but is only known to have value at least 1-1/(2\sqrt{e}). These results can be found in [P1981], [P1982], [P1989]. Better bounds are known to hold on average [EP1986].<br />
<br />
If n is a pseudoprime, then <math>2^n-1</math> is also a pseudoprime (because <math>2^n = 1 \hbox{ mod } 2^n - 1 </math>, and <math>2^n-2</math> is a multiple of n). This, technically, solves the problem, but can we find denser sets of pseudoprimes? What if we want <math>2^{n-1}=1 \hbox{ mod } n</math> and <math>3^{n-1} = 1 \hbox{ mod } n</math> simultaneously?<br />
<br />
=== Finding Almost Primes===<br />
<br />
An almost primes is a number that is the product of at most two primes (counted with multiplicity). <br />
<br />
:'''problem''' How fast can we deterministically write down a <math>k</math> digit almost prime?<br />
<br />
Clearly this is a relaxation of the prime problem, so we expect to get better results. In [L1996] it is shown that the interval <math>[x,x+x^{.436}]</math> contains an almost prime. This gives us a <math>O(10^{k})^{.436}</math> algorithm. Assuming a factoring oracle, the problems of deterministically finding a <math>k</math> digit almost prime and a <math>k</math> digit prime in polynomial time are equivalent. If we can find an almost prime in polynomial time we can factor it and get (a slightly smaller) prime. Conversely, if we can find a prime in polynomial time we can square it to find (a slightly larger) almost prime. Using our prime technology this should give a <math>O(10^{k})^{.262}</math> algorithm.<br />
<br />
== Observations and strategies ==<br />
<br />
# 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>N^\varepsilon</math>-smooth (or <math>\log^{O(1)} N</math> smooth, if one only wants to solve the weak conjecture with factoring). <br />
## 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>\{ Wn+1: 1 \leq n \leq k^{100} \}</math> (say) is <math>k^A</math>-smooth, then one has found a prime with at least <math>A \log k</math> digits in polynomial time. If one can make A arbitrarily large, one has solved the baby problem with factoring.<br />
## One way to proceed is to analyse [[iterated sumsets of log-primes]].<br />
## Another is to analyse [[signed sums of prime reciprocals]].<br />
## Probably the best known bound along these lines is given in [HB1995] and states that the interval <math>[x,x+x^{.5+\epsilon}]</math> contains an integer with a prime factor at least <math>x^{11/12 -\epsilon}</math>. This only leads to a <math>O(10^{k})^{.5455}</math> algorithm.<br />
# Another approach is to accurately compute the [[prime counting function]].<br />
# If one can find explicitly enumerable sets of k-digit numbers of size <math>O(10^{\varepsilon k})</math> for any fixed <math>\varepsilon > 0</math> that are guaranteed to contain a prime, then one has solved the weak conjecture. If instead one can find randomly samplable sets of k-digit numbers of size <math>O(10^{\varepsilon k})</math> that contain a large fraction (e.g. <math>\exp(-o(k))</math> of primes), one has solved the semi-weak conjecture. If one can find explicit sets of poly(k) size that are guaranteed to contain a prime, one has solved the strong conjecture.<br />
# 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 [[wikipedia:Pseudorandom_generators_for_polynomials|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.<br />
# If one can find a sequence of easily constructible, mutually coprime integers whose prime factors are contained in a sparse subset of the primes, this generates (with the aid of a factoring oracle) a sparse set of primes. So far the sparsest set of this type has come from factoring the Fermat numbers.<br />
<br />
== Negative results and other obstructions ==<br />
<br />
# 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>O(k^O(1))</math> smooth integer in any interval that can be searched in polynomial time. Indeed, there are heuristic arguments that suggest that even augmented with basic Fourier analysis and assuming RH, this method is unlikely to work, although they haven't yet been fully formalized.<br />
# 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.<br />
## In a similar spirit, one cannot hope to find non-smooth numbers in a short interval by analysing the iterated sumset of the log-primes and using average-case information about that set), because if one deletes all the primes arising from factors of that interval, one still captures most of the primes (and thus most of the average-case behaviour of the log-primes) while losing the information about that interval. <br />
# It is not possible to prove the conjecture purely by "soft" (i.e. relativisable) complexity theory methods which do not use any additional information on the primes rather than their density. Details are at [[Oracle counterexample to finding pseudoprimes]].<br />
<br />
== How could the conjecture be false? ==<br />
<br />
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:<br />
<br />
# 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>O(\log k)</math> that runs in time <math>k^{O(1)}</math>, are composite. [If the conjecture fails with factoring, then these numbers are furthermore <math>\exp(\varepsilon k)</math> smooth for any fixed <math>\varepsilon > 0</math>; if even the weak conjecture with factoring fails, they are <math>k^{O(1)}</math>-smooth.]<br />
# In fact, all constructible numbers are not only composite/smooth, but they sit inside intervals of length <math>k^{100}</math>, all of whose elements are composite/smooth. (One can replace 100 by any other fixed number.)<br />
## In particular, Cramer's conjecture fails; the gaps between adjacent k-digit primes exceeds <math>k^{100}</math> around every constructible number.<br />
# No pseudorandom number generators exist. In particular, this implies that one-way functions do not exist.<br />
# <math>P \neq NP</math>. More specifically, the decision problem "Does there exist a prime in a given interval?" is in [[The complexity class NP|NP]], but cannot lie in [[The complexity class P|P]] if the conjecture fails.<br />
<br />
== Relevant concepts ==<br />
<br />
Complexity theory concepts:<br />
<br />
# Complexity classes<br />
## [[The complexity class P|P]]<br />
## [[The complexity class NP|NP]]<br />
## [[The complexity class BPP|BPP]]<br />
## [[The complexity class promise-BPP|promise-BPP]]<br />
## [[The complexity class BQP|BQP]]<br />
## [[The complexity class DTIME|DTIME(f(n))]]<br />
# [[Pseudo-random generators (PRG)]]<br />
# [http://blog.computationalcomplexity.org/2006/07/full-derandomization.html Full derandomization]<br />
# [[wikipedia:One-way_function|one-way function]]<br />
# [http://cseweb.ucsd.edu/~russell/average.ps Impagliazzo's five worlds]: Algorithmica, Heuristica, Pessiland, Minicrypt, Cryptomania<br />
# [[Kolmogorov complexity]]<br />
# [[wikipedia:Oracle_machine|Oracles]]<br />
<br />
Number theory concepts:<br />
<br />
# [[Cramer's random model for the primes]]<br />
# [[Prime gaps]]<br />
# [[Generic prime]]<br />
# [[Smooth number]]<br />
# The [[W-trick]]<br />
# [[Sylvester's sequence]]<br />
# [[Siegel zero]]<br />
# [[wikipedia:Big_O_notation|Asymptotic notation]]<br />
# [[Fermat number]]<br />
# [[Pseudoprimes]]<br />
<br />
Other:<br />
<br />
# [[wikipedia:Expander_graph|Expander graphs]]<br />
<br />
Note: articles with external links should eventually be replaced by in-house pages that can provide information that is more dedicated to this project.<br />
<br />
== Relevant conjectures ==<br />
<br />
# [[The complexity class NP|P=NP]]<br />
# [[The complexity class BPP|P=BPP]]<br />
# [[The complexity class promise-BPP|P=promise-BPP]]<br />
# [[The complexity class BQP|P=BQP]]<br />
# [[Pseudo-random generators (PRG)|existence of PRG]]<br />
# [[wikipedia:One-way_function|existence of one-way functions]]<br />
# whether [[The complexity class DTIME|DTIME(2^n)]] has subexponential circuits<br />
# [[wikipedia:Riemann_hypothesis|The Riemann Hypothesis (RH)]]<br />
## [[wikipedia:Generalized_Riemann_hypothesis|The generalised Riemann Hypothesis (GRH)]]<br />
# the [[Hardy-Littlewood prime tuples conjecture]]<br />
# the [[ABC conjecture]]<br />
# [[Cramer's conjecture]]<br />
# [[Schinzel's hypothesis H]]<br />
# [[discrete logarithm|discrete log in P]]<br />
# [[factoring|factoring in P]]<br />
<br />
== Relevant results ==<br />
<br />
# [[Brun-Titchmarsh inequality]]<br />
# [[Erdos-Kac theorem]]<br />
# [[Bertrand's postulate]]<br />
# [[Friedlander-Iwaniec theorem]]<br />
# [[List of results implied by the Riemann Hypothesis|Conditional on the Riemann hypothesis]]<br />
<br />
== Relevant papers ==<br />
<br />
* [AMcC1994] L. Adelman, K. McCurley, [http://portal.acm.org/citation.cfm?id=749544 Open problems in number theoretic complexity, II], Lecture Notes In Computer Science; Vol. 877, Proceedings of the First International Symposium on Algorithmic Number Theory 291 - 322 (1994)<br />
* [AL1986] L. Adelman, H. Lenstra, [http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf Finding irreducible polynomials over finite fields], Proc. 18th Annual ACM Symp. on Theory of Computing (STOC), Berkeley, May 28–30, 350–355.<br />
* [B1990] E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), 355-380], <br />
* [BH1996] R. C. Baker and G. Harman, “The difference between consecutive primes,” Proc. Lond. Math. Soc., series 3, 72 (1996) 261–280. <br />
*[BH1998] R. C. Baker, G. Harmen, Shifted primes without large prime factors, Acta Arith. 83 (1998), no. 4, 331–361<br />
* [BHP2001] R. C. Baker, G. Harman and J. Pintz, The difference between consecutive primes, II, Proceedings of the London Mathematical Society 83, (2001), 532–562.<br />
* [BH1998] A. Balog, T. Wooley, “[http://www.austms.org.au/Publ/JAustMS/V64P2/abs/c30/ On strings of consecutive integers with no large prime factors]”, J. Austral. Math. Soc. Ser. A 64 (1998), no. 2, 266–276<br />
* [C2006] T. H. Chan, [http://arxiv.org/abs/math/0502199 Finding almost squares]. Acta Arith. 121 (2006), no. 3, 221--232.<br />
* [D1998] P. Dusart, [http://www.unilim.fr/laco/theses/1998/T1998_01.html Autour de la fonction qui compte le nombre de nombres premiers], 1998<br />
* [E1949] P. Erdős, [http://www.math-inst.hu/~p_erdos/1949-07.pdf On The Converse of Fermat's Theorem]<br />
* [EP1986] P. Erdős and C. Pomerance, On the number of false witnesses for a composite number, Math. Comp. 46 (1986), 259-279.<br />
* [FT????] M. Filaseta, O. Trifonov, [http://books.google.com/books?id=G02moOmuOX4C&pg=PA235&dq=squarefree+numbers#v=onepage&q=squarefree%20numbers&f=false On gaps between squarefree numbers], Analytic number theory: Proceedings of a conference in honor of Paul Bateman <br />
* [FT1992] M. Filaseta and O. Trifonov, On gaps between squarefree numbers. II, J. London Math. Soc. (2), 45 (1992), no. 2, 215-221. <br />
* [GW2002] O. Goldreich, A. Wigderson, [http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GW02/gw02.pdf Derandomization that is rarely wrong from short advice that is typically good]<br />
* [G1998] A. Granville, ABC allows us to count squarefrees, Internat. Math. Res. Notices (1998), no. 19, 991–1009.<br />
* [G1995] A. Granville, [http://www.dartmouth.edu/~chance/chance_news/for_chance_news/Riemann/cramer.pdf "Harald Cramér and the distribution of prime numbers"], Scandinavian Actuarial J. 1 (1995), 12—28. <br />
* [HB1984] D.R. Heath-Brown, The square sieve and consecutive square-free numbers, Math. Ann. 266 (1984), 251-259<br />
* [HB1995] D.R. Heath-Brown, The largest prime factor of integers in an interval, Science in China ???<br />
* [IW1997] 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.<br />
* [J2006] R. Jones, [http://arxiv.org/abs/math/0612415 The density of prime divisors in the arithmetic dynamics of quadratic polynomials]<br />
* [KLS2002] Křížek, Luca and Somer, On the convergence of series of reciprocals of primes related to the Fermat numbers, J. Number Theory 97(2002), 95–112<br />
* [L1979] H.W. Lenstra, [https://openaccess.leidenuniv.nl/bitstream/1887/3801/1/346_036.pdf Miller's Primality Test], Information Processing Letters, 1979<br />
* [L1996] H. Liu, Almost primes in short intervals. J. Number Theory 57 (1996), no. 2, 303--322.<br />
* [LW1999] H. Liu, J. Wu, Numbers with a large prime factor, Acta Arith. 89 (1999), no. 2, 163–187.<br />
* [M1994] U. Maurer, [http://eprints.kfupm.edu.sa/40655/ Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters], Journal of Cryptology 8 (1994), 123-155<br />
* [O1985] Odoni, On the prime divisors of the sequence <math>w_n+1 = 1+ w_1 \ldots w_n</math>. J. London Math. Soc. (2), 32(1):1–11, 1985. <br />
* [P????] F. Pappalardi, [http://www.mat.uniroma3.it/users/pappa/papers/allahabad2003.pdf A survey on k-freeness]<br />
* [P1981] C. Pomerance, [http://math.dartmouth.edu/~carlp/PDF/paper32.pdf On the distribution of pseudoprimes, Math. Comp. 37 (1981), 587-593.]<br />
* [P1982] C. Pomerance, [http://math.dartmouth.edu/~carlp/PDF/lower.pdf A new lower bound for the pseudoprime counting function, Illinois J. Math. 26 (1982), 4-9.]<br />
* [P1989] C. Pomerance, Two methods in elementary analytic number theory, Number theory and applications, R. A. Mollin, ed., Kluwer Academic Publishers, Dordrecht, 1989, pp. 135-161.<br />
<br />
* [S2006] K. Soundararajan, [http://arxiv.org/abs/math/0606408 The distribution of the primes] (survey)<br />
* [S2006b] K. Soundararajan, [http://arxiv.org/abs/math/0605696 Small gaps between prime numbers: The work of Goldston-Pintz-Yildirim]<br />
* [T2006] L. Trevisan, [http://arxiv.org/abs/cs.CC/0601100 Pseudorandomness and Combinatorial Constructions]<br />
<br />
Please help out by adding links or completing references, or adding further references to the list above!<br />
<br />
== External links ==<br />
<br />
# [http://qwiki.stanford.edu/wiki/Complexity_Zoo Complexity Zoo]<br />
# "[http://blog.computationalcomplexity.org/2009/08/finding-primes.html Finding Primes]", Lance Fortnow, August 4 2009</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Finding_primesFinding primes2009-08-20T00:23:50Z<p>Asdf: </p>
<hr />
<div>This is the main wiki page for the Polymath4 project "[http://en.wordpress.com/tag/finding-primes/ Finding primes]".<br />
<br />
The main aim of the project is to resolve the following conjecture:<br />
<br />
:'''(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.<br />
<br />
Since primality is known to be in [[The complexity class P|P]] by the [[wikipedia:AKS_primality_test|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.<br />
<br />
Contributions and corrections to this wiki page (and its subpages) are very welcome.<br />
<br />
== Threads ==<br />
<br />
# [http://polymathprojects.org/2009/07/27/proposal-deterministic-way-to-find-primes/ Proposal for the project and initial research thread] (Inactive)<br />
# [http://polymathprojects.org/2009/08/09/research-thread-ii-deterministic-way-to-find-primes/ Research thread II] (Inactive)<br />
# [http://polymathprojects.org/2009/08/13/research-thread-iii-determinstic-way-to-find-primes/ Research thread III] (Active)<br />
# [http://polymathprojects.org/2009/07/28/deterministic-way-to-find-primes-discussion-thread/ The current discussion thread] (Active)<br />
<br />
== Easier versions of the problem ==<br />
<br />
:'''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 [[Finding primes with O(k) random bits|one can do this with O(k) random bits]]; and if one can use just <math>O(\log k)</math> random bits, one is done by exhausting over the random bits.)<br />
<br />
One way to solve the semi-weak conjecture would be to find an "explorable" set of size <math>\exp(o(k))</math> of integers, a significant fraction (at least <math>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).<br />
<br />
:'''Weak conjecture''': There exists a deterministic algorithm, which, when given an integer k, is guaranteed to find a prime of at least <math>\omega(\log k)</math> digits in length in time polynomial in k, where <math>\omega(\log k)</math> grows faster than <math>\log k</math> as <math>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>\exp(o(k))</math>. Note that the semi-weak conjecture implies the weak conjecture).<br />
<br />
:'''Strong conjecture with factoring''': Same as the original conjecture, but assume that one has a ''factoring oracle'' will return the factors of any number given to it (as a stream of bits) in unit time. (This oracle can be given "for free" if factoring is in P, but we can also assume the existence of this oracle even if factoring is not in P.)<br />
<br />
:'''Semi-weak conjecture with factoring''': Same as the semi-weak conjecture, but with a factoring oracle.<br />
<br />
:'''Weak conjecture with factoring''': Same as the weak conjecture, but with a factoring oracle. (Note that there are deterministic sieve algorithms, such as the quadratic sieve, which are believed to run in subexponential time <math>\exp(o(k))</math>, so this oracle is in some sense available "for free" for this problem assuming this belief.)<br />
<br />
The weak conjecture with factoring is the easiest of the six, and so perhaps one should focus on that one first.<br />
<br />
It is also of interest to see whether the conjecture becomes easier to solve assuming that P=BPP or P=BQP.<br />
<br />
== Partial results ==<br />
<br />
# [[P=NP implies a deterministic algorithm to find primes]]<br />
# [[An efficient algorithm exists if Cramer's conjecture holds]]<br />
# [[Finding primes with O(k) random bits|k-digit primes can be found with high probability using O(k) random bits]]<br />
## If [[Pseudo-random generators (PRG)|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.<br />
# The function field analogue (i.e. finding degree k irreducible polynomials over a finite field) is known [AL1986]<br />
## The analogue over the rationals is even easier: Eisenstein's criterion provides plenty of irreducible polynomials of degree k, e.g. <math>x^k-2</math>.<br />
# Assuming a suitably quantitative version of [[Schinzel's hypothesis H]] (namely, the Bateman-Horn conjecture), the weak conjecture is true, as one can simply search over all k-digit numbers of the form <math>n^d-2</math> (say) for any fixed d to give an algorithm that works in time <math>O(10^{k/d})</math>. By randomly sampling such integers, one also establishes the semi-weak conjecture (assuming that one has the expected density for primes in hypothesis H).<br />
# It's easy to deterministically find large square-free numbers; just multiply lots of small primes together. However, it is not known how to test a number for square-freeness deterministically and quickly (unless one has a factoring oracle, in which case it is trivial).<br />
## However, it's not so obvious how to find large pairs <math>n,n+1</math> of consecutive square-free numbers, though such pairs must exist by counting arguments (the density of square-free numbers is <math>6/\pi^2 \approx 60\%</math>). This could be a good variant problem.<br />
### It is conjectured that every element of [[Sylvester's sequence]] is square-free. If so, this solves the above problem.<br />
# 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>k^A</math>, then increment A from 1 onward, until one gets a hit.<br />
<br />
Here are the current "world records" for the fastest way to deterministically (and provably) obtain a k-digit prime (ignoring errors of <math>\exp(o(k))</math> in the run time):<br />
<br />
# <math>O(10^k)</math>: The trivial algorithm of testing each of the k-digit numbers in turn until one gets a hit.<br />
# <math>O(10^k)^{3/4}</math>: Test the k-digit numbers of the form <math>a^2+b^4</math> for primality (the [[Friedlander-Iwaniec theorem]] guarantees a hit for k large enough).<br />
# <math>O(10^k)^{2/3}</math>: Test the k-digit numbers of the form <math>a^3+2b^3</math> for primality (a hit is guaranteed for large k by a result of Heath-Brown).<br />
# <math>O(10^{k})^{6/11+\epsilon} (\approx O(10^{k})^{.5454})</math>assuming factoring oracle: Factor each number in the interval <math>[x^{12/11},x^{12/11}+x^{6/11+\epsilon}]</math>, one will find a prime prime factor of order x by [HB1995]. <br />
# <math>O(10^k)^{0.525}</math>: Test the k-digit numbers from, say, <math>10^k</math> onwards until one gets a hit (here we use the [BHP2001] bound on [[prime gaps]]).<br />
# <math>O(10^k)^{1/2}</math> assuming RH: Test the k-digit numbers from, say, <math>10^k</math> onwards until one gets a hit (here we use the RH bound on [[prime gaps]]).<br />
<br />
Note that if one can get <math>O(10^k)^{\varepsilon}</math> for each fixed <math>\varepsilon > 0</math>, then one has established the weak conjecture.<br />
<br />
A slight variant of the problem: assuming a factoring oracle, given an algorithm that runs in k steps, how large a prime is the algorithm ''guaranteed'' to produce in the ''worst-case'' scenario? (Note that this is very different from what the algorithm is ''heuristically'' predicted to produce in the ''average-case'' scenario.)<br />
<br />
Here is a simple algorithm that produces a prime larger than about <math>k \log k</math> in k steps, based on Euclid's proof of the infinitude of primes:<br />
<br />
* Initialise <math>p_1=2</math>.<br />
* Once <math>p_1,\ldots,p_{k-1}</math> are computed, define <math>p_k</math> to be the largest prime factor of <math>p_1 \ldots p_{k-1}+1</math>.<br />
<br />
This generates k distinct primes; the prime number theorem tells us that the k^th prime has size about <math>k \log k</math>, so at least one of the primes produced here has size at least <math>k \log k</math>.<br />
<br />
If one instead works with [[Sylvester's sequence]] <math>a_k = a_1 \ldots a_{k-1}+1</math>, then it is known [O1985] that the number of primes less than n that can divide any one of the <math>a_k</math> is <math>O( n / \log n \log \log \log n )</math> rather than <math>O(n/\log n)</math> (the prime number theorem bound). If we then factor the first k elements of this sequence, we must get a prime of size at least <math>k \log k \log \log \log k</math> or so.<br />
<br />
One can do better still by working with the Fermat numbers, <math>F_n = 2^{2^n}+1</math>. It is known [KLS2002] that the number of primes dividing any of the <math>F_n</math> is <math>O(\sqrt{n}/\log n)</math>, so in particular if we factor the first k Fermat numbers, we get a prime almost of size <math>k^2</math>. In fact, it's a classical result of Euler that the prime divisors of <math>F_n</math> are all at least <math>2^{n+2}+1</math>, so we can obtain a large prime simply by factoring a Fermat number.<br />
<br />
Assuming RH, one can find a prime larger than <math>k^2</math> in about k steps by the method indicated earlier (start at <math>k^2</math> and increment until one hits a prime). Unconditionally, one gets a prime larger than <math>k^{1/0.525}</math> by this method. Currently this is the world record.<br />
<br />
== Variants of the problem ==<br />
<br />
# 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.<br />
<br />
=== Finding consecutive (or nearby) square-free integers ===<br />
<br />
:'''Toy problem''' Is there an efficient algorithm to find consecutive square-free integers n, n+1 of at least k digits in length assuming an oracle to determine whether a number is square free (a special case of the factoring oracle)? Or just square-free integers that are close together (e.g. polylog(n)).<br />
<br />
Note that finding one large square-free number is easy: just multiply lots of distinct small primes together. Also, as the density of square-free numbers is <math>6/\pi^2 \approx 0.6</math>, a counting argument shows that pairs of consecutive square-free numbers exist in abundance, and are thus easy to find probabilistically. The density can be increased to arbitrarily close to 1 using the [[W-trick]], so one could also ask for, say, long arithmetic progressions of square-free numbers also.<br />
<br />
If [[Sylvester's sequence]] is square-free, then this solves the problem.<br />
<br />
Testing a number for square-freeness is trivial with a factoring oracle. No unconditional polynomial-time deterministic algorithm for square-freeness seems to be known. (It is listed as an open problem in [http://portal.acm.org/citation.cfm?id=749544 this paper from 1994].)<br />
<br />
Unconditionally, there are asymptotics for the number of square-free numbers in [1,N] with an error term of <math>O(N^{1/2})</math>, which leads to a <math>O(10^k)^{1/2}</math> algorithm (just search an interval of this length for square-freeness). This is the current unconditional world record. Assuming RH, this can be improved to <math>O(10^k)^{17/54+\varepsilon}</math>. <br />
<br />
There is an asymptotic [HB1984] for the number of consecutive square free numbers with an error term of <math>O(N^{7/11})</math>, leading to a <math>O(10^k)^{7/11+\varepsilon}</math>, though this is inferior to the above bounds.<br />
<br />
It is known [FT1992] that the interval <math>[N, N+N^{1/5+\epsilon}]</math> contains at least one square-free number; Granville [G1998] improved this to <math>[N,N+N^{\varepsilon}]</math> assuming the [[ABC conjecture]]. If the density in such intervals can be made to exceed 50% (perhaps after first applying the [[W-trick]]) then we would have solved the weak version of this toy problem assuming ABC.<br />
<br />
=== Finding pseudoprimes ===<br />
<br />
:'''Problem:''' How quickly can one find a solution to the congruence <math>2^{n-1}=1 \hbox{ mod } n</math> with n at least k digits in length? (a pseudoprime)?<br />
<br />
It is conjectured that the largest gap between k-digit pseudoprimes is poly(k) (this is weaker than [[Cramer's conjecture]], and would imply a polynomial time solution to the above problem).<br />
<br />
It is conjectured that the number <math>\mathcal{P}_a(x)</math> of pseudoprimes to any base <math>a \neq \pm1</math> satisfies<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) = \log(x) - \log(x)\frac{\log\log\log(x)}{\log\log(x)}(1+o(1)).</math><br />
<br />
However, the best known bounds seem to be<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) \leq \log(x) - \frac{1}{2}\log(x)\frac{\log\log\log(x)}{\log\log(x)}(1+o(1)),</math><br />
<br />
and<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) \geq (\frac{\log(x)}{\log a})^{E/(E+1)-o(1)},</math><br />
<br />
where E is a constant which is conjectured to equal 1, but is only known to have value at least 1-1/(2\sqrt{e}). These results can be found in [P1981], [P1982], [P1989]. Better bounds are known to hold on average [EP1986].<br />
<br />
If n is a pseudoprime, then <math>2^n-1</math> is also a pseudoprime (because <math>2^n = 1 \hbox{ mod } 2^n - 1 </math>, and <math>2^n-2</math> is a multiple of n). This, technically, solves the problem, but can we find denser sets of pseudoprimes? What if we want <math>2^{n-1}=1 \hbox{ mod } n</math> and <math>3^{n-1} = 1 \hbox{ mod } n</math> simultaneously?<br />
<br />
=== Finding Almost Primes===<br />
<br />
An almost primes is a number that is the product of at most two primes (counted with multiplicity). <br />
<br />
:'''problem''' How fast can we deterministically write down a <math>k</math> digit almost prime?<br />
<br />
Clearly this is a relaxation of the prime problem, so we expect to get better results. In [L1996] it is shown that the interval <math>[x,x+x^{.436}]</math> contains an almost prime. This gives us a <math>O(10^{k})^{.436}</math> algorithm. Assuming a factoring oracle, the problems of deterministically finding a <math>k</math> digit almost prime and a <math>k</math> digit prime in polynomial time are equivalent. If we can find an almost prime in polynomial time we can factor it and get (a slightly smaller) prime. Conversely, if we can find a prime in polynomial time we can square it to find (a slightly larger) almost prime. Using our prime technology this should give a <math>O(10^{k})^{.262}</math> algorithm.<br />
<br />
== Observations and strategies ==<br />
<br />
# 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>N^\varepsilon</math>-smooth (or <math>\log^{O(1)} N</math> smooth, if one only wants to solve the weak conjecture with factoring). <br />
## 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>\{ Wn+1: 1 \leq n \leq k^{100} \}</math> (say) is <math>k^A</math>-smooth, then one has found a prime with at least <math>A \log k</math> digits in polynomial time. If one can make A arbitrarily large, one has solved the baby problem with factoring.<br />
## One way to proceed is to analyse [[iterated sumsets of log-primes]].<br />
## Another is to analyse [[signed sums of prime reciprocals]].<br />
## Probably the best known bound along these lines is given in [HB1995] and states that the interval <math>[x,x+x^{.5+\epsilon}]</math> contains an integer with a prime factor at least <math>x^{11/12 -\epsilon}</math>. This only leads to a <math>O(10^{k})^{.5455}</math> algorithm.<br />
# Another approach is to accurately compute the [[prime counting function]].<br />
# If one can find explicitly enumerable sets of k-digit numbers of size <math>O(10^{\varepsilon k})</math> for any fixed <math>\varepsilon > 0</math> that are guaranteed to contain a prime, then one has solved the weak conjecture. If instead one can find randomly samplable sets of k-digit numbers of size <math>O(10^{\varepsilon k})</math> that contain a large fraction (e.g. <math>\exp(-o(k))</math> of primes), one has solved the semi-weak conjecture. If one can find explicit sets of poly(k) size that are guaranteed to contain a prime, one has solved the strong conjecture.<br />
# 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 [[wikipedia:Pseudorandom_generators_for_polynomials|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.<br />
# If one can find a sequence of easily constructible, mutually coprime integers whose prime factors are contained in a sparse subset of the primes, this generates (with the aid of a factoring oracle) a sparse set of primes. So far the sparsest set of this type has come from factoring the Fermat numbers.<br />
<br />
== Negative results and other obstructions ==<br />
<br />
# 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>O(k^O(1))</math> smooth integer in any interval that can be searched in polynomial time. Indeed, there are heuristic arguments that suggest that even augmented with basic Fourier analysis and assuming RH, this method is unlikely to work, although they haven't yet been fully formalized.<br />
# 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.<br />
## In a similar spirit, one cannot hope to find non-smooth numbers in a short interval by analysing the iterated sumset of the log-primes and using average-case information about that set), because if one deletes all the primes arising from factors of that interval, one still captures most of the primes (and thus most of the average-case behaviour of the log-primes) while losing the information about that interval. <br />
# It is not possible to prove the conjecture purely by "soft" (i.e. relativisable) complexity theory methods which do not use any additional information on the primes rather than their density. Details are at [[Oracle counterexample to finding pseudoprimes]].<br />
<br />
== How could the conjecture be false? ==<br />
<br />
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:<br />
<br />
# 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>O(\log k)</math> that runs in time <math>k^{O(1)}</math>, are composite. [If the conjecture fails with factoring, then these numbers are furthermore <math>\exp(\varepsilon k)</math> smooth for any fixed <math>\varepsilon > 0</math>; if even the weak conjecture with factoring fails, they are <math>k^{O(1)}</math>-smooth.]<br />
# In fact, all constructible numbers are not only composite/smooth, but they sit inside intervals of length <math>k^{100}</math>, all of whose elements are composite/smooth. (One can replace 100 by any other fixed number.)<br />
## In particular, Cramer's conjecture fails; the gaps between adjacent k-digit primes exceeds <math>k^{100}</math> around every constructible number.<br />
# No pseudorandom number generators exist. In particular, this implies that one-way functions do not exist.<br />
# <math>P \neq NP</math>. More specifically, the decision problem "Does there exist a prime in a given interval?" is in [[The complexity class NP|NP]], but cannot lie in [[The complexity class P|P]] if the conjecture fails.<br />
<br />
== Relevant concepts ==<br />
<br />
Complexity theory concepts:<br />
<br />
# Complexity classes<br />
## [[The complexity class P|P]]<br />
## [[The complexity class NP|NP]]<br />
## [[The complexity class BPP|BPP]]<br />
## [[The complexity class promise-BPP|promise-BPP]]<br />
## [[The complexity class BQP|BQP]]<br />
## [[The complexity class DTIME|DTIME(f(n))]]<br />
# [[Pseudo-random generators (PRG)]]<br />
# [http://blog.computationalcomplexity.org/2006/07/full-derandomization.html Full derandomization]<br />
# [[wikipedia:One-way_function|one-way function]]<br />
# [[Impagliazzo's five worlds]]: Algorithmica, Heuristica, Pessiland, Minicrypt, Cryptomania<br />
# [[Kolmogorov complexity]]<br />
# [[wikipedia:Oracle_machine|Oracles]]<br />
<br />
Number theory concepts:<br />
<br />
# [[Cramer's random model for the primes]]<br />
# [[Prime gaps]]<br />
# [[Generic prime]]<br />
# [[Smooth number]]<br />
# The [[W-trick]]<br />
# [[Sylvester's sequence]]<br />
# [[Siegel zero]]<br />
# [[wikipedia:Big_O_notation|Asymptotic notation]]<br />
# [[Fermat number]]<br />
# [[Pseudoprimes]]<br />
<br />
Other:<br />
<br />
# [[wikipedia:Expander_graph|Expander graphs]]<br />
<br />
Note: articles with external links should eventually be replaced by in-house pages that can provide information that is more dedicated to this project.<br />
<br />
== Relevant conjectures ==<br />
<br />
# [[The complexity class NP|P=NP]]<br />
# [[The complexity class BPP|P=BPP]]<br />
# [[The complexity class promise-BPP|P=promise-BPP]]<br />
# [[The complexity class BQP|P=BQP]]<br />
# [[Pseudo-random generators (PRG)|existence of PRG]]<br />
# [[wikipedia:One-way_function|existence of one-way functions]]<br />
# whether [[The complexity class DTIME|DTIME(2^n)]] has subexponential circuits<br />
# [[wikipedia:Riemann_hypothesis|The Riemann Hypothesis (RH)]]<br />
## [[wikipedia:Generalized_Riemann_hypothesis|The generalised Riemann Hypothesis (GRH)]]<br />
# the [[Hardy-Littlewood prime tuples conjecture]]<br />
# the [[ABC conjecture]]<br />
# [[Cramer's conjecture]]<br />
# [[Schinzel's hypothesis H]]<br />
# [[discrete logarithm|discrete log in P]]<br />
# [[factoring|factoring in P]]<br />
<br />
== Relevant results ==<br />
<br />
# [[Brun-Titchmarsh inequality]]<br />
# [[Erdos-Kac theorem]]<br />
# [[Bertrand's postulate]]<br />
# [[Friedlander-Iwaniec theorem]]<br />
# [[List of results implied by the Riemann Hypothesis|Conditional on the Riemann hypothesis]]<br />
<br />
== Relevant papers ==<br />
<br />
* [AMcC1994] L. Adelman, K. McCurley, [http://portal.acm.org/citation.cfm?id=749544 Open problems in number theoretic complexity, II], Lecture Notes In Computer Science; Vol. 877, Proceedings of the First International Symposium on Algorithmic Number Theory 291 - 322 (1994)<br />
* [AL1986] L. Adelman, H. Lenstra, [http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf Finding irreducible polynomials over finite fields], Proc. 18th Annual ACM Symp. on Theory of Computing (STOC), Berkeley, May 28–30, 350–355.<br />
* [B1990] E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), 355-380], <br />
* [BH1996] R. C. Baker and G. Harman, “The difference between consecutive primes,” Proc. Lond. Math. Soc., series 3, 72 (1996) 261–280. <br />
*[BH1998] R. C. Baker, G. Harmen, Shifted primes without large prime factors, Acta Arith. 83 (1998), no. 4, 331–361<br />
* [BHP2001] R. C. Baker, G. Harman and J. Pintz, The difference between consecutive primes, II, Proceedings of the London Mathematical Society 83, (2001), 532–562.<br />
* [BH1998] A. Balog, T. Wooley, “[http://www.austms.org.au/Publ/JAustMS/V64P2/abs/c30/ On strings of consecutive integers with no large prime factors]”, J. Austral. Math. Soc. Ser. A 64 (1998), no. 2, 266–276<br />
* [C2006] T. H. Chan, [http://arxiv.org/abs/math/0502199 Finding almost squares]. Acta Arith. 121 (2006), no. 3, 221--232.<br />
* [D1998] P. Dusart, [http://www.unilim.fr/laco/theses/1998/T1998_01.html Autour de la fonction qui compte le nombre de nombres premiers], 1998<br />
* [E1949] P. Erdős, [http://www.math-inst.hu/~p_erdos/1949-07.pdf On The Converse of Fermat's Theorem]<br />
* [EP1986] P. Erdős and C. Pomerance, On the number of false witnesses for a composite number, Math. Comp. 46 (1986), 259-279.<br />
* [FT????] M. Filaseta, O. Trifonov, [http://books.google.com/books?id=G02moOmuOX4C&pg=PA235&dq=squarefree+numbers#v=onepage&q=squarefree%20numbers&f=false On gaps between squarefree numbers], Analytic number theory: Proceedings of a conference in honor of Paul Bateman <br />
* [FT1992] M. Filaseta and O. Trifonov, On gaps between squarefree numbers. II, J. London Math. Soc. (2), 45 (1992), no. 2, 215-221. <br />
* [GW2002] O. Goldreich, A. Wigderson, [http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GW02/gw02.pdf Derandomization that is rarely wrong from short advice that is typically good]<br />
* [G1998] A. Granville, ABC allows us to count squarefrees, Internat. Math. Res. Notices (1998), no. 19, 991–1009.<br />
* [G1995] A. Granville, [http://www.dartmouth.edu/~chance/chance_news/for_chance_news/Riemann/cramer.pdf "Harald Cramér and the distribution of prime numbers"], Scandinavian Actuarial J. 1 (1995), 12—28. <br />
* [HB1984] D.R. Heath-Brown, The square sieve and consecutive square-free numbers, Math. Ann. 266 (1984), 251-259<br />
* [HB1995] D.R. Heath-Brown, The largest prime factor of integers in an interval, Science in China ???<br />
* [IW1997] 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.<br />
* [J2006] R. Jones, [http://arxiv.org/abs/math/0612415 The density of prime divisors in the arithmetic dynamics of quadratic polynomials]<br />
* [KLS2002] Křížek, Luca and Somer, On the convergence of series of reciprocals of primes related to the Fermat numbers, J. Number Theory 97(2002), 95–112<br />
* [L1979] H.W. Lenstra, [https://openaccess.leidenuniv.nl/bitstream/1887/3801/1/346_036.pdf Miller's Primality Test], Information Processing Letters, 1979<br />
* [L1996] H. Liu, Almost primes in short intervals. J. Number Theory 57 (1996), no. 2, 303--322.<br />
* [LW1999] H. Liu, J. Wu, Numbers with a large prime factor, Acta Arith. 89 (1999), no. 2, 163–187.<br />
* [M1994] U. Maurer, [http://eprints.kfupm.edu.sa/40655/ Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters], Journal of Cryptology 8 (1994), 123-155<br />
* [O1985] Odoni, On the prime divisors of the sequence <math>w_n+1 = 1+ w_1 \ldots w_n</math>. J. London Math. Soc. (2), 32(1):1–11, 1985. <br />
* [P????] F. Pappalardi, [http://www.mat.uniroma3.it/users/pappa/papers/allahabad2003.pdf A survey on k-freeness]<br />
* [P1981] C. Pomerance, [http://math.dartmouth.edu/~carlp/PDF/paper32.pdf On the distribution of pseudoprimes, Math. Comp. 37 (1981), 587-593.]<br />
* [P1982] C. Pomerance, [http://math.dartmouth.edu/~carlp/PDF/lower.pdf A new lower bound for the pseudoprime counting function, Illinois J. Math. 26 (1982), 4-9.]<br />
* [P1989] C. Pomerance, Two methods in elementary analytic number theory, Number theory and applications, R. A. Mollin, ed., Kluwer Academic Publishers, Dordrecht, 1989, pp. 135-161.<br />
<br />
* [S2006] K. Soundararajan, [http://arxiv.org/abs/math/0606408 The distribution of the primes] (survey)<br />
* [S2006b] K. Soundararajan, [http://arxiv.org/abs/math/0605696 Small gaps between prime numbers: The work of Goldston-Pintz-Yildirim]<br />
* [T2006] L. Trevisan, [http://arxiv.org/abs/cs.CC/0601100 Pseudorandomness and Combinatorial Constructions]<br />
<br />
Please help out by adding links or completing references, or adding further references to the list above!<br />
<br />
== External links ==<br />
<br />
# [http://qwiki.stanford.edu/wiki/Complexity_Zoo Complexity Zoo]<br />
# "[http://blog.computationalcomplexity.org/2009/08/finding-primes.html Finding Primes]", Lance Fortnow, August 4 2009</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=ABC_conjectureABC conjecture2009-08-20T00:21:32Z<p>Asdf: </p>
<hr />
<div>The '''abc conjecture''' asserts, roughly speaking, that if a+b=c and a,b,c are coprime, then a,b,c cannot all be too smooth; in particular, the product of all the primes dividing a, b, or c has to exceed <math>c^{1-\varepsilon}</math> for any fixed <math>\varepsilon > 0</math> (if a,b,c are smooth).<br />
<br />
This shows for instance that <math>(1-\varepsilon) \log N / 3</math>-smooth a,b,c of size N which are coprime cannot sum to form a+b=c. This unfortunately seems to be too weak to be of much use for the [[finding primes]] project.<br />
<br />
* [[wikipedia:Abc_conjecture|Wikipedia page for the ABC conjecture]]</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Finding_primesFinding primes2009-08-20T00:14:52Z<p>Asdf: link to aks</p>
<hr />
<div>This is the main wiki page for the Polymath4 project "[http://en.wordpress.com/tag/finding-primes/ Finding primes]".<br />
<br />
The main aim of the project is to resolve the following conjecture:<br />
<br />
:'''(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.<br />
<br />
Since primality is known to be in [[The complexity class P|P]] by the [[wikipedia:AKS_primality_test|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.<br />
<br />
Contributions and corrections to this wiki page (and its subpages) are very welcome.<br />
<br />
== Threads ==<br />
<br />
# [http://polymathprojects.org/2009/07/27/proposal-deterministic-way-to-find-primes/ Proposal for the project and initial research thread] (Inactive)<br />
# [http://polymathprojects.org/2009/08/09/research-thread-ii-deterministic-way-to-find-primes/ Research thread II] (Inactive)<br />
# [http://polymathprojects.org/2009/08/13/research-thread-iii-determinstic-way-to-find-primes/ Research thread III] (Active)<br />
# [http://polymathprojects.org/2009/07/28/deterministic-way-to-find-primes-discussion-thread/ The current discussion thread] (Active)<br />
<br />
== Easier versions of the problem ==<br />
<br />
:'''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 [[Finding primes with O(k) random bits|one can do this with O(k) random bits]]; and if one can use just <math>O(\log k)</math> random bits, one is done by exhausting over the random bits.)<br />
<br />
One way to solve the semi-weak conjecture would be to find an "explorable" set of size <math>\exp(o(k))</math> of integers, a significant fraction (at least <math>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).<br />
<br />
:'''Weak conjecture''': There exists a deterministic algorithm, which, when given an integer k, is guaranteed to find a prime of at least <math>\omega(\log k)</math> digits in length in time polynomial in k, where <math>\omega(\log k)</math> grows faster than <math>\log k</math> as <math>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>\exp(o(k))</math>. Note that the semi-weak conjecture implies the weak conjecture).<br />
<br />
:'''Strong conjecture with factoring''': Same as the original conjecture, but assume that one has a ''factoring oracle'' will return the factors of any number given to it (as a stream of bits) in unit time. (This oracle can be given "for free" if factoring is in P, but we can also assume the existence of this oracle even if factoring is not in P.)<br />
<br />
:'''Semi-weak conjecture with factoring''': Same as the semi-weak conjecture, but with a factoring oracle.<br />
<br />
:'''Weak conjecture with factoring''': Same as the weak conjecture, but with a factoring oracle. (Note that there are deterministic sieve algorithms, such as the quadratic sieve, which are believed to run in subexponential time <math>\exp(o(k))</math>, so this oracle is in some sense available "for free" for this problem assuming this belief.)<br />
<br />
The weak conjecture with factoring is the easiest of the six, and so perhaps one should focus on that one first.<br />
<br />
It is also of interest to see whether the conjecture becomes easier to solve assuming that P=BPP or P=BQP.<br />
<br />
== Partial results ==<br />
<br />
# [[P=NP implies a deterministic algorithm to find primes]]<br />
# [[An efficient algorithm exists if Cramer's conjecture holds]]<br />
# [[Finding primes with O(k) random bits|k-digit primes can be found with high probability using O(k) random bits]]<br />
## If [[Pseudo-random generators (PRG)|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.<br />
# The function field analogue (i.e. finding degree k irreducible polynomials over a finite field) is known [AL1986]<br />
## The analogue over the rationals is even easier: Eisenstein's criterion provides plenty of irreducible polynomials of degree k, e.g. <math>x^k-2</math>.<br />
# Assuming a suitably quantitative version of [[Schinzel's hypothesis H]] (namely, the Bateman-Horn conjecture), the weak conjecture is true, as one can simply search over all k-digit numbers of the form <math>n^d-2</math> (say) for any fixed d to give an algorithm that works in time <math>O(10^{k/d})</math>. By randomly sampling such integers, one also establishes the semi-weak conjecture (assuming that one has the expected density for primes in hypothesis H).<br />
# It's easy to deterministically find large square-free numbers; just multiply lots of small primes together. However, it is not known how to test a number for square-freeness deterministically and quickly (unless one has a factoring oracle, in which case it is trivial).<br />
## However, it's not so obvious how to find large pairs <math>n,n+1</math> of consecutive square-free numbers, though such pairs must exist by counting arguments (the density of square-free numbers is <math>6/\pi^2 \approx 60\%</math>). This could be a good variant problem.<br />
### It is conjectured that every element of [[Sylvester's sequence]] is square-free. If so, this solves the above problem.<br />
# 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>k^A</math>, then increment A from 1 onward, until one gets a hit.<br />
<br />
Here are the current "world records" for the fastest way to deterministically (and provably) obtain a k-digit prime (ignoring errors of <math>\exp(o(k))</math> in the run time):<br />
<br />
# <math>O(10^k)</math>: The trivial algorithm of testing each of the k-digit numbers in turn until one gets a hit.<br />
# <math>O(10^k)^{3/4}</math>: Test the k-digit numbers of the form <math>a^2+b^4</math> for primality (the [[Friedlander-Iwaniec theorem]] guarantees a hit for k large enough).<br />
# <math>O(10^k)^{2/3}</math>: Test the k-digit numbers of the form <math>a^3+2b^3</math> for primality (a hit is guaranteed for large k by a result of Heath-Brown).<br />
# <math>O(10^{k})^{6/11+\epsilon} (\approx O(10^{k})^{.5454})</math>assuming factoring oracle: Factor each number in the interval <math>[x^{12/11},x^{12/11}+x^{6/11+\epsilon}]</math>, one will find a prime prime factor of order x by [HB1995]. <br />
# <math>O(10^k)^{0.525}</math>: Test the k-digit numbers from, say, <math>10^k</math> onwards until one gets a hit (here we use the [BHP2001] bound on [[prime gaps]]).<br />
# <math>O(10^k)^{1/2}</math> assuming RH: Test the k-digit numbers from, say, <math>10^k</math> onwards until one gets a hit (here we use the RH bound on [[prime gaps]]).<br />
<br />
Note that if one can get <math>O(10^k)^{\varepsilon}</math> for each fixed <math>\varepsilon > 0</math>, then one has established the weak conjecture.<br />
<br />
A slight variant of the problem: assuming a factoring oracle, given an algorithm that runs in k steps, how large a prime is the algorithm ''guaranteed'' to produce in the ''worst-case'' scenario? (Note that this is very different from what the algorithm is ''heuristically'' predicted to produce in the ''average-case'' scenario.)<br />
<br />
Here is a simple algorithm that produces a prime larger than about <math>k \log k</math> in k steps, based on Euclid's proof of the infinitude of primes:<br />
<br />
* Initialise <math>p_1=2</math>.<br />
* Once <math>p_1,\ldots,p_{k-1}</math> are computed, define <math>p_k</math> to be the largest prime factor of <math>p_1 \ldots p_{k-1}+1</math>.<br />
<br />
This generates k distinct primes; the prime number theorem tells us that the k^th prime has size about <math>k \log k</math>, so at least one of the primes produced here has size at least <math>k \log k</math>.<br />
<br />
If one instead works with [[Sylvester's sequence]] <math>a_k = a_1 \ldots a_{k-1}+1</math>, then it is known [O1985] that the number of primes less than n that can divide any one of the <math>a_k</math> is <math>O( n / \log n \log \log \log n )</math> rather than <math>O(n/\log n)</math> (the prime number theorem bound). If we then factor the first k elements of this sequence, we must get a prime of size at least <math>k \log k \log \log \log k</math> or so.<br />
<br />
One can do better still by working with the Fermat numbers, <math>F_n = 2^{2^n}+1</math>. It is known [KLS2002] that the number of primes dividing any of the <math>F_n</math> is <math>O(\sqrt{n}/\log n)</math>, so in particular if we factor the first k Fermat numbers, we get a prime almost of size <math>k^2</math>. In fact, it's a classical result of Euler that the prime divisors of <math>F_n</math> are all at least <math>2^{n+2}+1</math>, so we can obtain a large prime simply by factoring a Fermat number.<br />
<br />
Assuming RH, one can find a prime larger than <math>k^2</math> in about k steps by the method indicated earlier (start at <math>k^2</math> and increment until one hits a prime). Unconditionally, one gets a prime larger than <math>k^{1/0.525}</math> by this method. Currently this is the world record.<br />
<br />
== Variants of the problem ==<br />
<br />
# 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.<br />
<br />
=== Finding consecutive (or nearby) square-free integers ===<br />
<br />
:'''Toy problem''' Is there an efficient algorithm to find consecutive square-free integers n, n+1 of at least k digits in length assuming an oracle to determine whether a number is square free (a special case of the factoring oracle)? Or just square-free integers that are close together (e.g. polylog(n)).<br />
<br />
Note that finding one large square-free number is easy: just multiply lots of distinct small primes together. Also, as the density of square-free numbers is <math>6/\pi^2 \approx 0.6</math>, a counting argument shows that pairs of consecutive square-free numbers exist in abundance, and are thus easy to find probabilistically. The density can be increased to arbitrarily close to 1 using the [[W-trick]], so one could also ask for, say, long arithmetic progressions of square-free numbers also.<br />
<br />
If [[Sylvester's sequence]] is square-free, then this solves the problem.<br />
<br />
Testing a number for square-freeness is trivial with a factoring oracle. No unconditional polynomial-time deterministic algorithm for square-freeness seems to be known. (It is listed as an open problem in [http://portal.acm.org/citation.cfm?id=749544 this paper from 1994].)<br />
<br />
Unconditionally, there are asymptotics for the number of square-free numbers in [1,N] with an error term of <math>O(N^{1/2})</math>, which leads to a <math>O(10^k)^{1/2}</math> algorithm (just search an interval of this length for square-freeness). This is the current unconditional world record. Assuming RH, this can be improved to <math>O(10^k)^{17/54+\varepsilon}</math>. <br />
<br />
There is an asymptotic [HB1984] for the number of consecutive square free numbers with an error term of <math>O(N^{7/11})</math>, leading to a <math>O(10^k)^{7/11+\varepsilon}</math>, though this is inferior to the above bounds.<br />
<br />
It is known [FT1992] that the interval <math>[N, N+N^{1/5+\epsilon}]</math> contains at least one square-free number; Granville [G1998] improved this to <math>[N,N+N^{\varepsilon}]</math> assuming the [[ABC conjecture]]. If the density in such intervals can be made to exceed 50% (perhaps after first applying the [[W-trick]]) then we would have solved the weak version of this toy problem assuming ABC.<br />
<br />
=== Finding pseudoprimes ===<br />
<br />
:'''Problem:''' How quickly can one find a solution to the congruence <math>2^{n-1}=1 \hbox{ mod } n</math> with n at least k digits in length? (a pseudoprime)?<br />
<br />
It is conjectured that the largest gap between k-digit pseudoprimes is poly(k) (this is weaker than [[Cramer's conjecture]], and would imply a polynomial time solution to the above problem).<br />
<br />
It is conjectured that the number <math>\mathcal{P}_a(x)</math> of pseudoprimes to any base <math>a \neq \pm1</math> satisfies<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) = \log(x) - \log(x)\frac{\log\log\log(x)}{\log\log(x)}(1+o(1)).</math><br />
<br />
However, the best known bounds seem to be<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) \leq \log(x) - \frac{1}{2}\log(x)\frac{\log\log\log(x)}{\log\log(x)}(1+o(1)),</math><br />
<br />
and<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) \geq (\frac{\log(x)}{\log a})^{E/(E+1)-o(1)},</math><br />
<br />
where E is a constant which is conjectured to equal 1, but is only known to have value at least 1-1/(2\sqrt{e}). These results can be found in [P1981], [P1982], [P1989]. Better bounds are known to hold on average [EP1986].<br />
<br />
If n is a pseudoprime, then <math>2^n-1</math> is also a pseudoprime (because <math>2^n = 1 \hbox{ mod } 2^n - 1 </math>, and <math>2^n-2</math> is a multiple of n). This, technically, solves the problem, but can we find denser sets of pseudoprimes? What if we want <math>2^{n-1}=1 \hbox{ mod } n</math> and <math>3^{n-1} = 1 \hbox{ mod } n</math> simultaneously?<br />
<br />
=== Finding Almost Primes===<br />
<br />
An almost primes is a number that is the product of at most two primes (counted with multiplicity). <br />
<br />
:'''problem''' How fast can we deterministically write down a <math>k</math> digit almost prime?<br />
<br />
Clearly this is a relaxation of the prime problem, so we expect to get better results. In [L1996] it is shown that the interval <math>[x,x+x^{.436}]</math> contains an almost prime. This gives us a <math>O(10^{k})^{.436}</math> algorithm. Assuming a factoring oracle, the problems of deterministically finding a <math>k</math> digit almost prime and a <math>k</math> digit prime in polynomial time are equivalent. If we can find an almost prime in polynomial time we can factor it and get (a slightly smaller) prime. Conversely, if we can find a prime in polynomial time we can square it to find (a slightly larger) almost prime. Using our prime technology this should give a <math>O(10^{k})^{.262}</math> algorithm.<br />
<br />
== Observations and strategies ==<br />
<br />
# 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>N^\varepsilon</math>-smooth (or <math>\log^{O(1)} N</math> smooth, if one only wants to solve the weak conjecture with factoring). <br />
## 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>\{ Wn+1: 1 \leq n \leq k^{100} \}</math> (say) is <math>k^A</math>-smooth, then one has found a prime with at least <math>A \log k</math> digits in polynomial time. If one can make A arbitrarily large, one has solved the baby problem with factoring.<br />
## One way to proceed is to analyse [[iterated sumsets of log-primes]].<br />
## Another is to analyse [[signed sums of prime reciprocals]].<br />
## Probably the best known bound along these lines is given in [HB1995] and states that the interval <math>[x,x+x^{.5+\epsilon}]</math> contains an integer with a prime factor at least <math>x^{11/12 -\epsilon}</math>. This only leads to a <math>O(10^{k})^{.5455}</math> algorithm.<br />
# Another approach is to accurately compute the [[prime counting function]].<br />
# If one can find explicitly enumerable sets of k-digit numbers of size <math>O(10^{\varepsilon k})</math> for any fixed <math>\varepsilon > 0</math> that are guaranteed to contain a prime, then one has solved the weak conjecture. If instead one can find randomly samplable sets of k-digit numbers of size <math>O(10^{\varepsilon k})</math> that contain a large fraction (e.g. <math>\exp(-o(k))</math> of primes), one has solved the semi-weak conjecture. If one can find explicit sets of poly(k) size that are guaranteed to contain a prime, one has solved the strong conjecture.<br />
# 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 [[wikipedia:Pseudorandom_generators_for_polynomials|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.<br />
# If one can find a sequence of easily constructible, mutually coprime integers whose prime factors are contained in a sparse subset of the primes, this generates (with the aid of a factoring oracle) a sparse set of primes. So far the sparsest set of this type has come from factoring the Fermat numbers.<br />
<br />
== Negative results and other obstructions ==<br />
<br />
# 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>O(k^O(1))</math> smooth integer in any interval that can be searched in polynomial time. Indeed, there are heuristic arguments that suggest that even augmented with basic Fourier analysis and assuming RH, this method is unlikely to work, although they haven't yet been fully formalized.<br />
# 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.<br />
## In a similar spirit, one cannot hope to find non-smooth numbers in a short interval by analysing the iterated sumset of the log-primes and using average-case information about that set), because if one deletes all the primes arising from factors of that interval, one still captures most of the primes (and thus most of the average-case behaviour of the log-primes) while losing the information about that interval. <br />
# It is not possible to prove the conjecture purely by "soft" (i.e. relativisable) complexity theory methods which do not use any additional information on the primes rather than their density. Details are at [[Oracle counterexample to finding pseudoprimes]].<br />
<br />
== How could the conjecture be false? ==<br />
<br />
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:<br />
<br />
# 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>O(\log k)</math> that runs in time <math>k^{O(1)}</math>, are composite. [If the conjecture fails with factoring, then these numbers are furthermore <math>\exp(\varepsilon k)</math> smooth for any fixed <math>\varepsilon > 0</math>; if even the weak conjecture with factoring fails, they are <math>k^{O(1)}</math>-smooth.]<br />
# In fact, all constructible numbers are not only composite/smooth, but they sit inside intervals of length <math>k^{100}</math>, all of whose elements are composite/smooth. (One can replace 100 by any other fixed number.)<br />
## In particular, Cramer's conjecture fails; the gaps between adjacent k-digit primes exceeds <math>k^{100}</math> around every constructible number.<br />
# No pseudorandom number generators exist. In particular, this implies that one-way functions do not exist.<br />
# <math>P \neq NP</math>. More specifically, the decision problem "Does there exist a prime in a given interval?" is in [[The complexity class NP|NP]], but cannot lie in [[The complexity class P|P]] if the conjecture fails.<br />
<br />
== Relevant concepts ==<br />
<br />
Complexity theory concepts:<br />
<br />
# Complexity classes<br />
## [[The complexity class P|P]]<br />
## [[The complexity class NP|NP]]<br />
## [[The complexity class BPP|BPP]]<br />
## [[The complexity class promise-BPP|promise-BPP]]<br />
## [[The complexity class BQP|BQP]]<br />
## [[The complexity class DTIME|DTIME(f(n))]]<br />
# [[Pseudo-random generators (PRG)]]<br />
# [http://blog.computationalcomplexity.org/2006/07/full-derandomization.html Full derandomization]<br />
# [[wikipedia:One-way_function|one-way function]]<br />
# [[Impagliazzo's five worlds]]: Algorithmica, Heuristica, Pessiland, Minicrypt, Cryptomania<br />
# [[Kolmogorov complexity]]<br />
# [[wikipedia:Oracle_machine|Oracles]<br />
<br />
Number theory concepts:<br />
<br />
# [[Cramer's random model for the primes]]<br />
# [[Prime gaps]]<br />
# [[Generic prime]]<br />
# [[Smooth number]]<br />
# The [[W-trick]]<br />
# [[Sylvester's sequence]]<br />
# [[Siegel zero]]<br />
# [[wikipedia:Big_O_notation|Asymptotic notation]]<br />
# [[Fermat number]]<br />
# [[Pseudoprimes]]<br />
<br />
Other:<br />
<br />
# [[wikipedia:Expander_graph|Expander graphs]]<br />
<br />
Note: articles with external links should eventually be replaced by in-house pages that can provide information that is more dedicated to this project.<br />
<br />
== Relevant conjectures ==<br />
<br />
# [[The complexity class NP|P=NP]]<br />
# [[The complexity class BPP|P=BPP]]<br />
# [[The complexity class promise-BPP|P=promise-BPP]]<br />
# [[The complexity class BQP|P=BQP]]<br />
# [[Pseudo-random generators (PRG)|existence of PRG]]<br />
# [[wikipedia:One-way_function|existence of one-way functions]]<br />
# whether [[The complexity class DTIME|DTIME(2^n)]] has subexponential circuits<br />
# [[wikipedia:Riemann_hypothesis|The Riemann Hypothesis (RH)]]<br />
## [[wikipedia:Generalized_Riemann_hypothesis|The generalised Riemann Hypothesis (GRH)]]<br />
# the [[Hardy-Littlewood prime tuples conjecture]]<br />
# the [[ABC conjecture]]<br />
# [[Cramer's conjecture]]<br />
# [[Schinzel's hypothesis H]]<br />
# [[discrete logarithm|discrete log in P]]<br />
# [[factoring|factoring in P]]<br />
<br />
== Relevant results ==<br />
<br />
# [[Brun-Titchmarsh inequality]]<br />
# [[Erdos-Kac theorem]]<br />
# [[Bertrand's postulate]]<br />
# [[Friedlander-Iwaniec theorem]]<br />
# [[List of results implied by the Riemann Hypothesis|Conditional on the Riemann hypothesis]]<br />
<br />
== Relevant papers ==<br />
<br />
* [AMcC1994] L. Adelman, K. McCurley, [http://portal.acm.org/citation.cfm?id=749544 Open problems in number theoretic complexity, II], Lecture Notes In Computer Science; Vol. 877, Proceedings of the First International Symposium on Algorithmic Number Theory 291 - 322 (1994)<br />
* [AL1986] L. Adelman, H. Lenstra, [http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf Finding irreducible polynomials over finite fields], Proc. 18th Annual ACM Symp. on Theory of Computing (STOC), Berkeley, May 28–30, 350–355.<br />
* [B1990] E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), 355-380], <br />
* [BH1996] R. C. Baker and G. Harman, “The difference between consecutive primes,” Proc. Lond. Math. Soc., series 3, 72 (1996) 261–280. <br />
*[BH1998] R. C. Baker, G. Harmen, Shifted primes without large prime factors, Acta Arith. 83 (1998), no. 4, 331–361<br />
* [BHP2001] R. C. Baker, G. Harman and J. Pintz, The difference between consecutive primes, II, Proceedings of the London Mathematical Society 83, (2001), 532–562.<br />
* [BH1998] A. Balog, T. Wooley, “[http://www.austms.org.au/Publ/JAustMS/V64P2/abs/c30/ On strings of consecutive integers with no large prime factors]”, J. Austral. Math. Soc. Ser. A 64 (1998), no. 2, 266–276<br />
* [C2006] T. H. Chan, [http://arxiv.org/abs/math/0502199 Finding almost squares]. Acta Arith. 121 (2006), no. 3, 221--232.<br />
* [D1998] P. Dusart, [http://www.unilim.fr/laco/theses/1998/T1998_01.html Autour de la fonction qui compte le nombre de nombres premiers], 1998<br />
* [E1949] P. Erdős, [http://www.math-inst.hu/~p_erdos/1949-07.pdf On The Converse of Fermat's Theorem]<br />
* [EP1986] P. Erdős and C. Pomerance, On the number of false witnesses for a composite number, Math. Comp. 46 (1986), 259-279.<br />
* [FT????] M. Filaseta, O. Trifonov, [http://books.google.com/books?id=G02moOmuOX4C&pg=PA235&dq=squarefree+numbers#v=onepage&q=squarefree%20numbers&f=false On gaps between squarefree numbers], Analytic number theory: Proceedings of a conference in honor of Paul Bateman <br />
* [FT1992] M. Filaseta and O. Trifonov, On gaps between squarefree numbers. II, J. London Math. Soc. (2), 45 (1992), no. 2, 215-221. <br />
* [GW2002] O. Goldreich, A. Wigderson, [http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GW02/gw02.pdf Derandomization that is rarely wrong from short advice that is typically good]<br />
* [G1998] A. Granville, ABC allows us to count squarefrees, Internat. Math. Res. Notices (1998), no. 19, 991–1009.<br />
* [G1995] A. Granville, [http://www.dartmouth.edu/~chance/chance_news/for_chance_news/Riemann/cramer.pdf "Harald Cramér and the distribution of prime numbers"], Scandinavian Actuarial J. 1 (1995), 12—28. <br />
* [HB1984] D.R. Heath-Brown, The square sieve and consecutive square-free numbers, Math. Ann. 266 (1984), 251-259<br />
* [HB1995] D.R. Heath-Brown, The largest prime factor of integers in an interval, Science in China ???<br />
* [IW1997] 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.<br />
* [J2006] R. Jones, [http://arxiv.org/abs/math/0612415 The density of prime divisors in the arithmetic dynamics of quadratic polynomials]<br />
* [KLS2002] Křížek, Luca and Somer, On the convergence of series of reciprocals of primes related to the Fermat numbers, J. Number Theory 97(2002), 95–112<br />
* [L1979] H.W. Lenstra, [https://openaccess.leidenuniv.nl/bitstream/1887/3801/1/346_036.pdf Miller's Primality Test], Information Processing Letters, 1979<br />
* [L1996] H. Liu, Almost primes in short intervals. J. Number Theory 57 (1996), no. 2, 303--322.<br />
* [LW1999] H. Liu, J. Wu, Numbers with a large prime factor, Acta Arith. 89 (1999), no. 2, 163–187.<br />
* [M1994] U. Maurer, [http://eprints.kfupm.edu.sa/40655/ Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters], Journal of Cryptology 8 (1994), 123-155<br />
* [O1985] Odoni, On the prime divisors of the sequence <math>w_n+1 = 1+ w_1 \ldots w_n</math>. J. London Math. Soc. (2), 32(1):1–11, 1985. <br />
* [P????] F. Pappalardi, [http://www.mat.uniroma3.it/users/pappa/papers/allahabad2003.pdf A survey on k-freeness]<br />
* [P1981] C. Pomerance, [http://math.dartmouth.edu/~carlp/PDF/paper32.pdf On the distribution of pseudoprimes, Math. Comp. 37 (1981), 587-593.]<br />
* [P1982] C. Pomerance, [http://math.dartmouth.edu/~carlp/PDF/lower.pdf A new lower bound for the pseudoprime counting function, Illinois J. Math. 26 (1982), 4-9.]<br />
* [P1989] C. Pomerance, Two methods in elementary analytic number theory, Number theory and applications, R. A. Mollin, ed., Kluwer Academic Publishers, Dordrecht, 1989, pp. 135-161.<br />
<br />
* [S2006] K. Soundararajan, [http://arxiv.org/abs/math/0606408 The distribution of the primes] (survey)<br />
* [S2006b] K. Soundararajan, [http://arxiv.org/abs/math/0605696 Small gaps between prime numbers: The work of Goldston-Pintz-Yildirim]<br />
* [T2006] L. Trevisan, [http://arxiv.org/abs/cs.CC/0601100 Pseudorandomness and Combinatorial Constructions]<br />
<br />
Please help out by adding links or completing references, or adding further references to the list above!<br />
<br />
== External links ==<br />
<br />
# [http://qwiki.stanford.edu/wiki/Complexity_Zoo Complexity Zoo]<br />
# "[http://blog.computationalcomplexity.org/2009/08/finding-primes.html Finding Primes]", Lance Fortnow, August 4 2009</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Kolmogorov_complexityKolmogorov complexity2009-08-20T00:09:58Z<p>Asdf: </p>
<hr />
<div>Intuitively speaking, the '''Kolmogorov complexity''' of an integer n is the least number of bits one needs to describe n in some suitable language. For instance, one could use the language of Turing machines: an integer n has Kolmogorov complexity at most k if there exists a Turing machine with length at most k which, when run, will halt to produce n as output.<br />
<br />
Thus, for instance, any k-bit integer has Kolmogorov complexity at most k+O(1) (the O(1) overhead being for the trivial program that outputs the remaining k bits of the Turing machine). On the other hand, it is obvious that there are at most <math>2^k</math> integers of Kolmogorov complexity at most k (we'll refer to this as the ''counting argument''). As a consequence, most k-bit integers have Kolmogorov complexity close to k. <br />
<br />
On the other hand, a deterministic algorithm which takes k as input and runs in time polynomial in k can only produce integers of Kolmogorov complexity <math>O(\log k)</math>, since any number produced can be described by a Turing machine of length <math>O(\log k) + O(1)</math> (the O(1) is to describe the algorithm, and the <math>O(\log k)</math> bits are to describe how long the program is to run and what k is).<br />
<br />
* [[wikipedia:Kolmogorov_complexity|The Wikipedia entry for Kolmogorov complexity]]</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Kolmogorov_complexityKolmogorov complexity2009-08-20T00:09:09Z<p>Asdf: add a link to Kolmogorov complexity as explained on wikipedia</p>
<hr />
<div>Intuitively speaking, the Kolmogorov complexity of an integer n is the least number of bits one needs to describe n in some suitable language. For instance, one could use the language of Turing machines: an integer n has Kolmogorov complexity at most k if there exists a Turing machine with length at most k which, when run, will halt to produce n as output.<br />
<br />
Thus, for instance, any k-bit integer has Kolmogorov complexity at most k+O(1) (the O(1) overhead being for the trivial program that outputs the remaining k bits of the Turing machine). On the other hand, it is obvious that there are at most <math>2^k</math> integers of Kolmogorov complexity at most k (we'll refer to this as the ''counting argument''). As a consequence, most k-bit integers have Kolmogorov complexity close to k. <br />
<br />
On the other hand, a deterministic algorithm which takes k as input and runs in time polynomial in k can only produce integers of Kolmogorov complexity <math>O(\log k)</math>, since any number produced can be described by a Turing machine of length <math>O(\log k) + O(1)</math> (the O(1) is to describe the algorithm, and the <math>O(\log k)</math> bits are to describe how long the program is to run and what k is).<br />
<br />
* [[wikipedia:Kolmogorov_complexity|The Wikipedia entry for Kolmogorov complexity]]</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Generic_primeGeneric prime2009-08-20T00:05:42Z<p>Asdf: </p>
<hr />
<div>We'll use the term '''generic prime''' to denote a prime with high [[Kolmogorov complexity]], e.g. a k-digit prime with complexity at least <math>\sqrt{k}</math>. Note that almost all primes are generic.<br />
<br />
On the other hand, the [[finding primes]] conjecture is false for generic primes, as deterministic algorithms in poly(k) time can only produce numbers of complexity <math>O(\log k)</math>. Thus any solution of this conjecture must in some way distinguish primes from generic primes. This rules out any approach based purely on average-case results about the distribution of primes, since primes and generic primes are essentially indistinguishable in these results. (However, for the purposes of the weak conjecture, one could hope to use average-case results on relatively thin sets, of size <math>10^{\varepsilon k}</math> or so.)<br />
<br />
A factoring oracle breaks the indistinguishability between primes and generic primes, since non-generic primes cannot be given any non-trivial factoring. So generic primes do not seem to provide an obstruction to the conjecture with factoring.</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Sylvester%27s_sequenceSylvester's sequence2009-08-19T23:58:43Z<p>Asdf: </p>
<hr />
<div>'''Sylvester's sequence''' <math>a_1,a_2,a_3,\ldots</math> is defined recursively by setting <math>a_1=2</math> and <math>a_k = a_1 \ldots a_{k-1}+1</math> for all subsequent k, thus the sequence begins<br />
<br />
: 2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 (sequence [http://www.research.att.com/~njas/sequences/A000058 A000058] in OEIS).<br />
<br />
The elements of this sequence are mutually coprime, so after factoring k of them, one is guaranteed to have at least k prime factors.<br />
<br />
There is a connection to the [[finding primes]] project: It is a result of Odoni that the number of primes less than n that can divide any one of the <math>a_k</math> is <math>O(n / \log n \log\log\log n)</math> rather than <math>O(n / \log n)</math> (the prime number theorem bound). If we then factor the first k elements of this sequence, we must get a prime of size at least <math>k\log k \log \log \log k</math> or so. <br />
<br />
It is also conjectured that this sequence is square-free; if so, <math>a_k, a_k-1</math> form a pair of square-free integers, settling a toy problem in the finding primes project.<br />
<br />
* [[wikipedia:Sylvester's_sequence|The Wikipedia entry for this sequence]]</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Discrete_logarithmDiscrete logarithm2009-08-19T23:52:29Z<p>Asdf: </p>
<hr />
<div>The '''discrete logarithm''' problem is this: given a prime p, a generator g, and another non-zero residue class a mod p, find an integer n such that <math>g^n = a \hbox{ mod } p</math>. This problem is related to a number of cryptography systems, e.g. Diffie-Hellman.<br />
<br />
The possibility was raised that if discrete logarithm was assumed to be hard, then some pseudorandom number generator might be constructed which could resolve the [[finding primes]] problem. But there is a basic difficulty here, which is that one needs to have a large prime in hand before one could solve this problem! (But perhaps one could use one large prime to find others by this method?)<br />
<br />
* [[wikipedia:Discrete_logarithm|The wikipedia page on discrete logarithms]]</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Finding_primesFinding primes2009-08-19T23:47:27Z<p>Asdf: changed external links to wikipedia to interwiki links</p>
<hr />
<div>This is the main wiki page for the Polymath4 project "[http://en.wordpress.com/tag/finding-primes/ Finding primes]".<br />
<br />
The main aim of the project is to resolve the following conjecture:<br />
<br />
:'''(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.<br />
<br />
Since primality is known to be in [[The complexity class P|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.<br />
<br />
Contributions and corrections to this wiki page (and its subpages) are very welcome.<br />
<br />
== Threads ==<br />
<br />
# [http://polymathprojects.org/2009/07/27/proposal-deterministic-way-to-find-primes/ Proposal for the project and initial research thread] (Inactive)<br />
# [http://polymathprojects.org/2009/08/09/research-thread-ii-deterministic-way-to-find-primes/ Research thread II] (Inactive)<br />
# [http://polymathprojects.org/2009/08/13/research-thread-iii-determinstic-way-to-find-primes/ Research thread III] (Active)<br />
# [http://polymathprojects.org/2009/07/28/deterministic-way-to-find-primes-discussion-thread/ The current discussion thread] (Active)<br />
<br />
== Easier versions of the problem ==<br />
<br />
:'''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 [[Finding primes with O(k) random bits|one can do this with O(k) random bits]]; and if one can use just <math>O(\log k)</math> random bits, one is done by exhausting over the random bits.)<br />
<br />
One way to solve the semi-weak conjecture would be to find an "explorable" set of size <math>\exp(o(k))</math> of integers, a significant fraction (at least <math>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).<br />
<br />
:'''Weak conjecture''': There exists a deterministic algorithm, which, when given an integer k, is guaranteed to find a prime of at least <math>\omega(\log k)</math> digits in length in time polynomial in k, where <math>\omega(\log k)</math> grows faster than <math>\log k</math> as <math>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>\exp(o(k))</math>. Note that the semi-weak conjecture implies the weak conjecture).<br />
<br />
:'''Strong conjecture with factoring''': Same as the original conjecture, but assume that one has a ''factoring oracle'' will return the factors of any number given to it (as a stream of bits) in unit time. (This oracle can be given "for free" if factoring is in P, but we can also assume the existence of this oracle even if factoring is not in P.)<br />
<br />
:'''Semi-weak conjecture with factoring''': Same as the semi-weak conjecture, but with a factoring oracle.<br />
<br />
:'''Weak conjecture with factoring''': Same as the weak conjecture, but with a factoring oracle. (Note that there are deterministic sieve algorithms, such as the quadratic sieve, which are believed to run in subexponential time <math>\exp(o(k))</math>, so this oracle is in some sense available "for free" for this problem assuming this belief.)<br />
<br />
The weak conjecture with factoring is the easiest of the six, and so perhaps one should focus on that one first.<br />
<br />
It is also of interest to see whether the conjecture becomes easier to solve assuming that P=BPP or P=BQP.<br />
<br />
== Partial results ==<br />
<br />
# [[P=NP implies a deterministic algorithm to find primes]]<br />
# [[An efficient algorithm exists if Cramer's conjecture holds]]<br />
# [[Finding primes with O(k) random bits|k-digit primes can be found with high probability using O(k) random bits]]<br />
## If [[Pseudo-random generators (PRG)|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.<br />
# The function field analogue (i.e. finding degree k irreducible polynomials over a finite field) is known [AL1986]<br />
## The analogue over the rationals is even easier: Eisenstein's criterion provides plenty of irreducible polynomials of degree k, e.g. <math>x^k-2</math>.<br />
# Assuming a suitably quantitative version of [[Schinzel's hypothesis H]] (namely, the Bateman-Horn conjecture), the weak conjecture is true, as one can simply search over all k-digit numbers of the form <math>n^d-2</math> (say) for any fixed d to give an algorithm that works in time <math>O(10^{k/d})</math>. By randomly sampling such integers, one also establishes the semi-weak conjecture (assuming that one has the expected density for primes in hypothesis H).<br />
# It's easy to deterministically find large square-free numbers; just multiply lots of small primes together. However, it is not known how to test a number for square-freeness deterministically and quickly (unless one has a factoring oracle, in which case it is trivial).<br />
## However, it's not so obvious how to find large pairs <math>n,n+1</math> of consecutive square-free numbers, though such pairs must exist by counting arguments (the density of square-free numbers is <math>6/\pi^2 \approx 60\%</math>). This could be a good variant problem.<br />
### It is conjectured that every element of [[Sylvester's sequence]] is square-free. If so, this solves the above problem.<br />
# 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>k^A</math>, then increment A from 1 onward, until one gets a hit.<br />
<br />
Here are the current "world records" for the fastest way to deterministically (and provably) obtain a k-digit prime (ignoring errors of <math>\exp(o(k))</math> in the run time):<br />
<br />
# <math>O(10^k)</math>: The trivial algorithm of testing each of the k-digit numbers in turn until one gets a hit.<br />
# <math>O(10^k)^{3/4}</math>: Test the k-digit numbers of the form <math>a^2+b^4</math> for primality (the [[Friedlander-Iwaniec theorem]] guarantees a hit for k large enough).<br />
# <math>O(10^k)^{2/3}</math>: Test the k-digit numbers of the form <math>a^3+2b^3</math> for primality (a hit is guaranteed for large k by a result of Heath-Brown).<br />
# <math>O(10^{k})^{6/11+\epsilon} (\approx O(10^{k})^{.5454})</math>assuming factoring oracle: Factor each number in the interval <math>[x^{12/11},x^{12/11}+x^{6/11+\epsilon}]</math>, one will find a prime prime factor of order x by [HB1995]. <br />
# <math>O(10^k)^{0.525}</math>: Test the k-digit numbers from, say, <math>10^k</math> onwards until one gets a hit (here we use the [BHP2001] bound on [[prime gaps]]).<br />
# <math>O(10^k)^{1/2}</math> assuming RH: Test the k-digit numbers from, say, <math>10^k</math> onwards until one gets a hit (here we use the RH bound on [[prime gaps]]).<br />
<br />
Note that if one can get <math>O(10^k)^{\varepsilon}</math> for each fixed <math>\varepsilon > 0</math>, then one has established the weak conjecture.<br />
<br />
A slight variant of the problem: assuming a factoring oracle, given an algorithm that runs in k steps, how large a prime is the algorithm ''guaranteed'' to produce in the ''worst-case'' scenario? (Note that this is very different from what the algorithm is ''heuristically'' predicted to produce in the ''average-case'' scenario.)<br />
<br />
Here is a simple algorithm that produces a prime larger than about <math>k \log k</math> in k steps, based on Euclid's proof of the infinitude of primes:<br />
<br />
* Initialise <math>p_1=2</math>.<br />
* Once <math>p_1,\ldots,p_{k-1}</math> are computed, define <math>p_k</math> to be the largest prime factor of <math>p_1 \ldots p_{k-1}+1</math>.<br />
<br />
This generates k distinct primes; the prime number theorem tells us that the k^th prime has size about <math>k \log k</math>, so at least one of the primes produced here has size at least <math>k \log k</math>.<br />
<br />
If one instead works with [[Sylvester's sequence]] <math>a_k = a_1 \ldots a_{k-1}+1</math>, then it is known [O1985] that the number of primes less than n that can divide any one of the <math>a_k</math> is <math>O( n / \log n \log \log \log n )</math> rather than <math>O(n/\log n)</math> (the prime number theorem bound). If we then factor the first k elements of this sequence, we must get a prime of size at least <math>k \log k \log \log \log k</math> or so.<br />
<br />
One can do better still by working with the Fermat numbers, <math>F_n = 2^{2^n}+1</math>. It is known [KLS2002] that the number of primes dividing any of the <math>F_n</math> is <math>O(\sqrt{n}/\log n)</math>, so in particular if we factor the first k Fermat numbers, we get a prime almost of size <math>k^2</math>. In fact, it's a classical result of Euler that the prime divisors of <math>F_n</math> are all at least <math>2^{n+2}+1</math>, so we can obtain a large prime simply by factoring a Fermat number.<br />
<br />
Assuming RH, one can find a prime larger than <math>k^2</math> in about k steps by the method indicated earlier (start at <math>k^2</math> and increment until one hits a prime). Unconditionally, one gets a prime larger than <math>k^{1/0.525}</math> by this method. Currently this is the world record.<br />
<br />
== Variants of the problem ==<br />
<br />
# 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.<br />
<br />
=== Finding consecutive (or nearby) square-free integers ===<br />
<br />
:'''Toy problem''' Is there an efficient algorithm to find consecutive square-free integers n, n+1 of at least k digits in length assuming an oracle to determine whether a number is square free (a special case of the factoring oracle)? Or just square-free integers that are close together (e.g. polylog(n)).<br />
<br />
Note that finding one large square-free number is easy: just multiply lots of distinct small primes together. Also, as the density of square-free numbers is <math>6/\pi^2 \approx 0.6</math>, a counting argument shows that pairs of consecutive square-free numbers exist in abundance, and are thus easy to find probabilistically. The density can be increased to arbitrarily close to 1 using the [[W-trick]], so one could also ask for, say, long arithmetic progressions of square-free numbers also.<br />
<br />
If [[Sylvester's sequence]] is square-free, then this solves the problem.<br />
<br />
Testing a number for square-freeness is trivial with a factoring oracle. No unconditional polynomial-time deterministic algorithm for square-freeness seems to be known. (It is listed as an open problem in [http://portal.acm.org/citation.cfm?id=749544 this paper from 1994].)<br />
<br />
Unconditionally, there are asymptotics for the number of square-free numbers in [1,N] with an error term of <math>O(N^{1/2})</math>, which leads to a <math>O(10^k)^{1/2}</math> algorithm (just search an interval of this length for square-freeness). This is the current unconditional world record. Assuming RH, this can be improved to <math>O(10^k)^{17/54+\varepsilon}</math>. <br />
<br />
There is an asymptotic [HB1984] for the number of consecutive square free numbers with an error term of <math>O(N^{7/11})</math>, leading to a <math>O(10^k)^{7/11+\varepsilon}</math>, though this is inferior to the above bounds.<br />
<br />
It is known [FT1992] that the interval <math>[N, N+N^{1/5+\epsilon}]</math> contains at least one square-free number; Granville [G1998] improved this to <math>[N,N+N^{\varepsilon}]</math> assuming the [[ABC conjecture]]. If the density in such intervals can be made to exceed 50% (perhaps after first applying the [[W-trick]]) then we would have solved the weak version of this toy problem assuming ABC.<br />
<br />
=== Finding pseudoprimes ===<br />
<br />
:'''Problem:''' How quickly can one find a solution to the congruence <math>2^{n-1}=1 \hbox{ mod } n</math> with n at least k digits in length? (a pseudoprime)?<br />
<br />
It is conjectured that the largest gap between k-digit pseudoprimes is poly(k) (this is weaker than [[Cramer's conjecture]], and would imply a polynomial time solution to the above problem).<br />
<br />
It is conjectured that the number <math>\mathcal{P}_a(x)</math> of pseudoprimes to any base <math>a \neq \pm1</math> satisfies<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) = \log(x) - \log(x)\frac{\log\log\log(x)}{\log\log(x)}(1+o(1)).</math><br />
<br />
However, the best known bounds seem to be<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) \leq \log(x) - \frac{1}{2}\log(x)\frac{\log\log\log(x)}{\log\log(x)}(1+o(1)),</math><br />
<br />
and<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) \geq (\frac{\log(x)}{\log a})^{E/(E+1)-o(1)},</math><br />
<br />
where E is a constant which is conjectured to equal 1, but is only known to have value at least 1-1/(2\sqrt{e}). These results can be found in [P1981], [P1982], [P1989]. Better bounds are known to hold on average [EP1986].<br />
<br />
If n is a pseudoprime, then <math>2^n-1</math> is also a pseudoprime (because <math>2^n = 1 \hbox{ mod } 2^n - 1 </math>, and <math>2^n-2</math> is a multiple of n). This, technically, solves the problem, but can we find denser sets of pseudoprimes? What if we want <math>2^{n-1}=1 \hbox{ mod } n</math> and <math>3^{n-1} = 1 \hbox{ mod } n</math> simultaneously?<br />
<br />
=== Finding Almost Primes===<br />
<br />
An almost primes is a number that is the product of at most two primes (counted with multiplicity). <br />
<br />
:'''problem''' How fast can we deterministically write down a <math>k</math> digit almost prime?<br />
<br />
Clearly this is a relaxation of the prime problem, so we expect to get better results. In [L1996] it is shown that the interval <math>[x,x+x^{.436}]</math> contains an almost prime. This gives us a <math>O(10^{k})^{.436}</math> algorithm. Assuming a factoring oracle, the problems of deterministically finding a <math>k</math> digit almost prime and a <math>k</math> digit prime in polynomial time are equivalent. If we can find an almost prime in polynomial time we can factor it and get (a slightly smaller) prime. Conversely, if we can find a prime in polynomial time we can square it to find (a slightly larger) almost prime. Using our prime technology this should give a <math>O(10^{k})^{.262}</math> algorithm.<br />
<br />
== Observations and strategies ==<br />
<br />
# 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>N^\varepsilon</math>-smooth (or <math>\log^{O(1)} N</math> smooth, if one only wants to solve the weak conjecture with factoring). <br />
## 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>\{ Wn+1: 1 \leq n \leq k^{100} \}</math> (say) is <math>k^A</math>-smooth, then one has found a prime with at least <math>A \log k</math> digits in polynomial time. If one can make A arbitrarily large, one has solved the baby problem with factoring.<br />
## One way to proceed is to analyse [[iterated sumsets of log-primes]].<br />
## Another is to analyse [[signed sums of prime reciprocals]].<br />
## Probably the best known bound along these lines is given in [HB1995] and states that the interval <math>[x,x+x^{.5+\epsilon}]</math> contains an integer with a prime factor at least <math>x^{11/12 -\epsilon}</math>. This only leads to a <math>O(10^{k})^{.5455}</math> algorithm.<br />
# Another approach is to accurately compute the [[prime counting function]].<br />
# If one can find explicitly enumerable sets of k-digit numbers of size <math>O(10^{\varepsilon k})</math> for any fixed <math>\varepsilon > 0</math> that are guaranteed to contain a prime, then one has solved the weak conjecture. If instead one can find randomly samplable sets of k-digit numbers of size <math>O(10^{\varepsilon k})</math> that contain a large fraction (e.g. <math>\exp(-o(k))</math> of primes), one has solved the semi-weak conjecture. If one can find explicit sets of poly(k) size that are guaranteed to contain a prime, one has solved the strong conjecture.<br />
# 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 [[wikipedia:Pseudorandom_generators_for_polynomials|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.<br />
# If one can find a sequence of easily constructible, mutually coprime integers whose prime factors are contained in a sparse subset of the primes, this generates (with the aid of a factoring oracle) a sparse set of primes. So far the sparsest set of this type has come from factoring the Fermat numbers.<br />
<br />
== Negative results and other obstructions ==<br />
<br />
# 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>O(k^O(1))</math> smooth integer in any interval that can be searched in polynomial time. Indeed, there are heuristic arguments that suggest that even augmented with basic Fourier analysis and assuming RH, this method is unlikely to work, although they haven't yet been fully formalized.<br />
# 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.<br />
## In a similar spirit, one cannot hope to find non-smooth numbers in a short interval by analysing the iterated sumset of the log-primes and using average-case information about that set), because if one deletes all the primes arising from factors of that interval, one still captures most of the primes (and thus most of the average-case behaviour of the log-primes) while losing the information about that interval. <br />
# It is not possible to prove the conjecture purely by "soft" (i.e. relativisable) complexity theory methods which do not use any additional information on the primes rather than their density. Details are at [[Oracle counterexample to finding pseudoprimes]].<br />
<br />
== How could the conjecture be false? ==<br />
<br />
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:<br />
<br />
# 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>O(\log k)</math> that runs in time <math>k^{O(1)}</math>, are composite. [If the conjecture fails with factoring, then these numbers are furthermore <math>\exp(\varepsilon k)</math> smooth for any fixed <math>\varepsilon > 0</math>; if even the weak conjecture with factoring fails, they are <math>k^{O(1)}</math>-smooth.]<br />
# In fact, all constructible numbers are not only composite/smooth, but they sit inside intervals of length <math>k^{100}</math>, all of whose elements are composite/smooth. (One can replace 100 by any other fixed number.)<br />
## In particular, Cramer's conjecture fails; the gaps between adjacent k-digit primes exceeds <math>k^{100}</math> around every constructible number.<br />
# No pseudorandom number generators exist. In particular, this implies that one-way functions do not exist.<br />
# <math>P \neq NP</math>. More specifically, the decision problem "Does there exist a prime in a given interval?" is in [[The complexity class NP|NP]], but cannot lie in [[The complexity class P|P]] if the conjecture fails.<br />
<br />
== Relevant concepts ==<br />
<br />
Complexity theory concepts:<br />
<br />
# Complexity classes<br />
## [[The complexity class P|P]]<br />
## [[The complexity class NP|NP]]<br />
## [[The complexity class BPP|BPP]]<br />
## [[The complexity class promise-BPP|promise-BPP]]<br />
## [[The complexity class BQP|BQP]]<br />
## [[The complexity class DTIME|DTIME(f(n))]]<br />
# [[Pseudo-random generators (PRG)]]<br />
# [http://blog.computationalcomplexity.org/2006/07/full-derandomization.html Full derandomization]<br />
# [[wikipedia:One-way_function|one-way function]]<br />
# [[Impagliazzo's five worlds]]: Algorithmica, Heuristica, Pessiland, Minicrypt, Cryptomania<br />
# [[Kolmogorov complexity]]<br />
# [[wikipedia:Oracle_machine|Oracles]<br />
<br />
Number theory concepts:<br />
<br />
# [[Cramer's random model for the primes]]<br />
# [[Prime gaps]]<br />
# [[Generic prime]]<br />
# [[Smooth number]]<br />
# The [[W-trick]]<br />
# [[Sylvester's sequence]]<br />
# [[Siegel zero]]<br />
# [[wikipedia:Big_O_notation|Asymptotic notation]]<br />
# [[Fermat number]]<br />
# [[Pseudoprimes]]<br />
<br />
Other:<br />
<br />
# [[wikipedia:Expander_graph|Expander graphs]]<br />
<br />
Note: articles with external links should eventually be replaced by in-house pages that can provide information that is more dedicated to this project.<br />
<br />
== Relevant conjectures ==<br />
<br />
# [[The complexity class NP|P=NP]]<br />
# [[The complexity class BPP|P=BPP]]<br />
# [[The complexity class promise-BPP|P=promise-BPP]]<br />
# [[The complexity class BQP|P=BQP]]<br />
# [[Pseudo-random generators (PRG)|existence of PRG]]<br />
# [[wikipedia:One-way_function|existence of one-way functions]]<br />
# whether [[The complexity class DTIME|DTIME(2^n)]] has subexponential circuits<br />
# [[wikipedia:Riemann_hypothesis|The Riemann Hypothesis (RH)]]<br />
## [[wikipedia:Generalized_Riemann_hypothesis|The generalised Riemann Hypothesis (GRH)]]<br />
# the [[Hardy-Littlewood prime tuples conjecture]]<br />
# the [[ABC conjecture]]<br />
# [[Cramer's conjecture]]<br />
# [[Schinzel's hypothesis H]]<br />
# [[discrete logarithm|discrete log in P]]<br />
# [[factoring|factoring in P]]<br />
<br />
== Relevant results ==<br />
<br />
# [[Brun-Titchmarsh inequality]]<br />
# [[Erdos-Kac theorem]]<br />
# [[Bertrand's postulate]]<br />
# [[Friedlander-Iwaniec theorem]]<br />
# [[List of results implied by the Riemann Hypothesis|Conditional on the Riemann hypothesis]]<br />
<br />
== Relevant papers ==<br />
<br />
* [AMcC1994] L. Adelman, K. McCurley, [http://portal.acm.org/citation.cfm?id=749544 Open problems in number theoretic complexity, II], Lecture Notes In Computer Science; Vol. 877, Proceedings of the First International Symposium on Algorithmic Number Theory 291 - 322 (1994)<br />
* [AL1986] L. Adelman, H. Lenstra, [http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf Finding irreducible polynomials over finite fields], Proc. 18th Annual ACM Symp. on Theory of Computing (STOC), Berkeley, May 28–30, 350–355.<br />
* [B1990] E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), 355-380], <br />
* [BH1996] R. C. Baker and G. Harman, “The difference between consecutive primes,” Proc. Lond. Math. Soc., series 3, 72 (1996) 261–280. <br />
*[BH1998] R. C. Baker, G. Harmen, Shifted primes without large prime factors, Acta Arith. 83 (1998), no. 4, 331–361<br />
* [BHP2001] R. C. Baker, G. Harman and J. Pintz, The difference between consecutive primes, II, Proceedings of the London Mathematical Society 83, (2001), 532–562.<br />
* [BH1998] A. Balog, T. Wooley, “[http://www.austms.org.au/Publ/JAustMS/V64P2/abs/c30/ On strings of consecutive integers with no large prime factors]”, J. Austral. Math. Soc. Ser. A 64 (1998), no. 2, 266–276<br />
* [C2006] T. H. Chan, [http://arxiv.org/abs/math/0502199 Finding almost squares]. Acta Arith. 121 (2006), no. 3, 221--232.<br />
* [D1998] P. Dusart, [http://www.unilim.fr/laco/theses/1998/T1998_01.html Autour de la fonction qui compte le nombre de nombres premiers], 1998<br />
* [E1949] P. Erdős, [http://www.math-inst.hu/~p_erdos/1949-07.pdf On The Converse of Fermat's Theorem]<br />
* [EP1986] P. Erdős and C. Pomerance, On the number of false witnesses for a composite number, Math. Comp. 46 (1986), 259-279.<br />
* [FT????] M. Filaseta, O. Trifonov, [http://books.google.com/books?id=G02moOmuOX4C&pg=PA235&dq=squarefree+numbers#v=onepage&q=squarefree%20numbers&f=false On gaps between squarefree numbers], Analytic number theory: Proceedings of a conference in honor of Paul Bateman <br />
* [FT1992] M. Filaseta and O. Trifonov, On gaps between squarefree numbers. II, J. London Math. Soc. (2), 45 (1992), no. 2, 215-221. <br />
* [GW2002] O. Goldreich, A. Wigderson, [http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GW02/gw02.pdf Derandomization that is rarely wrong from short advice that is typically good]<br />
* [G1998] A. Granville, ABC allows us to count squarefrees, Internat. Math. Res. Notices (1998), no. 19, 991–1009.<br />
* [G1995] A. Granville, [http://www.dartmouth.edu/~chance/chance_news/for_chance_news/Riemann/cramer.pdf "Harald Cramér and the distribution of prime numbers"], Scandinavian Actuarial J. 1 (1995), 12—28. <br />
* [HB1984] D.R. Heath-Brown, The square sieve and consecutive square-free numbers, Math. Ann. 266 (1984), 251-259<br />
* [HB1995] D.R. Heath-Brown, The largest prime factor of integers in an interval, Science in China ???<br />
* [IW1997] 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.<br />
* [J2006] R. Jones, [http://arxiv.org/abs/math/0612415 The density of prime divisors in the arithmetic dynamics of quadratic polynomials]<br />
* [KLS2002] Křížek, Luca and Somer, On the convergence of series of reciprocals of primes related to the Fermat numbers, J. Number Theory 97(2002), 95–112<br />
* [L1979] H.W. Lenstra, [https://openaccess.leidenuniv.nl/bitstream/1887/3801/1/346_036.pdf Miller's Primality Test], Information Processing Letters, 1979<br />
* [L1996] H. Liu, Almost primes in short intervals. J. Number Theory 57 (1996), no. 2, 303--322.<br />
* [LW1999] H. Liu, J. Wu, Numbers with a large prime factor, Acta Arith. 89 (1999), no. 2, 163–187.<br />
* [M1994] U. Maurer, [http://eprints.kfupm.edu.sa/40655/ Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters], Journal of Cryptology 8 (1994), 123-155<br />
* [O1985] Odoni, On the prime divisors of the sequence <math>w_n+1 = 1+ w_1 \ldots w_n</math>. J. London Math. Soc. (2), 32(1):1–11, 1985. <br />
* [P????] F. Pappalardi, [http://www.mat.uniroma3.it/users/pappa/papers/allahabad2003.pdf A survey on k-freeness]<br />
* [P1981] C. Pomerance, [http://math.dartmouth.edu/~carlp/PDF/paper32.pdf On the distribution of pseudoprimes, Math. Comp. 37 (1981), 587-593.]<br />
* [P1982] C. Pomerance, [http://math.dartmouth.edu/~carlp/PDF/lower.pdf A new lower bound for the pseudoprime counting function, Illinois J. Math. 26 (1982), 4-9.]<br />
* [P1989] C. Pomerance, Two methods in elementary analytic number theory, Number theory and applications, R. A. Mollin, ed., Kluwer Academic Publishers, Dordrecht, 1989, pp. 135-161.<br />
<br />
* [S2006] K. Soundararajan, [http://arxiv.org/abs/math/0606408 The distribution of the primes] (survey)<br />
* [S2006b] K. Soundararajan, [http://arxiv.org/abs/math/0605696 Small gaps between prime numbers: The work of Goldston-Pintz-Yildirim]<br />
* [T2006] L. Trevisan, [http://arxiv.org/abs/cs.CC/0601100 Pseudorandomness and Combinatorial Constructions]<br />
<br />
Please help out by adding links or completing references, or adding further references to the list above!<br />
<br />
== External links ==<br />
<br />
# [http://qwiki.stanford.edu/wiki/Complexity_Zoo Complexity Zoo]<br />
# "[http://blog.computationalcomplexity.org/2009/08/finding-primes.html Finding Primes]", Lance Fortnow, August 4 2009</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Prime_gapsPrime gaps2009-08-19T23:39:50Z<p>Asdf: replace an external link with an interwiki link</p>
<hr />
<div>If <math>p_n</math> denotes the n^th prime, then <math>p_{n+1}-p_n</math> is the n^th prime gap.<br />
<br />
On average, the prime number theorem tells us that <math>p_{n+1}-p_n</math> has size <math>O(\log p_n)</math>. <br />
<br />
A recent result of Goldston-Pintz-Yildirim shows that there exist infinitely many n for which the gap is as small as <math>o(\log p_n)</math> (in fact more precise bounds are known). But the set of small gaps established by this method is sparse.<br />
<br />
[[Cramer's conjecture]] asserts that the prime gap never exceeds <math>O(\log^2 p_n)</math> in size. If so, this resolves the [[finding primes]] project positively. However, the best upper bound on the prime gap is <math>O( p_n^{1/2} \log p_n )</math> assuming the Riemann hypothesis, and <math>O( p_n^{0.525} )</math> otherwise (a result of Baker, Harman, and Pintz; an earlier bound of <math>O(p_n^{0.535})</math> was obtained by Baker and Harman.).<br />
<br />
Rankin showed that the prime gap can be as large as <math>\log p_n \frac{\log \log p_n \log \log \log \log p_n}{(\log \log \log p_n)^3}</math>.<br />
<br />
# R. C. Baker and G. Harman, “The difference between consecutive primes,” Proc. Lond. Math. Soc., series 3, 72 (1996) 261–280. MR 96k:11111<br />
# K. Soundararajan, [http://arxiv.org/abs/math/0605696 Small gaps between prime numbers: The work of Goldston-Pintz-Yildirim]<br />
# [[wikipedia:Prime_gap|The Wikipedia entry on prime gaps]]</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Finding_primesFinding primes2009-08-19T23:27:43Z<p>Asdf: fixed bad links ending with spurious commas</p>
<hr />
<div>This is the main wiki page for the Polymath4 project "[http://en.wordpress.com/tag/finding-primes/ Finding primes]".<br />
<br />
The main aim of the project is to resolve the following conjecture:<br />
<br />
:'''(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.<br />
<br />
Since primality is known to be in [[The complexity class P|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.<br />
<br />
Contributions and corrections to this wiki page (and its subpages) are very welcome.<br />
<br />
== Threads ==<br />
<br />
# [http://polymathprojects.org/2009/07/27/proposal-deterministic-way-to-find-primes/ Proposal for the project and initial research thread] (Inactive)<br />
# [http://polymathprojects.org/2009/08/09/research-thread-ii-deterministic-way-to-find-primes/ Research thread II] (Inactive)<br />
# [http://polymathprojects.org/2009/08/13/research-thread-iii-determinstic-way-to-find-primes/ Research thread III] (Active)<br />
# [http://polymathprojects.org/2009/07/28/deterministic-way-to-find-primes-discussion-thread/ The current discussion thread] (Active)<br />
<br />
== Easier versions of the problem ==<br />
<br />
:'''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 [[Finding primes with O(k) random bits|one can do this with O(k) random bits]]; and if one can use just <math>O(\log k)</math> random bits, one is done by exhausting over the random bits.)<br />
<br />
One way to solve the semi-weak conjecture would be to find an "explorable" set of size <math>\exp(o(k))</math> of integers, a significant fraction (at least <math>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).<br />
<br />
:'''Weak conjecture''': There exists a deterministic algorithm, which, when given an integer k, is guaranteed to find a prime of at least <math>\omega(\log k)</math> digits in length in time polynomial in k, where <math>\omega(\log k)</math> grows faster than <math>\log k</math> as <math>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>\exp(o(k))</math>. Note that the semi-weak conjecture implies the weak conjecture).<br />
<br />
:'''Strong conjecture with factoring''': Same as the original conjecture, but assume that one has a ''factoring oracle'' will return the factors of any number given to it (as a stream of bits) in unit time. (This oracle can be given "for free" if factoring is in P, but we can also assume the existence of this oracle even if factoring is not in P.)<br />
<br />
:'''Semi-weak conjecture with factoring''': Same as the semi-weak conjecture, but with a factoring oracle.<br />
<br />
:'''Weak conjecture with factoring''': Same as the weak conjecture, but with a factoring oracle. (Note that there are deterministic sieve algorithms, such as the quadratic sieve, which are believed to run in subexponential time <math>\exp(o(k))</math>, so this oracle is in some sense available "for free" for this problem assuming this belief.)<br />
<br />
The weak conjecture with factoring is the easiest of the six, and so perhaps one should focus on that one first.<br />
<br />
It is also of interest to see whether the conjecture becomes easier to solve assuming that P=BPP or P=BQP.<br />
<br />
== Partial results ==<br />
<br />
# [[P=NP implies a deterministic algorithm to find primes]]<br />
# [[An efficient algorithm exists if Cramer's conjecture holds]]<br />
# [[Finding primes with O(k) random bits|k-digit primes can be found with high probability using O(k) random bits]]<br />
## If [[Pseudo-random generators (PRG)|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.<br />
# The function field analogue (i.e. finding degree k irreducible polynomials over a finite field) is known [AL1986]<br />
## The analogue over the rationals is even easier: Eisenstein's criterion provides plenty of irreducible polynomials of degree k, e.g. <math>x^k-2</math>.<br />
# Assuming a suitably quantitative version of [[Schinzel's hypothesis H]] (namely, the Bateman-Horn conjecture), the weak conjecture is true, as one can simply search over all k-digit numbers of the form <math>n^d-2</math> (say) for any fixed d to give an algorithm that works in time <math>O(10^{k/d})</math>. By randomly sampling such integers, one also establishes the semi-weak conjecture (assuming that one has the expected density for primes in hypothesis H).<br />
# It's easy to deterministically find large square-free numbers; just multiply lots of small primes together. However, it is not known how to test a number for square-freeness deterministically and quickly (unless one has a factoring oracle, in which case it is trivial).<br />
## However, it's not so obvious how to find large pairs <math>n,n+1</math> of consecutive square-free numbers, though such pairs must exist by counting arguments (the density of square-free numbers is <math>6/\pi^2 \approx 60\%</math>). This could be a good variant problem.<br />
### It is conjectured that every element of [[Sylvester's sequence]] is square-free. If so, this solves the above problem.<br />
# 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>k^A</math>, then increment A from 1 onward, until one gets a hit.<br />
<br />
Here are the current "world records" for the fastest way to deterministically (and provably) obtain a k-digit prime (ignoring errors of <math>\exp(o(k))</math> in the run time):<br />
<br />
# <math>O(10^k)</math>: The trivial algorithm of testing each of the k-digit numbers in turn until one gets a hit.<br />
# <math>O(10^k)^{3/4}</math>: Test the k-digit numbers of the form <math>a^2+b^4</math> for primality (the [[Friedlander-Iwaniec theorem]] guarantees a hit for k large enough).<br />
# <math>O(10^k)^{2/3}</math>: Test the k-digit numbers of the form <math>a^3+2b^3</math> for primality (a hit is guaranteed for large k by a result of Heath-Brown).<br />
# <math>O(10^{k})^{6/11+\epsilon} (\approx O(10^{k})^{.5454})</math>assuming factoring oracle: Factor each number in the interval <math>[x^{12/11},x^{12/11}+x^{6/11+\epsilon}]</math>, one will find a prime prime factor of order x by [HB1995]. <br />
# <math>O(10^k)^{0.525}</math>: Test the k-digit numbers from, say, <math>10^k</math> onwards until one gets a hit (here we use the [BHP2001] bound on [[prime gaps]]).<br />
# <math>O(10^k)^{1/2}</math> assuming RH: Test the k-digit numbers from, say, <math>10^k</math> onwards until one gets a hit (here we use the RH bound on [[prime gaps]]).<br />
<br />
Note that if one can get <math>O(10^k)^{\varepsilon}</math> for each fixed <math>\varepsilon > 0</math>, then one has established the weak conjecture.<br />
<br />
A slight variant of the problem: assuming a factoring oracle, given an algorithm that runs in k steps, how large a prime is the algorithm ''guaranteed'' to produce in the ''worst-case'' scenario? (Note that this is very different from what the algorithm is ''heuristically'' predicted to produce in the ''average-case'' scenario.)<br />
<br />
Here is a simple algorithm that produces a prime larger than about <math>k \log k</math> in k steps, based on Euclid's proof of the infinitude of primes:<br />
<br />
* Initialise <math>p_1=2</math>.<br />
* Once <math>p_1,\ldots,p_{k-1}</math> are computed, define <math>p_k</math> to be the largest prime factor of <math>p_1 \ldots p_{k-1}+1</math>.<br />
<br />
This generates k distinct primes; the prime number theorem tells us that the k^th prime has size about <math>k \log k</math>, so at least one of the primes produced here has size at least <math>k \log k</math>.<br />
<br />
If one instead works with [[Sylvester's sequence]] <math>a_k = a_1 \ldots a_{k-1}+1</math>, then it is known [O1985] that the number of primes less than n that can divide any one of the <math>a_k</math> is <math>O( n / \log n \log \log \log n )</math> rather than <math>O(n/\log n)</math> (the prime number theorem bound). If we then factor the first k elements of this sequence, we must get a prime of size at least <math>k \log k \log \log \log k</math> or so.<br />
<br />
One can do better still by working with the Fermat numbers, <math>F_n = 2^{2^n}+1</math>. It is known [KLS2002] that the number of primes dividing any of the <math>F_n</math> is <math>O(\sqrt{n}/\log n)</math>, so in particular if we factor the first k Fermat numbers, we get a prime almost of size <math>k^2</math>. In fact, it's a classical result of Euler that the prime divisors of <math>F_n</math> are all at least <math>2^{n+2}+1</math>, so we can obtain a large prime simply by factoring a Fermat number.<br />
<br />
Assuming RH, one can find a prime larger than <math>k^2</math> in about k steps by the method indicated earlier (start at <math>k^2</math> and increment until one hits a prime). Unconditionally, one gets a prime larger than <math>k^{1/0.525}</math> by this method. Currently this is the world record.<br />
<br />
== Variants of the problem ==<br />
<br />
# 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.<br />
<br />
=== Finding consecutive (or nearby) square-free integers ===<br />
<br />
:'''Toy problem''' Is there an efficient algorithm to find consecutive square-free integers n, n+1 of at least k digits in length assuming an oracle to determine whether a number is square free (a special case of the factoring oracle)? Or just square-free integers that are close together (e.g. polylog(n)).<br />
<br />
Note that finding one large square-free number is easy: just multiply lots of distinct small primes together. Also, as the density of square-free numbers is <math>6/\pi^2 \approx 0.6</math>, a counting argument shows that pairs of consecutive square-free numbers exist in abundance, and are thus easy to find probabilistically. The density can be increased to arbitrarily close to 1 using the [[W-trick]], so one could also ask for, say, long arithmetic progressions of square-free numbers also.<br />
<br />
If [[Sylvester's sequence]] is square-free, then this solves the problem.<br />
<br />
Testing a number for square-freeness is trivial with a factoring oracle. No unconditional polynomial-time deterministic algorithm for square-freeness seems to be known. (It is listed as an open problem in [http://portal.acm.org/citation.cfm?id=749544 this paper from 1994].)<br />
<br />
Unconditionally, there are asymptotics for the number of square-free numbers in [1,N] with an error term of <math>O(N^{1/2})</math>, which leads to a <math>O(10^k)^{1/2}</math> algorithm (just search an interval of this length for square-freeness). This is the current unconditional world record. Assuming RH, this can be improved to <math>O(10^k)^{17/54+\varepsilon}</math>. <br />
<br />
There is an asymptotic [HB1984] for the number of consecutive square free numbers with an error term of <math>O(N^{7/11})</math>, leading to a <math>O(10^k)^{7/11+\varepsilon}</math>, though this is inferior to the above bounds.<br />
<br />
It is known [FT1992] that the interval <math>[N, N+N^{1/5+\epsilon}]</math> contains at least one square-free number; Granville [G1998] improved this to <math>[N,N+N^{\varepsilon}]</math> assuming the [[ABC conjecture]]. If the density in such intervals can be made to exceed 50% (perhaps after first applying the [[W-trick]]) then we would have solved the weak version of this toy problem assuming ABC.<br />
<br />
=== Finding pseudoprimes ===<br />
<br />
:'''Problem:''' How quickly can one find a solution to the congruence <math>2^{n-1}=1 \hbox{ mod } n</math> with n at least k digits in length? (a pseudoprime)?<br />
<br />
It is conjectured that the largest gap between k-digit pseudoprimes is poly(k) (this is weaker than [[Cramer's conjecture]], and would imply a polynomial time solution to the above problem).<br />
<br />
It is conjectured that the number <math>\mathcal{P}_a(x)</math> of pseudoprimes to any base <math>a \neq \pm1</math> satisfies<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) = \log(x) - \log(x)\frac{\log\log\log(x)}{\log\log(x)}(1+o(1)).</math><br />
<br />
However, the best known bounds seem to be<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) \leq \log(x) - \frac{1}{2}\log(x)\frac{\log\log\log(x)}{\log\log(x)}(1+o(1)),</math><br />
<br />
and<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) \geq (\frac{\log(x)}{\log a})^{E/(E+1)-o(1)},</math><br />
<br />
where E is a constant which is conjectured to equal 1, but is only known to have value at least 1-1/(2\sqrt{e}). These results can be found in [P1981], [P1982], [P1989]. Better bounds are known to hold on average [EP1986].<br />
<br />
If n is a pseudoprime, then <math>2^n-1</math> is also a pseudoprime (because <math>2^n = 1 \hbox{ mod } 2^n - 1 </math>, and <math>2^n-2</math> is a multiple of n). This, technically, solves the problem, but can we find denser sets of pseudoprimes? What if we want <math>2^{n-1}=1 \hbox{ mod } n</math> and <math>3^{n-1} = 1 \hbox{ mod } n</math> simultaneously?<br />
<br />
=== Finding Almost Primes===<br />
<br />
An almost primes is a number that is the product of at most two primes (counted with multiplicity). <br />
<br />
:'''problem''' How fast can we deterministically write down a <math>k</math> digit almost prime?<br />
<br />
Clearly this is a relaxation of the prime problem, so we expect to get better results. In [L1996] it is shown that the interval <math>[x,x+x^{.436}]</math> contains an almost prime. This gives us a <math>O(10^{k})^{.436}</math> algorithm. Assuming a factoring oracle, the problems of deterministically finding a <math>k</math> digit almost prime and a <math>k</math> digit prime in polynomial time are equivalent. If we can find an almost prime in polynomial time we can factor it and get (a slightly smaller) prime. Conversely, if we can find a prime in polynomial time we can square it to find (a slightly larger) almost prime. Using our prime technology this should give a <math>O(10^{k})^{.262}</math> algorithm.<br />
<br />
== Observations and strategies ==<br />
<br />
# 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>N^\varepsilon</math>-smooth (or <math>\log^{O(1)} N</math> smooth, if one only wants to solve the weak conjecture with factoring). <br />
## 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>\{ Wn+1: 1 \leq n \leq k^{100} \}</math> (say) is <math>k^A</math>-smooth, then one has found a prime with at least <math>A \log k</math> digits in polynomial time. If one can make A arbitrarily large, one has solved the baby problem with factoring.<br />
## One way to proceed is to analyse [[iterated sumsets of log-primes]].<br />
## Another is to analyse [[signed sums of prime reciprocals]].<br />
## Probably the best known bound along these lines is given in [HB1995] and states that the interval <math>[x,x+x^{.5+\epsilon}]</math> contains an integer with a prime factor at least <math>x^{11/12 -\epsilon}</math>. This only leads to a <math>O(10^{k})^{.5455}</math> algorithm.<br />
# Another approach is to accurately compute the [[prime counting function]].<br />
# If one can find explicitly enumerable sets of k-digit numbers of size <math>O(10^{\varepsilon k})</math> for any fixed <math>\varepsilon > 0</math> that are guaranteed to contain a prime, then one has solved the weak conjecture. If instead one can find randomly samplable sets of k-digit numbers of size <math>O(10^{\varepsilon k})</math> that contain a large fraction (e.g. <math>\exp(-o(k))</math> of primes), one has solved the semi-weak conjecture. If one can find explicit sets of poly(k) size that are guaranteed to contain a prime, one has solved the strong conjecture.<br />
# 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 [http://en.wikipedia.org/wiki/Pseudorandom_generators_for_polynomials 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.<br />
# If one can find a sequence of easily constructible, mutually coprime integers whose prime factors are contained in a sparse subset of the primes, this generates (with the aid of a factoring oracle) a sparse set of primes. So far the sparsest set of this type has come from factoring the Fermat numbers.<br />
<br />
== Negative results and other obstructions ==<br />
<br />
# 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>O(k^O(1))</math> smooth integer in any interval that can be searched in polynomial time. Indeed, there are heuristic arguments that suggest that even augmented with basic Fourier analysis and assuming RH, this method is unlikely to work, although they haven't yet been fully formalized.<br />
# 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.<br />
## In a similar spirit, one cannot hope to find non-smooth numbers in a short interval by analysing the iterated sumset of the log-primes and using average-case information about that set), because if one deletes all the primes arising from factors of that interval, one still captures most of the primes (and thus most of the average-case behaviour of the log-primes) while losing the information about that interval. <br />
# It is not possible to prove the conjecture purely by "soft" (i.e. relativisable) complexity theory methods which do not use any additional information on the primes rather than their density. Details are at [[Oracle counterexample to finding pseudoprimes]].<br />
<br />
== How could the conjecture be false? ==<br />
<br />
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:<br />
<br />
# 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>O(\log k)</math> that runs in time <math>k^{O(1)}</math>, are composite. [If the conjecture fails with factoring, then these numbers are furthermore <math>\exp(\varepsilon k)</math> smooth for any fixed <math>\varepsilon > 0</math>; if even the weak conjecture with factoring fails, they are <math>k^{O(1)}</math>-smooth.]<br />
# In fact, all constructible numbers are not only composite/smooth, but they sit inside intervals of length <math>k^{100}</math>, all of whose elements are composite/smooth. (One can replace 100 by any other fixed number.)<br />
## In particular, Cramer's conjecture fails; the gaps between adjacent k-digit primes exceeds <math>k^{100}</math> around every constructible number.<br />
# No pseudorandom number generators exist. In particular, this implies that one-way functions do not exist.<br />
# <math>P \neq NP</math>. More specifically, the decision problem "Does there exist a prime in a given interval?" is in [[The complexity class NP|NP]], but cannot lie in [[The complexity class P|P]] if the conjecture fails.<br />
<br />
== Relevant concepts ==<br />
<br />
Complexity theory concepts:<br />
<br />
# Complexity classes<br />
## [[The complexity class P|P]]<br />
## [[The complexity class NP|NP]]<br />
## [[The complexity class BPP|BPP]]<br />
## [[The complexity class promise-BPP|promise-BPP]]<br />
## [[The complexity class BQP|BQP]]<br />
## [[The complexity class DTIME|DTIME(f(n))]]<br />
# [[Pseudo-random generators (PRG)]]<br />
# [http://blog.computationalcomplexity.org/2006/07/full-derandomization.html Full derandomization]<br />
# [http://en.wikipedia.org/wiki/One-way_function one-way function]<br />
# [[Impagliazzo's five worlds]]: Algorithmica, Heuristica, Pessiland, Minicrypt, Cryptomania<br />
# [[Kolmogorov complexity]]<br />
# [http://en.wikipedia.org/wiki/Oracle_machine Oracles]<br />
<br />
Number theory concepts:<br />
<br />
# [[Cramer's random model for the primes]]<br />
# [[Prime gaps]]<br />
# [[Generic prime]]<br />
# [[Smooth number]]<br />
# The [[W-trick]]<br />
# [[Sylvester's sequence]]<br />
# [[Siegel zero]]<br />
# [http://en.wikipedia.org/wiki/Big_O_notation Asymptotic notation]<br />
# [[Fermat number]]<br />
# [[Pseudoprimes]]<br />
<br />
Other:<br />
<br />
# [http://en.wikipedia.org/wiki/Expander_graph Expander graphs]<br />
<br />
Note: articles with external links should eventually be replaced by in-house pages that can provide information that is more dedicated to this project.<br />
<br />
== Relevant conjectures ==<br />
<br />
# [[The complexity class NP|P=NP]]<br />
# [[The complexity class BPP|P=BPP]]<br />
# [[The complexity class promise-BPP|P=promise-BPP]]<br />
# [[The complexity class BQP|P=BQP]]<br />
# [[Pseudo-random generators (PRG)|existence of PRG]]<br />
# [http://en.wikipedia.org/wiki/One-way_function existence of one-way functions]<br />
# whether [[The complexity class DTIME|DTIME(2^n)]] has subexponential circuits<br />
# [http://en.wikipedia.org/wiki/Riemann_hypothesis The Riemann Hypothesis (RH)]<br />
## [http://en.wikipedia.org/wiki/Generalized_Riemann_hypothesis The generalised Riemann Hypothesis (GRH)]<br />
# the [[Hardy-Littlewood prime tuples conjecture]]<br />
# the [[ABC conjecture]]<br />
# [[Cramer's conjecture]]<br />
# [[Schinzel's hypothesis H]]<br />
# [[discrete logarithm|discrete log in P]]<br />
# [[factoring|factoring in P]]<br />
<br />
== Relevant results ==<br />
<br />
# [[Brun-Titchmarsh inequality]]<br />
# [[Erdos-Kac theorem]]<br />
# [[Bertrand's postulate]]<br />
# [[Friedlander-Iwaniec theorem]]<br />
# [[List of results implied by the Riemann Hypothesis|Conditional on the Riemann hypothesis]]<br />
<br />
== Relevant papers ==<br />
<br />
* [AMcC1994] L. Adelman, K. McCurley, [http://portal.acm.org/citation.cfm?id=749544 Open problems in number theoretic complexity, II], Lecture Notes In Computer Science; Vol. 877, Proceedings of the First International Symposium on Algorithmic Number Theory 291 - 322 (1994)<br />
* [AL1986] L. Adelman, H. Lenstra, [http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf Finding irreducible polynomials over finite fields], Proc. 18th Annual ACM Symp. on Theory of Computing (STOC), Berkeley, May 28–30, 350–355.<br />
* [B1990] E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), 355-380], <br />
* [BH1996] R. C. Baker and G. Harman, “The difference between consecutive primes,” Proc. Lond. Math. Soc., series 3, 72 (1996) 261–280. <br />
*[BH1998] R. C. Baker, G. Harmen, Shifted primes without large prime factors, Acta Arith. 83 (1998), no. 4, 331–361<br />
* [BHP2001] R. C. Baker, G. Harman and J. Pintz, The difference between consecutive primes, II, Proceedings of the London Mathematical Society 83, (2001), 532–562.<br />
* [BH1998] A. Balog, T. Wooley, “[http://www.austms.org.au/Publ/JAustMS/V64P2/abs/c30/ On strings of consecutive integers with no large prime factors]”, J. Austral. Math. Soc. Ser. A 64 (1998), no. 2, 266–276<br />
* [C2006] T. H. Chan, [http://arxiv.org/abs/math/0502199 Finding almost squares]. Acta Arith. 121 (2006), no. 3, 221--232.<br />
* [D1998] P. Dusart, [http://www.unilim.fr/laco/theses/1998/T1998_01.html Autour de la fonction qui compte le nombre de nombres premiers], 1998<br />
* [E1949] P. Erdős, [http://www.math-inst.hu/~p_erdos/1949-07.pdf On The Converse of Fermat's Theorem]<br />
* [EP1986] P. Erdős and C. Pomerance, On the number of false witnesses for a composite number, Math. Comp. 46 (1986), 259-279.<br />
* [FT????] M. Filaseta, O. Trifonov, [http://books.google.com/books?id=G02moOmuOX4C&pg=PA235&dq=squarefree+numbers#v=onepage&q=squarefree%20numbers&f=false On gaps between squarefree numbers], Analytic number theory: Proceedings of a conference in honor of Paul Bateman <br />
* [FT1992] M. Filaseta and O. Trifonov, On gaps between squarefree numbers. II, J. London Math. Soc. (2), 45 (1992), no. 2, 215-221. <br />
* [GW2002] O. Goldreich, A. Wigderson, [http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GW02/gw02.pdf Derandomization that is rarely wrong from short advice that is typically good]<br />
* [G1998] A. Granville, ABC allows us to count squarefrees, Internat. Math. Res. Notices (1998), no. 19, 991–1009.<br />
* [G1995] A. Granville, [http://www.dartmouth.edu/~chance/chance_news/for_chance_news/Riemann/cramer.pdf "Harald Cramér and the distribution of prime numbers"], Scandinavian Actuarial J. 1 (1995), 12—28. <br />
* [HB1984] D.R. Heath-Brown, The square sieve and consecutive square-free numbers, Math. Ann. 266 (1984), 251-259<br />
* [HB1995] D.R. Heath-Brown, The largest prime factor of integers in an interval, Science in China ???<br />
* [IW1997] 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.<br />
* [J2006] R. Jones, [http://arxiv.org/abs/math/0612415 The density of prime divisors in the arithmetic dynamics of quadratic polynomials]<br />
* [KLS2002] Křížek, Luca and Somer, On the convergence of series of reciprocals of primes related to the Fermat numbers, J. Number Theory 97(2002), 95–112<br />
* [L1979] H.W. Lenstra, [https://openaccess.leidenuniv.nl/bitstream/1887/3801/1/346_036.pdf Miller's Primality Test], Information Processing Letters, 1979<br />
* [L1996] H. Liu, Almost primes in short intervals. J. Number Theory 57 (1996), no. 2, 303--322.<br />
* [LW1999] H. Liu, J. Wu, Numbers with a large prime factor, Acta Arith. 89 (1999), no. 2, 163–187.<br />
* [M1994] U. Maurer, [http://eprints.kfupm.edu.sa/40655/ Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters], Journal of Cryptology 8 (1994), 123-155<br />
* [O1985] Odoni, On the prime divisors of the sequence <math>w_n+1 = 1+ w_1 \ldots w_n</math>. J. London Math. Soc. (2), 32(1):1–11, 1985. <br />
* [P????] F. Pappalardi, [http://www.mat.uniroma3.it/users/pappa/papers/allahabad2003.pdf A survey on k-freeness]<br />
* [P1981] C. Pomerance, [http://math.dartmouth.edu/~carlp/PDF/paper32.pdf On the distribution of pseudoprimes, Math. Comp. 37 (1981), 587-593.]<br />
* [P1982] C. Pomerance, [http://math.dartmouth.edu/~carlp/PDF/lower.pdf A new lower bound for the pseudoprime counting function, Illinois J. Math. 26 (1982), 4-9.]<br />
* [P1989] C. Pomerance, Two methods in elementary analytic number theory, Number theory and applications, R. A. Mollin, ed., Kluwer Academic Publishers, Dordrecht, 1989, pp. 135-161.<br />
<br />
* [S2006] K. Soundararajan, [http://arxiv.org/abs/math/0606408 The distribution of the primes] (survey)<br />
* [S2006b] K. Soundararajan, [http://arxiv.org/abs/math/0605696 Small gaps between prime numbers: The work of Goldston-Pintz-Yildirim]<br />
* [T2006] L. Trevisan, [http://arxiv.org/abs/cs.CC/0601100 Pseudorandomness and Combinatorial Constructions]<br />
<br />
Please help out by adding links or completing references, or adding further references to the list above!<br />
<br />
== External links ==<br />
<br />
# [http://qwiki.stanford.edu/wiki/Complexity_Zoo Complexity Zoo]<br />
# "[http://blog.computationalcomplexity.org/2009/08/finding-primes.html Finding Primes]", Lance Fortnow, August 4 2009</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Finding_primesFinding primes2009-08-19T23:21:57Z<p>Asdf: add a pdf link</p>
<hr />
<div>This is the main wiki page for the Polymath4 project "[http://en.wordpress.com/tag/finding-primes/ Finding primes]".<br />
<br />
The main aim of the project is to resolve the following conjecture:<br />
<br />
:'''(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.<br />
<br />
Since primality is known to be in [[The complexity class P|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.<br />
<br />
Contributions and corrections to this wiki page (and its subpages) are very welcome.<br />
<br />
== Threads ==<br />
<br />
# [http://polymathprojects.org/2009/07/27/proposal-deterministic-way-to-find-primes/ Proposal for the project and initial research thread] (Inactive)<br />
# [http://polymathprojects.org/2009/08/09/research-thread-ii-deterministic-way-to-find-primes/ Research thread II] (Inactive)<br />
# [http://polymathprojects.org/2009/08/13/research-thread-iii-determinstic-way-to-find-primes/ Research thread III] (Active)<br />
# [http://polymathprojects.org/2009/07/28/deterministic-way-to-find-primes-discussion-thread/ The current discussion thread] (Active)<br />
<br />
== Easier versions of the problem ==<br />
<br />
:'''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 [[Finding primes with O(k) random bits|one can do this with O(k) random bits]]; and if one can use just <math>O(\log k)</math> random bits, one is done by exhausting over the random bits.)<br />
<br />
One way to solve the semi-weak conjecture would be to find an "explorable" set of size <math>\exp(o(k))</math> of integers, a significant fraction (at least <math>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).<br />
<br />
:'''Weak conjecture''': There exists a deterministic algorithm, which, when given an integer k, is guaranteed to find a prime of at least <math>\omega(\log k)</math> digits in length in time polynomial in k, where <math>\omega(\log k)</math> grows faster than <math>\log k</math> as <math>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>\exp(o(k))</math>. Note that the semi-weak conjecture implies the weak conjecture).<br />
<br />
:'''Strong conjecture with factoring''': Same as the original conjecture, but assume that one has a ''factoring oracle'' will return the factors of any number given to it (as a stream of bits) in unit time. (This oracle can be given "for free" if factoring is in P, but we can also assume the existence of this oracle even if factoring is not in P.)<br />
<br />
:'''Semi-weak conjecture with factoring''': Same as the semi-weak conjecture, but with a factoring oracle.<br />
<br />
:'''Weak conjecture with factoring''': Same as the weak conjecture, but with a factoring oracle. (Note that there are deterministic sieve algorithms, such as the quadratic sieve, which are believed to run in subexponential time <math>\exp(o(k))</math>, so this oracle is in some sense available "for free" for this problem assuming this belief.)<br />
<br />
The weak conjecture with factoring is the easiest of the six, and so perhaps one should focus on that one first.<br />
<br />
It is also of interest to see whether the conjecture becomes easier to solve assuming that P=BPP or P=BQP.<br />
<br />
== Partial results ==<br />
<br />
# [[P=NP implies a deterministic algorithm to find primes]]<br />
# [[An efficient algorithm exists if Cramer's conjecture holds]]<br />
# [[Finding primes with O(k) random bits|k-digit primes can be found with high probability using O(k) random bits]]<br />
## If [[Pseudo-random generators (PRG)|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.<br />
# The function field analogue (i.e. finding degree k irreducible polynomials over a finite field) is known [AL1986]<br />
## The analogue over the rationals is even easier: Eisenstein's criterion provides plenty of irreducible polynomials of degree k, e.g. <math>x^k-2</math>.<br />
# Assuming a suitably quantitative version of [[Schinzel's hypothesis H]] (namely, the Bateman-Horn conjecture), the weak conjecture is true, as one can simply search over all k-digit numbers of the form <math>n^d-2</math> (say) for any fixed d to give an algorithm that works in time <math>O(10^{k/d})</math>. By randomly sampling such integers, one also establishes the semi-weak conjecture (assuming that one has the expected density for primes in hypothesis H).<br />
# It's easy to deterministically find large square-free numbers; just multiply lots of small primes together. However, it is not known how to test a number for square-freeness deterministically and quickly (unless one has a factoring oracle, in which case it is trivial).<br />
## However, it's not so obvious how to find large pairs <math>n,n+1</math> of consecutive square-free numbers, though such pairs must exist by counting arguments (the density of square-free numbers is <math>6/\pi^2 \approx 60\%</math>). This could be a good variant problem.<br />
### It is conjectured that every element of [[Sylvester's sequence]] is square-free. If so, this solves the above problem.<br />
# 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>k^A</math>, then increment A from 1 onward, until one gets a hit.<br />
<br />
Here are the current "world records" for the fastest way to deterministically (and provably) obtain a k-digit prime (ignoring errors of <math>\exp(o(k))</math> in the run time):<br />
<br />
# <math>O(10^k)</math>: The trivial algorithm of testing each of the k-digit numbers in turn until one gets a hit.<br />
# <math>O(10^k)^{3/4}</math>: Test the k-digit numbers of the form <math>a^2+b^4</math> for primality (the [[Friedlander-Iwaniec theorem]] guarantees a hit for k large enough).<br />
# <math>O(10^k)^{2/3}</math>: Test the k-digit numbers of the form <math>a^3+2b^3</math> for primality (a hit is guaranteed for large k by a result of Heath-Brown).<br />
# <math>O(10^{k})^{6/11+\epsilon} (\approx O(10^{k})^{.5454})</math>assuming factoring oracle: Factor each number in the interval <math>[x^{12/11},x^{12/11}+x^{6/11+\epsilon}]</math>, one will find a prime prime factor of order x by [HB1995]. <br />
# <math>O(10^k)^{0.525}</math>: Test the k-digit numbers from, say, <math>10^k</math> onwards until one gets a hit (here we use the [BHP2001] bound on [[prime gaps]]).<br />
# <math>O(10^k)^{1/2}</math> assuming RH: Test the k-digit numbers from, say, <math>10^k</math> onwards until one gets a hit (here we use the RH bound on [[prime gaps]]).<br />
<br />
Note that if one can get <math>O(10^k)^{\varepsilon}</math> for each fixed <math>\varepsilon > 0</math>, then one has established the weak conjecture.<br />
<br />
A slight variant of the problem: assuming a factoring oracle, given an algorithm that runs in k steps, how large a prime is the algorithm ''guaranteed'' to produce in the ''worst-case'' scenario? (Note that this is very different from what the algorithm is ''heuristically'' predicted to produce in the ''average-case'' scenario.)<br />
<br />
Here is a simple algorithm that produces a prime larger than about <math>k \log k</math> in k steps, based on Euclid's proof of the infinitude of primes:<br />
<br />
* Initialise <math>p_1=2</math>.<br />
* Once <math>p_1,\ldots,p_{k-1}</math> are computed, define <math>p_k</math> to be the largest prime factor of <math>p_1 \ldots p_{k-1}+1</math>.<br />
<br />
This generates k distinct primes; the prime number theorem tells us that the k^th prime has size about <math>k \log k</math>, so at least one of the primes produced here has size at least <math>k \log k</math>.<br />
<br />
If one instead works with [[Sylvester's sequence]] <math>a_k = a_1 \ldots a_{k-1}+1</math>, then it is known [O1985] that the number of primes less than n that can divide any one of the <math>a_k</math> is <math>O( n / \log n \log \log \log n )</math> rather than <math>O(n/\log n)</math> (the prime number theorem bound). If we then factor the first k elements of this sequence, we must get a prime of size at least <math>k \log k \log \log \log k</math> or so.<br />
<br />
One can do better still by working with the Fermat numbers, <math>F_n = 2^{2^n}+1</math>. It is known [KLS2002] that the number of primes dividing any of the <math>F_n</math> is <math>O(\sqrt{n}/\log n)</math>, so in particular if we factor the first k Fermat numbers, we get a prime almost of size <math>k^2</math>. In fact, it's a classical result of Euler that the prime divisors of <math>F_n</math> are all at least <math>2^{n+2}+1</math>, so we can obtain a large prime simply by factoring a Fermat number.<br />
<br />
Assuming RH, one can find a prime larger than <math>k^2</math> in about k steps by the method indicated earlier (start at <math>k^2</math> and increment until one hits a prime). Unconditionally, one gets a prime larger than <math>k^{1/0.525}</math> by this method. Currently this is the world record.<br />
<br />
== Variants of the problem ==<br />
<br />
# 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.<br />
<br />
=== Finding consecutive (or nearby) square-free integers ===<br />
<br />
:'''Toy problem''' Is there an efficient algorithm to find consecutive square-free integers n, n+1 of at least k digits in length assuming an oracle to determine whether a number is square free (a special case of the factoring oracle)? Or just square-free integers that are close together (e.g. polylog(n)).<br />
<br />
Note that finding one large square-free number is easy: just multiply lots of distinct small primes together. Also, as the density of square-free numbers is <math>6/\pi^2 \approx 0.6</math>, a counting argument shows that pairs of consecutive square-free numbers exist in abundance, and are thus easy to find probabilistically. The density can be increased to arbitrarily close to 1 using the [[W-trick]], so one could also ask for, say, long arithmetic progressions of square-free numbers also.<br />
<br />
If [[Sylvester's sequence]] is square-free, then this solves the problem.<br />
<br />
Testing a number for square-freeness is trivial with a factoring oracle. No unconditional polynomial-time deterministic algorithm for square-freeness seems to be known. (It is listed as an open problem in [http://portal.acm.org/citation.cfm?id=749544 this paper from 1994].)<br />
<br />
Unconditionally, there are asymptotics for the number of square-free numbers in [1,N] with an error term of <math>O(N^{1/2})</math>, which leads to a <math>O(10^k)^{1/2}</math> algorithm (just search an interval of this length for square-freeness). This is the current unconditional world record. Assuming RH, this can be improved to <math>O(10^k)^{17/54+\varepsilon}</math>. <br />
<br />
There is an asymptotic [HB1984] for the number of consecutive square free numbers with an error term of <math>O(N^{7/11})</math>, leading to a <math>O(10^k)^{7/11+\varepsilon}</math>, though this is inferior to the above bounds.<br />
<br />
It is known [FT1992] that the interval <math>[N, N+N^{1/5+\epsilon}]</math> contains at least one square-free number; Granville [G1998] improved this to <math>[N,N+N^{\varepsilon}]</math> assuming the [[ABC conjecture]]. If the density in such intervals can be made to exceed 50% (perhaps after first applying the [[W-trick]]) then we would have solved the weak version of this toy problem assuming ABC.<br />
<br />
=== Finding pseudoprimes ===<br />
<br />
:'''Problem:''' How quickly can one find a solution to the congruence <math>2^{n-1}=1 \hbox{ mod } n</math> with n at least k digits in length? (a pseudoprime)?<br />
<br />
It is conjectured that the largest gap between k-digit pseudoprimes is poly(k) (this is weaker than [[Cramer's conjecture]], and would imply a polynomial time solution to the above problem).<br />
<br />
It is conjectured that the number <math>\mathcal{P}_a(x)</math> of pseudoprimes to any base <math>a \neq \pm1</math> satisfies<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) = \log(x) - \log(x)\frac{\log\log\log(x)}{\log\log(x)}(1+o(1)).</math><br />
<br />
However, the best known bounds seem to be<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) \leq \log(x) - \frac{1}{2}\log(x)\frac{\log\log\log(x)}{\log\log(x)}(1+o(1)),</math><br />
<br />
and<br />
<br />
:<math>\displaystyle \log\mathcal{P}_a(x) \geq (\frac{\log(x)}{\log a})^{E/(E+1)-o(1)},</math><br />
<br />
where E is a constant which is conjectured to equal 1, but is only known to have value at least 1-1/(2\sqrt{e}). These results can be found in [P1981], [P1982], [P1989]. Better bounds are known to hold on average [EP1986].<br />
<br />
If n is a pseudoprime, then <math>2^n-1</math> is also a pseudoprime (because <math>2^n = 1 \hbox{ mod } 2^n - 1 </math>, and <math>2^n-2</math> is a multiple of n). This, technically, solves the problem, but can we find denser sets of pseudoprimes? What if we want <math>2^{n-1}=1 \hbox{ mod } n</math> and <math>3^{n-1} = 1 \hbox{ mod } n</math> simultaneously?<br />
<br />
=== Finding Almost Primes===<br />
<br />
An almost primes is a number that is the product of at most two primes (counted with multiplicity). <br />
<br />
:'''problem''' How fast can we deterministically write down a <math>k</math> digit almost prime?<br />
<br />
Clearly this is a relaxation of the prime problem, so we expect to get better results. In [L1996] it is shown that the interval <math>[x,x+x^{.436}]</math> contains an almost prime. This gives us a <math>O(10^{k})^{.436}</math> algorithm. Assuming a factoring oracle, the problems of deterministically finding a <math>k</math> digit almost prime and a <math>k</math> digit prime in polynomial time are equivalent. If we can find an almost prime in polynomial time we can factor it and get (a slightly smaller) prime. Conversely, if we can find a prime in polynomial time we can square it to find (a slightly larger) almost prime. Using our prime technology this should give a <math>O(10^{k})^{.262}</math> algorithm.<br />
<br />
== Observations and strategies ==<br />
<br />
# 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>N^\varepsilon</math>-smooth (or <math>\log^{O(1)} N</math> smooth, if one only wants to solve the weak conjecture with factoring). <br />
## 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>\{ Wn+1: 1 \leq n \leq k^{100} \}</math> (say) is <math>k^A</math>-smooth, then one has found a prime with at least <math>A \log k</math> digits in polynomial time. If one can make A arbitrarily large, one has solved the baby problem with factoring.<br />
## One way to proceed is to analyse [[iterated sumsets of log-primes]].<br />
## Another is to analyse [[signed sums of prime reciprocals]].<br />
## Probably the best known bound along these lines is given in [HB1995] and states that the interval <math>[x,x+x^{.5+\epsilon}]</math> contains an integer with a prime factor at least <math>x^{11/12 -\epsilon}</math>. This only leads to a <math>O(10^{k})^{.5455}</math> algorithm.<br />
# Another approach is to accurately compute the [[prime counting function]].<br />
# If one can find explicitly enumerable sets of k-digit numbers of size <math>O(10^{\varepsilon k})</math> for any fixed <math>\varepsilon > 0</math> that are guaranteed to contain a prime, then one has solved the weak conjecture. If instead one can find randomly samplable sets of k-digit numbers of size <math>O(10^{\varepsilon k})</math> that contain a large fraction (e.g. <math>\exp(-o(k))</math> of primes), one has solved the semi-weak conjecture. If one can find explicit sets of poly(k) size that are guaranteed to contain a prime, one has solved the strong conjecture.<br />
# 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 [http://en.wikipedia.org/wiki/Pseudorandom_generators_for_polynomials 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.<br />
# If one can find a sequence of easily constructible, mutually coprime integers whose prime factors are contained in a sparse subset of the primes, this generates (with the aid of a factoring oracle) a sparse set of primes. So far the sparsest set of this type has come from factoring the Fermat numbers.<br />
<br />
== Negative results and other obstructions ==<br />
<br />
# 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>O(k^O(1))</math> smooth integer in any interval that can be searched in polynomial time. Indeed, there are heuristic arguments that suggest that even augmented with basic Fourier analysis and assuming RH, this method is unlikely to work, although they haven't yet been fully formalized.<br />
# 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.<br />
## In a similar spirit, one cannot hope to find non-smooth numbers in a short interval by analysing the iterated sumset of the log-primes and using average-case information about that set), because if one deletes all the primes arising from factors of that interval, one still captures most of the primes (and thus most of the average-case behaviour of the log-primes) while losing the information about that interval. <br />
# It is not possible to prove the conjecture purely by "soft" (i.e. relativisable) complexity theory methods which do not use any additional information on the primes rather than their density. Details are at [[Oracle counterexample to finding pseudoprimes]].<br />
<br />
== How could the conjecture be false? ==<br />
<br />
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:<br />
<br />
# 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>O(\log k)</math> that runs in time <math>k^{O(1)}</math>, are composite. [If the conjecture fails with factoring, then these numbers are furthermore <math>\exp(\varepsilon k)</math> smooth for any fixed <math>\varepsilon > 0</math>; if even the weak conjecture with factoring fails, they are <math>k^{O(1)}</math>-smooth.]<br />
# In fact, all constructible numbers are not only composite/smooth, but they sit inside intervals of length <math>k^{100}</math>, all of whose elements are composite/smooth. (One can replace 100 by any other fixed number.)<br />
## In particular, Cramer's conjecture fails; the gaps between adjacent k-digit primes exceeds <math>k^{100}</math> around every constructible number.<br />
# No pseudorandom number generators exist. In particular, this implies that one-way functions do not exist.<br />
# <math>P \neq NP</math>. More specifically, the decision problem "Does there exist a prime in a given interval?" is in [[The complexity class NP|NP]], but cannot lie in [[The complexity class P|P]] if the conjecture fails.<br />
<br />
== Relevant concepts ==<br />
<br />
Complexity theory concepts:<br />
<br />
# Complexity classes<br />
## [[The complexity class P|P]]<br />
## [[The complexity class NP|NP]]<br />
## [[The complexity class BPP|BPP]]<br />
## [[The complexity class promise-BPP|promise-BPP]]<br />
## [[The complexity class BQP|BQP]]<br />
## [[The complexity class DTIME|DTIME(f(n))]]<br />
# [[Pseudo-random generators (PRG)]]<br />
# [http://blog.computationalcomplexity.org/2006/07/full-derandomization.html Full derandomization]<br />
# [http://en.wikipedia.org/wiki/One-way_function one-way function]<br />
# [[Impagliazzo's five worlds]]: Algorithmica, Heuristica, Pessiland, Minicrypt, Cryptomania<br />
# [[Kolmogorov complexity]]<br />
# [http://en.wikipedia.org/wiki/Oracle_machine Oracles]<br />
<br />
Number theory concepts:<br />
<br />
# [[Cramer's random model for the primes]]<br />
# [[Prime gaps]]<br />
# [[Generic prime]]<br />
# [[Smooth number]]<br />
# The [[W-trick]]<br />
# [[Sylvester's sequence]]<br />
# [[Siegel zero]]<br />
# [http://en.wikipedia.org/wiki/Big_O_notation Asymptotic notation]<br />
# [[Fermat number]]<br />
# [[Pseudoprimes]]<br />
<br />
Other:<br />
<br />
# [http://en.wikipedia.org/wiki/Expander_graph Expander graphs]<br />
<br />
Note: articles with external links should eventually be replaced by in-house pages that can provide information that is more dedicated to this project.<br />
<br />
== Relevant conjectures ==<br />
<br />
# [[The complexity class NP|P=NP]]<br />
# [[The complexity class BPP|P=BPP]]<br />
# [[The complexity class promise-BPP|P=promise-BPP]]<br />
# [[The complexity class BQP|P=BQP]]<br />
# [[Pseudo-random generators (PRG)|existence of PRG]]<br />
# [http://en.wikipedia.org/wiki/One-way_function existence of one-way functions]<br />
# whether [[The complexity class DTIME|DTIME(2^n)]] has subexponential circuits<br />
# [http://en.wikipedia.org/wiki/Riemann_hypothesis The Riemann Hypothesis (RH)]<br />
## [http://en.wikipedia.org/wiki/Generalized_Riemann_hypothesis The generalised Riemann Hypothesis (GRH)]<br />
# the [[Hardy-Littlewood prime tuples conjecture]]<br />
# the [[ABC conjecture]]<br />
# [[Cramer's conjecture]]<br />
# [[Schinzel's hypothesis H]]<br />
# [[discrete logarithm|discrete log in P]]<br />
# [[factoring|factoring in P]]<br />
<br />
== Relevant results ==<br />
<br />
# [[Brun-Titchmarsh inequality]]<br />
# [[Erdos-Kac theorem]]<br />
# [[Bertrand's postulate]]<br />
# [[Friedlander-Iwaniec theorem]]<br />
# [[List of results implied by the Riemann Hypothesis|Conditional on the Riemann hypothesis]]<br />
<br />
== Relevant papers ==<br />
<br />
* [AMcC1994] L. Adelman, K. McCurley, [http://portal.acm.org/citation.cfm?id=749544 Open problems in number theoretic complexity, II], Lecture Notes In Computer Science; Vol. 877, Proceedings of the First International Symposium on Algorithmic Number Theory 291 - 322 (1994)<br />
* [AL1986] L. Adelman, H. Lenstra, [http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf Finding irreducible polynomials over finite fields], Proc. 18th Annual ACM Symp. on Theory of Computing (STOC), Berkeley, May 28–30, 350–355.<br />
* [B1990] E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), 355-380], <br />
* [BH1996] R. C. Baker and G. Harman, “The difference between consecutive primes,” Proc. Lond. Math. Soc., series 3, 72 (1996) 261–280. <br />
*[BH1998] R. C. Baker, G. Harmen, Shifted primes without large prime factors, Acta Arith. 83 (1998), no. 4, 331–361<br />
* [BHP2001] R. C. Baker, G. Harman and J. Pintz, The difference between consecutive primes, II, Proceedings of the London Mathematical Society 83, (2001), 532–562.<br />
* [BH1998] A. Balog, T. Wooley, “[http://www.austms.org.au/Publ/JAustMS/V64P2/abs/c30/ On strings of consecutive integers with no large prime factors]”, J. Austral. Math. Soc. Ser. A 64 (1998), no. 2, 266–276<br />
* [C2006] T. H. Chan, [http://arxiv.org/abs/math/0502199, Finding almost squares]. Acta Arith. 121 (2006), no. 3, 221--232.<br />
* [D1998] P. Dusart, [http://www.unilim.fr/laco/theses/1998/T1998_01.html Autour de la fonction qui compte le nombre de nombres premiers], 1998<br />
* [E1949] P. Erdős, [http://www.math-inst.hu/~p_erdos/1949-07.pdf, On The Converse of Fermat's Theorem]<br />
* [EP1986] P. Erdős and C. Pomerance, On the number of false witnesses for a composite number, Math. Comp. 46 (1986), 259-279.<br />
* [FT????] M. Filaseta, O. Trifonov, [http://books.google.com/books?id=G02moOmuOX4C&pg=PA235&dq=squarefree+numbers#v=onepage&q=squarefree%20numbers&f=false On gaps between squarefree numbers], Analytic number theory: Proceedings of a conference in honor of Paul Bateman <br />
* [FT1992] M. Filaseta and O. Trifonov, On gaps between squarefree numbers. II, J. London Math. Soc. (2), 45 (1992), no. 2, 215-221. <br />
* [GW2002] O. Goldreich, A. Wigderson, [http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GW02/gw02.pdf Derandomization that is rarely wrong from short advice that is typically good]<br />
* [G1998] A. Granville, ABC allows us to count squarefrees, Internat. Math. Res. Notices (1998), no. 19, 991–1009.<br />
* [G1995] A. Granville, [http://www.dartmouth.edu/~chance/chance_news/for_chance_news/Riemann/cramer.pdf "Harald Cramér and the distribution of prime numbers"], Scandinavian Actuarial J. 1 (1995), 12—28. <br />
* [HB1984] D.R. Heath-Brown, The square sieve and consecutive square-free numbers, Math. Ann. 266 (1984), 251-259<br />
* [HB1995] D.R. Heath-Brown, The largest prime factor of integers in an interval, Science in China ???<br />
* [IW1997] 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.<br />
* [J2006] R. Jones, [http://arxiv.org/abs/math/0612415, The density of prime divisors in the arithmetic dynamics of quadratic polynomials]<br />
* [KLS2002] Křížek, Luca and Somer, On the convergence of series of reciprocals of primes related to the Fermat numbers, J. Number Theory 97(2002), 95–112<br />
* [L1979] H.W. Lenstra, [https://openaccess.leidenuniv.nl/bitstream/1887/3801/1/346_036.pdf, Miller's Primality Test], Information Processing Letters, 1979<br />
* [L1996] H. Liu, Almost primes in short intervals. J. Number Theory 57 (1996), no. 2, 303--322.<br />
* [LW1999] H. Liu, J. Wu, Numbers with a large prime factor, Acta Arith. 89 (1999), no. 2, 163–187.<br />
* [M1994] U. Maurer, [http://eprints.kfupm.edu.sa/40655/ Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters], Journal of Cryptology 8 (1994), 123-155<br />
* [O1985] Odoni, On the prime divisors of the sequence <math>w_n+1 = 1+ w_1 \ldots w_n</math>. J. London Math. Soc. (2), 32(1):1–11, 1985. <br />
* [P????] F. Pappalardi, [http://www.mat.uniroma3.it/users/pappa/papers/allahabad2003.pdf, A survey on k-freeness]<br />
* [P1981] C. Pomerance, [http://math.dartmouth.edu/~carlp/PDF/paper32.pdf, On the distribution of pseudoprimes, Math. Comp. 37 (1981), 587-593.]<br />
* [P1982] C. Pomerance, [http://math.dartmouth.edu/~carlp/PDF/lower.pdf, A new lower bound for the pseudoprime counting function, Illinois J. Math. 26 (1982), 4-9.]<br />
* [P1989] C. Pomerance, Two methods in elementary analytic number theory, Number theory and applications, R. A. Mollin, ed., Kluwer Academic Publishers, Dordrecht, 1989, pp. 135-161.<br />
<br />
* [S2006] K. Soundararajan, [http://arxiv.org/abs/math/0606408 The distribution of the primes] (survey)<br />
* [S2006b] K. Soundararajan, [http://arxiv.org/abs/math/0605696 Small gaps between prime numbers: The work of Goldston-Pintz-Yildirim]<br />
* [T2006] L. Trevisan, [http://arxiv.org/abs/cs.CC/0601100 Pseudorandomness and Combinatorial Constructions]<br />
<br />
Please help out by adding links or completing references, or adding further references to the list above!<br />
<br />
== External links ==<br />
<br />
# [http://qwiki.stanford.edu/wiki/Complexity_Zoo Complexity Zoo]<br />
# "[http://blog.computationalcomplexity.org/2009/08/finding-primes.html Finding Primes]", Lance Fortnow, August 4 2009</div>Asdfhttp://michaelnielsen.org/polymath1/index.php?title=Oracle_counterexample_to_finding_pseudoprimesOracle counterexample to finding pseudoprimes2009-08-05T23:37:27Z<p>Asdf: change an instance of $latex ...$ to <math> ... </math></p>
<hr />
<div>One can consider the following soft generalisation to the [[finding primes]] conjecture:<br />
<br />
:'''Soft conjecture''' Suppose one has a set S of integers which is in P, and which is at least as dense at the primes (thus the set of k-digit elements of S has density <math>\gg 1/k</math>. Then there exists a deterministic algorithm which, when given an integer k, will produce an element of S of at least k digits in length in time poly(k).<br />
<br />
This soft conjecture is for instance true if P=NP, by [[P=NP implies a deterministic algorithm to find primes|this argument]]. It certainly implies the finding primes conjecture, by taking S to be the set of primes. However, we show here that the soft conjecture fails in the presence of an oracle. Roughly speaking, this means that there is no "soft" way to prove the finding primes conjecture that uses nothing about the primes other than that they are in P and are dense.<br />
<br />
Here's how it works. For each integer k, we recursively define the set <math>S_k</math> to be the set of k-digit numbers whose Kolmogorov complexity is at least <math>\sqrt{k}</math> relative to <math>S_1,\ldots,S_{k-1}</math>. What this means is that n lies in <math>S_k</math> if n has k digits and it is not possible to find a Turing machine of length less than <math>\sqrt{k}</math> that can compute n even given access to oracles for <math>S_1,\ldots,S_{k-1}</math>. An easy counting argument shows that all but at most <math>2^{\sqrt{k}}</math> k-digit integers lie in <math>S_k</math>. Thus if we set S to be the union of the <math>S_k</math>, then S is at least as dense as the primes (in fact it is much, much denser).<br />
<br />
We now work relative to an oracle for S, i.e. the oracle takes any number n as input and returns whether it is in S in unit time. Clearly, S is now in P. Suppose for contradiction that there was an algorithm A (of length O(1)) which, when given k as input, returns an element of S at least k digits in length in time poly(k). <br />
<br />
Let k be large. One can show inductively that every integer of k digits or more produced by the algorithm A with input k in time less than poly(k) has a Kolmogorov complexity of O( log(k) ) relative to <math>S_1,\ldots,S_{k-1}</math>; the point is that the oracles for <math>S_k, S_{k+1},\ldots,</math> can be shown by induction to be useless as the numbers produced by A will never lie in these sets. But O(log(k)) is less than <math>\sqrt{k}</math> for k large, so A cannot produce an element of S of k digits or more, a contradiction.<br />
<br />
The same argument shows that there is no soft way to prove the weak conjecture either. However, it is not obvious whether one can adapt the argument to handle the situation in which there is a factoring oracle, since of course the fundamental theorem of arithmetic doesn't work if one replaces the primes by an arbitrary set S of "pseudoprimes".<br />
<br />
It is also not known at present whether one can modify the above oracle to produce a situation in which P=BPP (or in which <math>P \neq BPP</math>).</div>Asdf