# Brute force RSA cracking

Suppose one had a complete list of primes up to $2^{n+1}-1$. Then wouldn't one be able to crack an $n$-bit RSA public key in time $O(\pi(2^{n+1}-1))$, making RSA insecure?

Thanks,

René

-

Actually, one would be able to crack a $2n$-bit RSA public key in $O(\pi(2^{n+1})-1)$ time. However, $O(\pi(2^{n+1})-1) = O(2^n / n)$, and we already know how to factor $2n$-bit numbers faster than that.