A question of modulo

Example 2.1.9 Suppose we want to compute 432^678 (mod 987). The basic trick is to

start with a number and keep squaring:

432^2 = 186624 ≡ 81 432^4 ≡ 81^2 ≡ 639 432^8 ≡ 639^2 ≡ 690 ...432^512 ≡ 858

Since 678 = 512 + 128 + 32 + 4 + 2,

432 678 ≡ (81)(639) ...(858) ≡ 204

Calculations with exponents involve not-too-many multiplications. If the numbers have

several hundred digits, however, it is necessary to design special subroutines to do the

multiplications.

The idea behind fast exponentiation is that if the exponent is a power of 2 then we can

exponentiate by successively squaring:

x^8 =((x^2)^2)^2,

x^256 = (((((((x^2)^2)^2)^2)^2)^2)^2)^2.

If the exponent is not a power of 2, then we use its binary representation, which is just a

sum powers of 2:

x^291 = x^256 × x^32 × x^2 × x^1.

Thus to raise x to power n requires only about log n operations.