P=NP implies a deterministic algorithm to find primes

From Polymath Wiki
Revision as of 21:25, 28 July 2009 by WikiSysop (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Consider the decision problem of determining whether there is a prime in the range [math][m,n][/math], where [math]m \lt n[/math]. This problem is in NP, since if there is a prime in the range, we can efficiently verify that it is prime. By assumption, this decision problem is therefore in P, and thus there is a polynomial-time algorithm to determine whether there is a prime in the range [math][m,n][/math].

We can use this algorithm as a subroutine to quickly find a prime in the range [n,2n] for large n. We use the well-known fact that such a prime always exists. We then use the polynomial-time algorithm described above to do a binary search to locate such a prime. This terminates after at most [math]\log_2 n[/math] applications of the subroutine, and thus is a polynomial-time algorithm to generate a prime.