in left to right order. In practice, we would usually want the result modulo some modulus . In that case, we would reduce each multiplication result before proceeding. For simplicity, the modulus calculation is omitted here. This example shows how to compute using left to right binary exponentiation. The exponent is 1101 in binary; there are 4 bits, so there are 4 iterations. Initialize the result to 1: . Step 1) ; bit 1 = 1, so compute ; Step 2) ; bit 2 = 1, so compute ; Step 3) ; bit 3 = 0, so we are done with this step; Step 4) ; bit 4 = 1, so compute . Minimum multiplications In The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, page 463, Donald Knuth notes that contrary to some assertions, this method does always give the minimum possible number of multiplications. The smallest counterexample is for a power of 15, when the binary method needs six multiplications. Instead, form x3 in two multiplications, then x6 by squaring x3, then x12 by squaring x6, and finally x15 by multiplying x12 and x3, thereby achieving the desired result with only five multiplications. However, many pages follow describing how such sequences might be contrived in general. Generalizations Matrices The -th term of any constant-recursive sequence (such as Fibonacci numbers or Perrin numbers) where each term is a linear function of previous terms can be computed efficiently modulo by computing , where is the corresponding companion matrix. The above methods adapt easily to this application. This can be used for primality testing of large numbers , for example. Pseudocode A recursive algorithm for ModExp(A, b, c) = , where is a square matrix. function Matrix_ModExp(Matrix A, int b, int c) is if b == 0 then return I // The identity matrix if (b mod 2 == 1) then return (A * Matrix_ModExp(A, b - 1, c)) mod c Matrix D := Matrix_ModExp(A, b / 2, c) return (D * D) mod c Finite cyclic groups Diffie–Hellman key exchange uses exponentiation in finite cyclic groups. The above methods for modular matrix exponentiation clearly extend to this context. The modular matrix multiplication is simply replaced everywhere by the group multiplication . Reversible and quantum modular exponentiation In quantum computing, modular exponentiation appears as the bottleneck of Shor's algorithm, where it must be computed by a circuit consisting of reversible gates,