Is there an algorithm which, given the number of digits n, generates a prime number which is n-digits long, in polynomial time complexity?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
It is believed (though it is a much stronger result than anyone has been able to prove) that for $N$ large enough there is a prime between $N$ and $N+C(\log N)^2$, for some small positive constant $C$ (I think $C=2$ will do). So in practice you could take some $n$-digit number $N$ and then just test $N,N+1,N+2,\dots$ until you find a prime, and you would expect to find one in time polynomial in $n$. Of course in practice you wouldn't test the even numbers, indeed, you might sieve the whole interval for small factors first before applying any other primality tests.
I don't know if there is any algorithm proved to find a prime in polynomial time. We don't have any useful formulas guaranteed to give primes.
One of Terence Tao's "polymath" projects is exactly about this question. Here is the relevant page, containing conjectures, partial results, and further references.
To sum it all up: At the moment there is no such algorithm.