8
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\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$
    – Marzio De Biasi
    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$
    – Daniel Apon
    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$
    – Noah Stephens-Davidowitz
    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$
    – Daniel Apon
    Sep 10, 2017 at 23:42

0

Reset to default

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.