Hacker News Reader

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.

View on HN

Yes 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.

There 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.

Got it. This has been very enlightening. Thanks.

There 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.

Reply on news.ycombinator.com