Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

Is there an algorithm which, given the number of digits n, generates a prime number which is n-digits long, in polynomial time complexity?

share|improve this question
1  
here is c++ code for this with GMP,is what you want?codegolf.stackexchange.com/questions/2963/… – dato Aug 31 '12 at 11:34
by 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 – dato Aug 31 '12 at 11:39
Yes 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. – ajay Aug 31 '12 at 11:44
ok i see,i will think about this criteria – dato Aug 31 '12 at 11:49

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
+1. Doesn't Tao have a polymath paper on this? – Charles Aug 31 '12 at 12:55
I 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. – Ben Millwood Aug 31 '12 at 14:09
@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. – Gerry Myerson Sep 1 '12 at 0:52
up vote 4 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.