Square and Multiply

A algorithm to calculate the power of a number. This is not particularly useful if we are just calculating some laaarge natural number. There are a lot of operations in cryptography where a number x is taken to the power of n, mod m. These calculations greatly benefit from this algorithm.

Idea: \begin{align} a&=x^9 = x \cdot x \cdot x \cdot x \cdot x \cdot x \cdot x \cdot x \cdot x \\ \\ b &= x \cdot x = x^2 \\ c &= b \cdot b = x^4 \\ d &= c \cdot c = x^8 \\ \\ a &= d \cdot x = x^9 \end{align}

How it works

The square-and-multiply method is an efficient algorithm for computing x^n by using the binary representation of the exponent n.

1. Convert the exponent to binary: Express n in binary form
2. Start with the result = x: Begin with the leftmost bit (always 1)
3. Process remaining bits left-to-right:
   • Square: For each subsequent bit, square the result
   • Multiply: If the bit is 1, multiply the result by x