Is there an algorithm which, given the number of digits n, generates a prime number which is n-digits long, in polynomial time complexity?
Algorithm to generate a prime number which is n-digits long
-
0ok i see,i will think about this criteria – 2012-08-31
3 Answers
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.
-
0@Ben, quite right, it was big news a few $y$ears ago when the algorithm you refer to was found. But there are algorithms that are faster in practice, even though they are not proved to run in polynomial time. – 2012-09-01
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.