Algorithm to generate a prime number which is n-digits long Is there an algorithm which, given the number of digits n, generates a prime number which is      n-digits long, in polynomial time complexity?
 A: 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.  
A: One of Terence Tao's "polymath" projects is exactly about this question. Here is the relevant page, containing conjectures, partial results, and further references. 
http://michaelnielsen.org/polymath1/index.php?title=Finding_primes
To sum it all up: At the moment there is no such algorithm.
A: Such polynomial algorithm (depending on n) in unknow to humanity currently - but try this online tool for arbitrary precision calculations if you need to generate some n-digit primary number
https://www.alpertron.com.ar/ECM.HTM
For e.g. 20-digit number type:
N(100000000000000000000000000000)
and click 'factor' button - it will will return:
  100000000000000000000000000319

