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é
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.
Hence, even if someone could come up with such a list (and find some place to store it), it wouldn't actually affect the security of RSA.
