How fast would a polynomial time factoring algorithm compute? 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.
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.