Skip to main content
MathOverflow

Return to Answer

deleted 3 characters in body
Source Link
Dan Brumleve
Dan Brumleve
  • 2.3k
  • 17
  • 28

As mentioned, this follows from an effective form of Cramér's conjecture, so we won't be able to disprove it.

But we won't be able to prove it either, because it implies the existence of an algorithm to find an $n$-bit prime in polynomial time, another open problem. The algorithm searches for a prime using the AKS primality test by starting at $2^n+1$ and counting up until it finds one, requiring total time $O(n^{8+o(1)})$$n^{8+o(1)}$ if your conjecture is true. But the state of the art in finding an $n$-bit prime is an algorithm requiring $2^{0.525 \cdot n + o(n)}$ time — in fact, it's the same algorithm, it's just not known to run any faster than that.

As mentioned, this follows from an effective form of Cramér's conjecture, so we won't be able to disprove it.

But we won't be able to prove it either, because it implies the existence of an algorithm to find an $n$-bit prime in polynomial time, another open problem. The algorithm searches for a prime using the AKS primality test by starting at $2^n+1$ and counting up until it finds one, requiring total time $O(n^{8+o(1)})$ if your conjecture is true. But the state of the art in finding an $n$-bit prime is an algorithm requiring $2^{0.525 \cdot n + o(n)}$ time — in fact, it's the same algorithm, it's just not known to run any faster than that.

As mentioned, this follows from an effective form of Cramér's conjecture, so we won't be able to disprove it.

But we won't be able to prove it either, because it implies the existence of an algorithm to find an $n$-bit prime in polynomial time, another open problem. The algorithm searches for a prime using the AKS primality test by starting at $2^n+1$ and counting up until it finds one, requiring total time $n^{8+o(1)}$ if your conjecture is true. But the state of the art in finding an $n$-bit prime is an algorithm requiring $2^{0.525 \cdot n + o(n)}$ time — in fact, it's the same algorithm, it's just not known to run any faster than that.

Source Link
Dan Brumleve
Dan Brumleve
  • 2.3k
  • 17
  • 28

As mentioned, this follows from an effective form of Cramér's conjecture, so we won't be able to disprove it.

But we won't be able to prove it either, because it implies the existence of an algorithm to find an $n$-bit prime in polynomial time, another open problem. The algorithm searches for a prime using the AKS primality test by starting at $2^n+1$ and counting up until it finds one, requiring total time $O(n^{8+o(1)})$ if your conjecture is true. But the state of the art in finding an $n$-bit prime is an algorithm requiring $2^{0.525 \cdot n + o(n)}$ time — in fact, it's the same algorithm, it's just not known to run any faster than that.