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
-
1here is c++ code for this with GMP,is what you want?http://codegolf.stackexchange.com/questions/2963/find-10-large-prime-numbers-with-n-digits – 2012-08-31
-
0by the way you can solve it easily,if have n digit,then take maximum number in this range ,for example suppose $n=5$,maximum is $99999$ and for i=1 to 999 substract i from $99999$ and test each result for prime – 2012-08-31
-
0Yes you are right but I need an algorithm which would accomplish the task in polynomial time in n. I am not sure if the method you suggested fulfills this criteria. – 2012-08-31
-
0ok i see,i will think about this criteria – 2012-08-31
2 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+1. Doesn't Tao have a polymath paper on this? – 2012-08-31
-
0I think a key part of this answer is that there is a polynomial-time algorithm for checking that a number is prime, which is (I believe) true but far from obvious. – 2012-08-31
-
0@Ben, quite right, it was big news a few years 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.