/ 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 xn 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.
Replace result=1 with result=unit_matrix_of_the_same_size_as_x to get Matrix exponentiating algorithm.
def exp(x,n) result=1 i=1 while (n != 0) if ((n & i) != 0) then result*=x n-=i end x*=x i<<=1 end return result end