4 ms·
If you could do a multiply in a nano-second, you could do about 3 x 10^16 multiplies in a year. Keys are about 10^300, so it would take 10^84 years. Sort of.
by ColinWright 13y ago
If you could do a multiply in a nano-second, you could do about 3 x 10^16 multiplies in a year. Keys are about 10^300, so it would take 10^84 years.
Sort of.
In practice it's more complicated than that, but the numbers involved are HUGE. Doing the math with small examples always gives completely the wrong impression, like doing hill-climbing in 3D.
- weavie 13y agoYes I see. So, I assume there must be a quicker way to work out x ^ n that incorporates wrapping than just doing x = x * x % y repetitively. Darn it, my maths is getting rusty in my old age.
- ColinWright 13y agoThere is a fast exponentiation that is effectively Russian Peasant Multiplication, and it works in time proportional to number of bits in the exponent. Look up "fast exponentiation" or similar.
- weavie 13y agoGot it. This has been very enlightening. Thanks.
- sluukkonen 13y agoThere is. x^n = (x^(n/2))^2 if n is even, (x^(n-1/2))^2 if n is odd, so it's possible to exponentiation in logarithmic time.