/ 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.
This is an implementation of the above algorithm in the Ruby programming language. It doesn't use recursion, which increases the speed even further.
Replace result=1 with result=unit_matrix_of_the_same_size_as_x to get a matrix exponentiating algorithm.
def power(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