Square and multiply exponentiation

"Square and multiply" exponentiation is a quick method of raising to a power x modulus N, which needs only bit length (x) operations instead of x operations.

Calculation of y = m^x (mod N) in pseudo-code where we use for the exponent x the binary representation of x[0] x[1] ... x[n-1]:

1. y = 1
2. for ( i = 0, ..., n-1 )
    {
    y = y*y (mod N)                             // Square
    if (x[i] == 1) then y = y*m (mod N)         // Multiply
    }

This algorithm thus requires bit length(x) multiplications and squares.

For example, in

m^65537_10 = m^10000000000000001_2 (mod N)

y = 1;
y = y*y;
y = y*m (x[0]=1);
y=y*y (x[1]=0);
....;
y=y*y (x[15]=0);
y=y*y; y*y*m (x[16]=1)

is calculated via one multiplication and 16 squares.