4
$\begingroup$

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

  • 0
    ok i see,i will think about this criteria2012-08-31

3 Answers 3

6

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
6

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.