The prime number theorem, states that the "average length" of the gap between a prime $p$ and the next prime is ln(p). I am looking for (preferably deterministic efficient) an algorithm that generates two consecutive primes. For instance, 43 and 47 are consecutive primes.

The input is two positive integers $x$ and $y$ and I want two consecutive primes $p_1,p_2 \gt x$ and $|p_1-p_2 |\lt y$.

What deterministic algorithms are known for generating consecutive prime numbers given $x$ and $y$?

Also, It would helpful to determine the complexity of the decision version:

INPUT: positive integers $x$ and $y$

QUESTION: Are there consecutive primes $p_1, p_2 \gt x$ and $|p_1-p_2| \lt y$?

  • $\begingroup$ It may not be what you want, but ""I bet"" that this probabilistic approach works: "Guess a random number between $p_1, p_2$ and after ruling out quickly some small divisors check it using the Miller-Rabin primality test (that can be run several times to reduce the error rate), until you find a prime (with high probability you'll hit a prime if $x-y$ is great); then start checking $p_1 \pm 2*i, i=1,2,...$ until you hit the next one or the previous one." :-) $\endgroup$ Sep 7, 2017 at 16:30
  • 4
    $\begingroup$ We do not even know deterministic efficients algorithms to generate primes of at least a given value, do we? (cf. e.g. this and that) Since your problem is at least as hard, deterministic and efficient looks rather hopeless. $\endgroup$
    – Clement C.
    Sep 7, 2017 at 16:56
  • $\begingroup$ Oh Lordy, please tell me ASAP if such an algorithm is known. $\endgroup$ Sep 9, 2017 at 4:23
  • 1
    $\begingroup$ Note that the decision version is trivial if the twin prime conjecture is true, since the answer is just always YES for y > 2. $\endgroup$ Sep 9, 2017 at 5:45
  • $\begingroup$ Hard search and hard decision are very different beasts w.r.t. cryptographically-interesting questions.. @NoahStephens-Davidowitz $\endgroup$ Sep 10, 2017 at 23:42


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.