According to [PolyMath](http://michaelnielsen.org/polymath1/index.php?title=Finding_primes)



> 
> **(Strong) conjecture**. There exists *deterministic* algorithm 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](https://mathoverflow.net/questions/217813/upper-bound-for-oeis-a076689-smallest-k-such-that-kp1-is-prime).


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?
> 
> 
> 



What is wrong with this deterministic algorithm efficiently generating large primes?
I have a somewhat different answer. The bound (1) is not known, but it is expected by some optimist paper. See for example this [paper](http://www.ams.org/journals/mcom/1996-65-216/S0025-5718-96-00763-6/S0025-5718-96-00763-6.pdf) which says that one expects $p' = O(p (\log p)^2)$ and gives (page 1718) three references to papers discussing this. This estimate is way better that anything one can prove with GRH. If it holds, then there is nothing wrong with your algorithm, it works fine (and is nice, by the way). 


However that estimate is so strong it is very doubtful. Actually it is related to Montgomery's conjecture, that $\psi(x,p,a) - x/(p-1) = O\_\epsilon( (x/p)^{1/2+\epsilon} \log(x))$, where $\psi(x,p,a)$ counts the (weighted by their log) primes congruent to $a$ modulo $p$ up to $x$. If I'm not mistaken, this implies that the first such prime $p'$ is $O\_\epsilon(p (\log p)^{2+\epsilon})$ which is very close to your estimate and enough for your algorithm. The problem is: Montgomery's conjecture 
has been proved false: see this [article](http://web.williams.edu/Mathematics/sjmiller/public_html/ntrmt11/handouts/primes/FriedlanderGranville_LimitationsEquiDsitrPrimesI.pdf) by Friedlander and Granville.
As a replacement, the same authors proposes (conjecture 1) $\psi(x,p,a) - x/(p-1) = O\_\epsilon( (x/p)^{1/2} x^\epsilon)$. This gives an estimate of $p'$ in $O(x^{1+\epsilon})$ and kills your algorithm. 


So in conclusion, your algorithm works assume your estimate, but this estimate, while it has been conjectured, is at best very doubtful.


