# Algorithms to generate consecutive primes

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$?

• 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." :-) – Marzio De Biasi Sep 7 '17 at 16:30
• 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. – Clement C. Sep 7 '17 at 16:56
• Oh Lordy, please tell me ASAP if such an algorithm is known. – Daniel Apon Sep 9 '17 at 4:23
• Note that the decision version is trivial if the twin prime conjecture is true, since the answer is just always YES for y > 2. – Noah Stephens-Davidowitz Sep 9 '17 at 5:45
• Hard search and hard decision are very different beasts w.r.t. cryptographically-interesting questions.. @NoahStephens-Davidowitz – Daniel Apon Sep 10 '17 at 23:42