Modular exponentiation
Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie-Hellman Key Exchange and RSA public/private keys.

Modular exponentiation is the remainder when an integer  (the base) is raised to the power  (the exponent), and divided by a positive integer  (the modulus); that is, . From the definition of division, it follows that .

For example, given ,  and , dividing  by  leaves a remainder of .

Modular exponentiation can be performed with a negative exponent  by finding the modular multiplicative inverse  of  modulo  using the extended Euclidean algorithm. That is:
, where  and .

Modular exponentiation is efficient to compute, even for very large integers.  On the other hand, computing the modular discrete logarithm – that is, finding the exponent  when given , , and  – is believed to be difficult. This one-way function behavior makes modular exponentiation a candidate for use in cryptographic algorithms.

Direct method 
The most direct method of calculating a modular exponent is to calculate  directly, then to take this number modulo .  Consider trying to compute , given , , and :
 

One could use a calculator to compute 413; this comes out to 67,108,864.  Taking this value modulo 497, the answer  is determined to be 445.

Note that  is only one digit in length and that  is only two digits in length, but the value  is 8 digits in length.

In strong cryptography,  is often at least 1024 bits.  Consider  and , both of which are perfectly reasonable values.  In this example,  is 77 digits in length and  is 2 digits in length, but the value  is 1,304 decimal digits in length.  Such calculations are possible on modern computers, but the sheer magnitude of such numbers causes the speed of calculations to slow considerably.  As  and  increase even further to provide better security, the value  becomes unwieldy.

The time required to perform the exponentiation depends on the operating environment and the processor.  The method described above requires  multiplications to complete.

Memory-efficient method 
Keeping the numbers smaller requires additional modular reduction operations, but the reduced size makes each operation faster, saving time (as well as memory) overall.

This algorithm makes use of the identity
 

The modified algorithm is:
 Set , .
 Increase  by 1.
 Set .
 If , go to step 2.  Else,  contains the correct solution to .

Note that in every pass through step 3, the equation  holds true.  When step 3 has been executed  times, then,  contains the answer that was sought. In summary, this algorithm basically counts up  by ones until  reaches , doing a multiply by  and a modulo operation each time it adds one (to ensure the results stay small).

The example , , and  is presented again.  The algorithm passes through step 3 thirteen times:
 
 
 
 
 
 
 
 
 
 
 
 
 

The final answer for  is therefore 445, as in the first method.

Like the first method, this requires  multiplications to complete.  However, since the numbers used in these calculations are much smaller than the numbers used in the first algorithm's calculations, the computation time decreases by a factor of at least  in this method.

In pseudocode, this method can be performed the following way:
 function modular_pow(base, exponent, modulus) is
     if modulus = 1 then
         return 0
     c := 1
     for e_prime = 0 to exponent-1 do
         c := (c * base) mod modulus
     return c

Right-to-left binary method 
A third method drastically reduces the number of operations to perform modular exponentiation, while keeping the same memory footprint as in the previous method.  It is a combination of the previous method and a more general principle called exponentiation by squaring (also known as binary exponentiation).

First, it is required that the exponent  be converted to binary notation.  That is,  can be written as:
 

In such notation, the length of  is  bits.  can take the value 0 or 1 for any  such that .  By definition, .

The value  can then be written as:
 

The solution  is therefore:

Pseudocode 

The following is an example in pseudocode based on Applied Cryptography by Bruce Schneier.  The inputs base, exponent, and modulus correspond to , , and  in the equations given above.

 function modular_pow(base, exponent, modulus) is
     if modulus = 1 then
         return 0
     Assert :: (modulus - 1) * (modulus - 1) does not overflow base
     result := 1
     base := base mod modulus
     while exponent > 0 do
         if (exponent mod 2 == 1) then
             result := (result * base) mod modulus
         exponent := exponent >> 1
         base := (base * base) mod modulus
     return result

Note that upon entering the loop for the first time, the code variable base is equivalent to .  However, the repeated squaring in the third line of code ensures that at the completion of every loop, the variable base is equivalent to , where  is the number of times the loop has been iterated.  (This makes  the next working bit of the binary exponent exponent, where the least-significant bit is exponent0).

