# Implications of a deterministic polytime prime-finding algorithm

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, which produced this writeup, but I do not see anywhere that they discuss implications of truth of the conjecture.

• This is likely true since it is conjectured that the prime gap is O(log(p_n)^2): en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture
– joro
Jan 23, 2015 at 7:56
• @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
Jan 23, 2015 at 11:21