"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.