All About Programming: To work out powers mod n, use repeated squaring

Quick description

A fact of fundamental importance in computational number theory is that calculating $a^r$ mod $n$ can be done efficiently on a computer. The reason is simple: by repeatedly squaring $a$ , one can work out $a^2$ , $a^4$ , $a^8$ , ... and then other powers $a^r$ can be calculated by taking products chosen according to the binary expansion of $r$ .

Prerequisites

Modular arithmetic

Example 1

One example is enough to give the idea. Let us work out $3^{37}$ mod $53$ . First, we repeatedly square $3$ mod $53$ until we have worked out $3^{2^k}$ for every $k$ such that $2^k\leq 37$ . We get $3^2=9$ ; $3^4=9^2=81\equiv 28$ ; $3^8\equiv 28^2=784\equiv -11$ (because $15\times 53=795$ ); $3^{16}\equiv 121\equiv 15$ ; $3^{32}\equiv 225\equiv 13$ . Next, we observe that $37=32+4+1$ . Therefore,