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,

$3^{37}\equiv 13\times 28\times 3=13\times 84\equiv 13\times 31=403\equiv 32.$

General discussion

This algorithm is considered efficient because the time it takes depends polynomially on the numbers of digits of $a$ , $r$ and $n$ . For instance, the number of steps taken by long multiplication of two $k$ -digit numbers is roughly proportional to $k^2$ (and there are quicker methods that use the fast Fourier transform), and the number of multiplications we need to do in the above calculation is proportional to $\log r$ , which is proportional to the number of digits of $r$ . If we reduce mod $n$ every time we multiply two numbers together, then the numbers we have to multiply are always smaller than $n$ . And reduction mod $n$ can also be done in time polynomial in the number of digits of the number to be reduced, which will always be at most $n^2$ and will therefore have at most twice as many digits as $n$ .

55931 reads
Subscribe

Comments

Post new comment

(Note: commenting is not possible on this snapshot.)