Exponentiation By Squaring - Further Applications

Further Applications

The same idea allows fast computation of large exponents modulo a number. Especially in cryptography, it is useful to compute powers in a ring of integers modulo q. It can also be used to compute integer powers in a group, using the rule

Power(x, −n) = (Power(x, n))−1.

The method works in every semigroup and is often used to compute powers of matrices,

For example, the evaluation of

13789722341 (mod 2345)

would take a very long time and lots of storage space if the naïve method were used: compute 13789722341 then take the remainder when divided by 2345. Even using a more effective method will take a long time: square 13789, take the remainder when divided by 2345, multiply the result by 13789, and so on. This will take 722340 modular multiplications. The square-and-multiply algorithm is based on the observation that 13789722341 = 13789(137892)361170. So, if we computed 137892, then the full computation would only take 361170 modular multiplications. This is a gain of a factor of two. But since the new problem is of the same type, we can apply the same observation again, once more approximately halving the size.

The repeated application of this algorithm is equivalent to decomposing the exponent (by a base conversion to binary) into a sequence of squares and products: for example

x13 = x1101_bin

= x(1·2^3 + 1·2^2 + 0·2^1 + 1·2^0)

= x1·2^3 · x1·2^2 · x0·2^1 · x1·2^0

= x2^3 · x2^2 · 1 · x2^0

= x8 · x4 · x1

= (x4)2 · (x2)2 · x

= (x4 · x2)2 · x

= ((x2)2 · x2)2 · x

= ((x2 · x)2)2 · x → algorithm needs only 5 multiplications instead of 12 (13−1)

Some more examples:

• x10 = ((x2)2·x)2 because 10 = (1,010)₂ = 23+21, algorithm needs 4 multiplications instead of 9
• x100 = (((((x2·x)2)2)2·x)2)2 because 100 = (1,100,100)₂ = 26+25+22, algorithm needs 8 multiplications instead of 99
• x1,000 = ((((((((x2·x)2·x)2·x)2·x)2)2·x)2)2)2 because 103 = (1,111,101,000)₂, algorithm needs 14 multiplications instead of 999
• Worked example (with modulo) for the RSA algorithm.