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.
Implications of a deterministic polytime prime-finding algorithm
cc.complexity theory;ds.algorithms;primes