Fast modular exponentiation

RSA requires us to calculate numbers such as m^65537 mod n, where n has 600 digits. Calculating m^65537 and then reducing it is impossible: the intermediate number would have millions of digits.

Two ideas

Reduce at each stage. Since the multiplication is carried out modulo, we reduce after each product. The numbers never exceed the size of n.

Square rather than multiply one by one. To calculate a^16, we do not perform 15 multiplications:

a^2  = a × a
a^4  = a^2 × a^2
a^8  = a^4 × a^4
a^16 = a^8 × a^8

Four multiplications instead of fifteen. For any exponent, we break it down into binary.

A complete example

Let’s calculate 7^13 mod 11. In binary, this is 13 = 1101.

7^1  ≡ 7          (mod 11)
7^2  ≡ 49 ≡ 5     (mod 11)
7^4  ≡ 5² = 25 ≡ 3   (mod 11)
7^8  ≡ 3² = 9     (mod 11)

Like 13 = 8 + 4 + 1:

7^13 ≡ 7^8 × 7^4 × 7^1
     ≡ 9 × 3 × 7
     ≡ 189
     ≡ 2       (mod 11)

None of the numbers used exceeded 189.

Why this is crucial

The naive method requires a number of multiplications proportional to the exponent. Fast exponentiation requires a number proportional to the number of digits in the exponent.

For an exponent of 600 digits, the number of operations drops from 10^600 — which is inconceivable — to a few thousand. It is this difference that makes RSA practical.

It is also the central asymmetry of modern cryptography: certain operations are fast in one direction and beyond reach in the other.