How fast would a polynomial time factoring algorithm compute?

Question

I know factoring is the chief means of breaking RSA keys. I know an algorithm that runs in polynomial time would be able to break an RSA key pair "quickly". But how quickly is "quickly"? Note, I'm not talking about any quantum computing at all here.

Answer 1

I know an algorithm that runs in polynomial time would be able to break an RSA key pair "quickly". But how quickly is "quickly"?

No way to say, it might be microseconds, and it might be large multiplies of the age of the universe.

When we say that an algorithm runs in polynomial time, we're not saying anything about how fast the algorithm runs given any particular input. Instead, what we're saying that, as we give the algorithm increasingly large inputs, the time it takes doesn't increase that quickly.

How polynomial time is generally expressed is that there are values $c, e$ such that, given a problem of size $N$ (and in the factorization case, $N$ would be the number of bits in the RSA key), the algorithm takes time less than $cN^e$. Now, there are no limits on how big $c$ and $e$ might be, and so this doesn't give any limits on how much time a specific instance might take.

On the other hand, for all known factorization algorithms, this is not true -- no matter how large values we select for $c$ and $e$, we can find problem sizes $N$ large enough that the algorithm takes more than $cN^e$ time; hence saying that an algorithm is "polytime" does say something -- it just doesn't say what you're hoping it did.

Answer 2

The rationale behind polynomial vs. exponential is in tweaking the size of the keys. We need to achieve mainly two goals:

• Encryption and decryption by legitimate users is reasonable fast.
• Decryption by adversary without private key knowledge is prohibitively slow. (One way for decrypting by adversary might be computing private key from public key and subsequent decryption with the private key.)

When the size of the key grows, time of all these operations also grows bot both legitimate users and adversaries. We want to hugely (prohibitively) increase the computation time for adversaries while maintaining only small increase of time for legitimate users (i.e. for encryption with public key and decryption with private key). The encryption schemes are usually designed to increase the time polynomially for legitimate users and exponentially for adversaries. Note that if legitimate users can do the tasks in polynomial time, we can't make it any harder than exponential for adversary, because the best attack can't perform worse than brute-force.

This is the way we make the gap between legitimate users and adversaries huge. When a polynomial algorithm for factorisation is found, the gap will at least get lower. It might be a practical algorithm (and thus effectively a RSA break), but not necessarily:

• It might be an algorithm with a high degree of polynomial (e.g. $n^{10000}$), which will perform better than today's algorithms only on very very large inputs and which is clearly impractical.
• It might be an algorithm with a promising asymptotic complexity (e.g. $n^2$), but it would have a significant multiplicative or additive constant (e.g. $2^{128}$ seconds).

Nevertheless, when a polynomial-time integer factorisation algorithm is found, we have to at least reconsider usage of RSA. Such algorithm would be a warning sign that RSA is weaker than we thought.