Exponentiating by squaring

Exponentiating by squaring is an algorithm used for the fast computation of large powers of a number x. The following recursive algorithm computes xⁿ for a natural number n:

                      /  1;                      if n = 0 
     Power(x, n)  =  {   Power(x2, n/2);         if n is positive and even
                      \  x * Power(x2, (n-1)/2); if n is odd

Compared to the ordinary method of multiplying x with itself n-1 times, this algorithm speeds up the computation of xⁿ tremendously.

The method works in every semigroup and is often used to compute powers of matrices, and, especially in cryptography, to compute powers in a ring of integers modulo q.