[FOM] Finding a prime

joeshipman@aol.com joeshipman at aol.com
Mon Jun 12 19:51:28 EDT 2006

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.

More information about the FOM mailing list