Exponentiation by Squaring Algorithm

Exponentiation by squaring computes a large integer or modular power, such as a raised to the power n, in O(log n) multiplications rather than the n minus one multiplications a naive repeated-multiplication approach would require, by repeatedly squaring the base and multiplying the accumulated result by the current squared value whenever the corresponding bit of the exponent's binary representation is set. When performed with a modulus applied after each multiplication, the same technique is the standard method for fast modular exponentiation used throughout public-key cryptography, including RSA. The method has been known in various forms since antiquity and is sometimes called binary exponentiation or square-and-multiply.