[FOM] Finding a prime
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?
Check out AOL.com today. Breaking news, video search, pictures, email
and IM. All on demand. Always Free.
More information about the FOM