View source for P=NP implies a deterministic algorithm to find primes

Consider the decision problem of determining whether there is a prime in the range <math>[m,n]</math>, where <math>m < n</math>.  This problem is in NP, since if there is a prime in the range, we can efficiently verify that it is prime.  Therefore, if P=NP, then this decision problem is in P, i.e., 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.