According to PolyMath

(Strong) conjecture. There existsdeterministicalgorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in k. You may assume as many standard conjectures in number theory (e.g. the generalised Riemann hypothesis) as necessary, but avoid powerful conjectures in complexity theory (e.g. P=BPP) if possible.

According to answers in this question.

Let $p$ be prime. Under GRH there exists prime $p' \equiv 1 \pmod{p}$ satisfying

$$p' \leq 70 p (\log p)^2 \qquad (1)$$

**Doubling lemma** Let $p$ be odd prime. In time polynomial in $\log{p}$
we can find prime $p' > 2p$.

From (1), the interval $[p+1,70 p (\log p)^2]$ contains about $70(\log{p})^2$ integers congruent to $1$ modulo $p$ of form $mp+1$ and at least one $p'$ is prime. Since $p+1$ is even, $p' \ge 2p+1$.

To find $p'$, enumerate the candidates and check them for primality.

The complexity is polynomial in $\log{p}$.

Start from $p=3$ and repeat Doubling lemma.

Each iteration produces prime at least twice larger than the previous step.

So this appears to give algorithm under GRH to find $p>k$ in time polynomial in $\log{k}$, which is equivalent to the Strong conjecture.

What is wrong with this?

5more comments