<p>I'm wondering what are the current known uses/implications of a polynomial-time algorithm for the following problem:</p>

<blockquote>
  <p>Given $n$ in binary, output a prime $p &gt; n$.</p>
</blockquote>

<p>I'm both curious about specific useful applications, and any more broad complexity implications (for instance, would this get us any closer to $P=BPP$?).</p>

<p>Edit: by the way, this problem was (is?) the subject of the <a href="http://michaelnielsen.org/polymath1/index.php?title=Finding_primes" rel="nofollow">Polymath4 project</a>, which produced <a href="http://arxiv.org/abs/1009.3956" rel="nofollow">this writeup</a>, but I do not see anywhere that they discuss implications of truth of the conjecture.</p>

CC BY-SA 3.0
2015-01-23T07:56:22.510Z
This is likely true since it is conjectured that the prime gap is O(log(p_n)^2): https://en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture
joro
CC BY-SA 3.0
2015-01-23T11:21:19.997Z
@joro, agreed that it is likely true (although I am not sure if Cramer's conjecture is generally conjectured). There are interesting consequences of lots of things we think are likely true but cannot currently prove....
usul
<cc.complexity-theory><ds.algorithms><primes>
Implications of a deterministic polytime prime-finding algorithm
usul
# Implications of a deterministic polytime prime-finding algorithm

(Asked by: username_0 on 2015-01-23)

I'm wondering what are the current known uses/implications of a polynomial-time algorithm for the following problem:

> Given $n$ in binary, output a prime $p > n$.

I'm both curious about specific useful applications, and any more broad complexity implications (for instance, would this get us any closer to $P=BPP$?).

Edit: by the way, this problem was (is?) the subject of the [Polymath4 project](http://michaelnielsen.org/polymath1/index.php?title=Finding_primes), which produced [this writeup](http://arxiv.org/abs/1009.3956), but I do not see anywhere that they discuss implications of truth of the conjecture.

**Tags:** cc.complexity-theory, ds.algorithms, primes
> **Comments:**
> **username_1**: This is likely true since it is conjectured that the prime gap is O(log(p_n)^2): https://en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture  
> **username_0**: @joro, agreed that it is likely true (although I am not sure if Cramer's conjecture is generally conjectured). There are interesting consequences of lots of things we think are likely true but cannot currently prove....  

---

## 0 answers

