<p>The <a href="https://en.wikipedia.org/wiki/Prime_number_theorem" rel="nofollow noreferrer">prime number theorem</a>, 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.</p>

<p>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$.</p>

<blockquote>
  <p>What deterministic algorithms are known for generating consecutive prime numbers given $x$ and $y$?</p>
</blockquote>

<p>Also, It would helpful to determine the complexity of the decision version:</p>

<p>INPUT: positive integers $x$ and $y$</p>

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

CC BY-SA 3.0
2017-09-07T16:30:04.897Z
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
CC BY-SA 3.0
2017-09-07T16:56:59.190Z
We do not even know deterministic efficients algorithms to generate primes of at least a given value, do we? (cf. e.g. [this](https://terrytao.wordpress.com/2010/09/21/a-deterministic-way-to-find-primes/) and [that](https://eccc.weizmann.ac.il/report/2016/196/)) Since your problem is at least as hard, deterministic and efficient looks rather hopeless.
Clement C.
CC BY-SA 3.0
2017-09-09T04:23:58.373Z
Oh Lordy, please tell me ASAP if such an algorithm is known.
Daniel Apon
CC BY-SA 3.0
2017-09-09T05:45:37.493Z
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
CC BY-SA 3.0
2017-09-10T23:42:48.483Z
Hard search and hard decision are very different beasts w.r.t. cryptographically-interesting questions.. @NoahStephens-Davidowitz
Daniel Apon
<ds.algorithms><nt.number-theory><primes>
Algorithms to generate consecutive primes
Mohammad Al-Turkistany
# Algorithms to generate consecutive primes

(Asked by: username_0 on 2017-09-07)

The [prime number theorem](https://en.wikipedia.org/wiki/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$?

**Tags:** ds.algorithms, nt.number-theory, primes

> **Comments:**
> **username_1**: 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." :-)  
> **username_2**: We do not even know deterministic efficients algorithms to generate primes of at least a given value, do we? (cf. e.g. [this](https://terrytao.wordpress.com/2010/09/21/a-deterministic-way-to-find-primes/) and [that](https://eccc.weizmann.ac.il/report/2016/196/)) Since your problem is at least as hard, deterministic and efficient looks rather hopeless.  
> **username_3**: Oh Lordy, please tell me ASAP if such an algorithm is known.  
> **username_4**: Note that the decision version is trivial if the twin prime conjecture is true, since the answer is just always YES for y > 2.  
> **username_3**: Hard search and hard decision are very different beasts w.r.t. cryptographically-interesting questions.. @NoahStephens-Davidowitz  

---

## 0 answers