The first line of code simply carries out the multiplication in .  If  is zero, no code executes since this effectively multiplies the running total by one.  If  instead is one, the variable base (containing the value  of the original base) is simply multiplied in.

In this example, the base  is raised to the exponent .
The exponent is 1101 in binary. There are four binary digits, so the loop executes four times, with values , and .

First, initialize the result  to 1 and preserve the value of  in the variable :
 .
 Step 1)  bit 1 is 1, so set ;
 set .
 Step 2)  bit 2 is 0, so do not reset ;
 set .
 Step 3)  bit 3 is 1, so set ;
 set .
 Step 4)  bit 4 is 1, so set ;
 This is the last step so we don't need to square .
We are done:  is now .

Here is the above calculation, where we compute  to the power  , performed modulo 497.

Initialize:
   and  .
 Step 1)  bit 1 is 1, so set ;
 set .
 Step 2) bit 2 is 0, so do not reset ;
 set .
 Step 3)  bit 3 is 1, so set ;
 set .
 Step 4)  bit 4 is 1, so set ;

We are done:  is now , the same result obtained in the previous algorithms.

The running time of this algorithm is exponent.  When working with large values of exponent, this offers a substantial speed benefit over the previous two algorithms, whose time is exponent. For example, if the exponent was 220 = 1048576, this algorithm would have 20 steps instead of 1048576 steps.

Implementation in Lua 

 function modPow(b, e, m)
   if m == 1 then
     return 0
   else
     local r = 1
     b = b % m
     while e > 0 do
       if e % 2 == 1 then
         r = (r*b) % m
       end
       b = (b*b) % m
       e = e >> 1     --use 'e = math.floor(e / 2)' on Lua 5.2 or older
     end
     return r
   end
 end

Left-to-right binary method 
We can also use the bits of the exponent 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, which can be further broken down into quantum gates appropriate for a specific physical device. Furthermore, in Shor's algorithm it is possible to know the base and the modulus of exponentiation at every call, which enables various circuit optimizations.

Software implementations 

Because modular exponentiation is an important operation in computer science, and there are efficient algorithms (see above) that are much faster than simply exponentiating and then taking the remainder, many programming languages and arbitrary-precision integer libraries have a dedicated function to perform modular exponentiation:
 Python's built-in pow() (exponentiation) function  takes an optional third argument, the modulus
 .NET Framework's BigInteger class has a ModPow() method to perform modular exponentiation
 Java's java.math.BigInteger class has a  method to perform modular exponentiation
 MATLAB's powermod function from Symbolic Math Toolbox
Wolfram Language has the PowerMod function
 Perl's Math::BigInt module has a bmodpow() method  to perform modular exponentiation
 Raku has a built-in routine expmod.
 Go's big.Int type contains an Exp() (exponentiation) method  whose third parameter, if non-nil, is the modulus
 PHP's BC Math library has a bcpowmod() function  to perform modular exponentiation
 The GNU Multiple Precision Arithmetic Library (GMP) library contains a mpz_powm() function  to perform modular exponentiation
 Custom Function @PowerMod() for FileMaker Pro (with 1024-bit RSA encryption example)
 Ruby's openssl package has the OpenSSL::BN#mod_exp method  to perform modular exponentiation.
 The HP Prime Calculator has the CAS.powmod() function  to perform modular exponentiation. For a^b mod c, a can be no larger than 1 EE 12.  This is the maximum precision of most HP calculators including the Prime.

See also 
 Montgomery reduction, for calculating the remainder when the modulus is very large.
 Kochanski multiplication, serializable method for calculating the remainder when the modulus is very large
 Barrett reduction, algorithm for calculating the remainder when the modulus is very large.

References

External links 

 Paul Garrett, Fast Modular Exponentiation Java Applet
 

Cryptographic algorithms
Number theoretic algorithms
Modular arithmetic
Articles with example pseudocode