2.1.4 Repeated Squaring Method

2.1.4 Repeated Squaring Method

A repeated squaring method is a basic computation in modular arithmetic for finding

b^n (mod m) when both m and n are very large. There is a clever way of doing this

that is much quicker than repeated multiplication of b itself. The related algorithm is as

following:

Let n0,n1,... ,nk-1 denote the binary digits of n, i.e.,

n = n0 +2n1 +4n2 + ···+2^(k-1)nk-1 (nj =0 or 1).

Then, We compute as following :

b^2, (b^2)^2 = b^4, (b^4)^2 = b^8, ··· , (b^2^(k-2))^2 = b^2^(k-1).

It follows as

b^n = b^(n0 +2n1 +4n2 +···+2^(k - 1). nk - 1

= b^n0 · b^2n1 · b^4n2 ...b^[2( k-1)(nk – 1)]

= b^n0 · (b^2)^n1 · (b^4)^n2 ···(b^2^k - 1 )^nk - 1

As b^2, (b^2)^2 = b^4, (b^4)^2 = b^8, ··· , (b^2^k-2)^2 = b^2^(k-1) is computed before,

b^n (mod m) can be computed easily.