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](http://michaelnielsen.org/polymath1/index.php?title=Finding_primes), 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.