[FOM] Finding a prime

[joeshipman@aol.com]

What is the fastest deterministic algorithm known which, given n, finds 
an n-bit prime (that is, a prime number between 2^(n-1) and 2^n)?

Now that primality testing is known to be polynomial time, there is 
clearly an "expected polynomial time" algorithm which works by guessing 
a number at random and testing it for primality, but is there known to 
be a deterministic polynomial time algorithm?

Since the largest prime gaps in the range [2^(n-1), 2^n] are 
conjectured to be of size O(n^2), simply starting at the bottom and 
working up ought to suffice, but is the best known unconditional bound 
on prime gaps up to 2^n polynomial in n?

-- JS
________________________________________________________________________
Check out AOL.com today. Breaking news, video search, pictures, email 
and IM. All on demand. Always Free.