Return to Revisions

If we could find a number $x$ co-prime to $2^n!$ in $n^{O(1)}$ time, we could factor it to find a prime greater than $2^n$. This would constitute a solution to the strong conjecture with factoring, so it is an open problem. As far as I know, it is open whether or not it is possible to find a prime larger than $2^n$ in time $2^{\frac{n}{2}+o(1)}$ with or without a factoring oracle.