5 ms·
But squaring numbers is paralellizable. You pick an exponent you want and take a modulus only later. Iterative squaring is also trivial if exponent is a power o
by superpermutat0r 7y ago
But squaring numbers is paralellizable. You pick an exponent you want and take a modulus only later. Iterative squaring is also trivial if exponent is a power of two. Calculating x^(2^t) mod n should take no time on any computer.
I think the rest of the puzzle is fairly hard to guess.
- zodiac 7y agoIterative squaring is not paralellizable - to compute x^4 as (x^2)^2 you have to compute t = x^2 first before starting the computation of t^2. Calculating x^(2^t) mod n takes t squarings.