Modular exponentiation

Template:Short description Template:More citations needed 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 Template:Math (the base) is raised to the power Template:Math (the exponent), and divided by a positive integer Template:Math (the modulus); that is, Template:Math. From the definition of division, it follows that Template:Math.

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

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

Template:Math, where Template:Math and Template:Math.

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 Template:Math when given Template:Math, Template:Math, and Template:Math – is believed to be difficult. This one-way function behavior makes modular exponentiation a candidate for use in cryptographic algorithms.

Direct methodEdit

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

Template:Math

One could use a calculator to compute 4¹³; this comes out to 67,108,864. Taking this value modulo 497, the answer Template:Math is determined to be 445.

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

In strong cryptography, Template:Math is often at least 1024 bits.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> Consider Template:Math and Template:Math, both of which are perfectly reasonable values. In this example, Template:Math is 77 digits in length and Template:Math is 2 digits in length, but the value Template:Math 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 drop considerably. As Template:Math and Template:Math increase even further to provide better security, the value Template:Math becomes unwieldy.

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

Memory-efficient methodEdit

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

Template:Math

The modified algorithm is:

Inputs An integer Template:Mvar (base), integer Template:Mvar (exponent), and a positive integer Template:Mvar (modulus)

Outputs The modular exponent Template:Mvar where Template:Math

Initialise Template:Math and loop variable Template:Math
While Template:Math do
1. Increment Template:Mvar by 1
2. Calculate Template:Math
Output Template:Mvar

Note that at the end of every iteration through the loop, the equation Template:Math holds true. The algorithm ends when the loop has been executed Template:Mvar times. At that point Template:Mvar contains the result of Template:Math.

In summary, this algorithm increases Template:Mvar by one until it is equal to Template:Mvar. At every step multiplying the result from the previous iteration, Template:Mvar, by Template:Mvar and performing a modulo operation on the resulting product, thereby keeping the resulting Template:Mvar a small integer.

The example Template:Math, Template:Math, and Template:Math is presented again. The algorithm performs the iteration thirteen times:

Template:Math

The final answer for Template:Mvar is therefore 445, as in the direct method.

Like the first method, this requires Template:Math 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 Template:Math 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 methodEdit

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 Template:Math be converted to binary notation. That is, Template:Math can be written as:

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

The value Template:Math can then be written as:

<math>b^e = b^{\left( \sum_{i=0}^{n-1} a_i 2^i \right)} = \prod_{i=0}^{n-1} b^{a_i 2^i}</math>

The solution Template:Math is therefore:

<math>c \equiv \prod_{i=0}^{n-1} b^{a_i 2^i} \pmod m</math>

PseudocodeEdit

The following is an example in pseudocode based on Applied Cryptography by Bruce Schneier.<ref name="schneier96p244">Schneier 1996, p. 244.</ref> The inputs base, exponent, and modulus correspond to Template:Mvar, Template:Mvar, and Template:Mvar 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 Template:Mvar. However, the repeated squaring in the third line of code ensures that at the completion of every loop, the variable base is equivalent to Template:Math, where Template:Mvar is the number of times the loop has been iterated. (This makes Template:Mvar the next working bit of the binary exponent exponent, where the least-significant bit is exponent₀).

The first line of code simply carries out the multiplication in <math>\prod_{i=0}^{n-1} b^{a_i 2^i}\pmod m</math>. If Template:Mvar is zero, no code executes since this effectively multiplies the running total by one. If Template:Mvar instead is one, the variable base (containing the value Template:Math of the original base) is simply multiplied in.

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

First, initialize the result <math>R</math> to 1 and preserve the value of Template:Math in the variable Template:Math:

<math> R \leftarrow 1 \, ( = b^0) \text{ and } x \leftarrow b </math>.

Step 1) bit 1 is 1, so set <math> R \leftarrow R \cdot x \text{ }(= b^1) </math>;

set <math> x \leftarrow x^2 \text{ }(= b^2) </math>.

Step 2) bit 2 is 0, so do not reset Template:Math;

set <math> x \leftarrow x^2 \text{ }(= b^4) </math>.

Step 3) bit 3 is 1, so set <math> R \leftarrow R \cdot x \text{ }(= b^5) </math>;

set <math> x \leftarrow x^2 \text{ }(= b^8) </math>.

Step 4) bit 4 is 1, so set <math> R \leftarrow R \cdot x \text{ }(= b^{13}) </math>;

This is the last step so we don't need to square Template:Math.

We are done: Template:Math is now <math>b^{13}</math>.

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

Initialize:

<math> R \leftarrow 1 \, ( = b^0) </math> and <math> x \leftarrow b = 4 </math>.

Step 1) bit 1 is 1, so set <math>R \leftarrow R \cdot 4 \equiv 4 \pmod{497} </math>;

set <math> x \leftarrow x^2 \text{ }(= b^2) \equiv 4^2 \equiv 16 \pmod{497} </math>.

Step 2) bit 2 is 0, so do not reset Template:Math;

set <math> x \leftarrow x^2 \text{ }(= b^4) \equiv 16^2\equiv 256 \pmod{497} </math>.

Step 3) bit 3 is 1, so set <math> R \leftarrow R \cdot x \text{ }(= b^5) \equiv 4 \cdot 256 \equiv 30 \pmod{497} </math>;

set <math> x \leftarrow x^2 \text{ }(= b^8) \equiv 256^2 \equiv 429 \pmod{497} </math>.

Step 4) bit 4 is 1, so set <math> R \leftarrow R \cdot x \text{ }(= b^{13}) \equiv 30 \cdot 429 \equiv 445 \pmod{497} </math>;

We are done: Template:Mvar is now <math>4^{13} \equiv 445 \pmod{497}</math>, the same result obtained in the previous algorithms.

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

Implementation in LuaEdit

function modPow(b, e, m)
  if m == 1 then
    return 0
  end
  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

Left-to-right binary methodEdit

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 Template:Math. In that case, we would reduce each multiplication result Template:Math before proceeding. For simplicity, the modulus calculation is omitted here. This example shows how to compute <math>b^{13}</math> 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: <math>r \leftarrow 1 \, ( = b^0)</math>.

Step 1) <math>r \leftarrow r^2 \, ( = b^0)</math>; bit 1 = 1, so compute <math>r \leftarrow r \cdot b \,( = b^1)</math>;

Step 2) <math>r \leftarrow r^2 \, ( = b^2)</math>; bit 2 = 1, so compute <math>r \leftarrow r \cdot b \, ( = b^3)</math>;

Step 3) <math>r \leftarrow r^2 \, ( = b^6)</math>; bit 3 = 0, so we are done with this step;

Step 4) <math>r \leftarrow r^2 \, ( = b^{12})</math>; bit 4 = 1, so compute <math>r \leftarrow r \cdot b \, ( = b^{13})</math>.

Minimum multiplicationsEdit

In The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, page 463, Donald Knuth notes that contrary to some assertions, this method does Template:Em 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 x³ in two multiplications, then x⁶ by squaring x³, then x¹² by squaring x⁶, and finally x¹⁵ by multiplying x¹² and x³, thereby achieving the desired result with only five multiplications. However, many pages follow describing how such sequences might be contrived in general.

GeneralizationsEdit

MatricesEdit

The Template:Mvar-th term of any constant-recursive sequence (such as Fibonacci numbers or Perrin numbers) where each term is a linear function of Template:Mvar previous terms can be computed efficiently modulo Template:Mvar by computing Template:Math, where Template:Mvar is the corresponding Template:Math companion matrix. The above methods adapt easily to this application. This can be used for primality testing of large numbers Template:Mvar, for example.

Pseudocode

A recursive algorithm for ModExp(A, b, c) = Template:Math, where Template:Mvar 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 groupsEdit

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 Template:Math is simply replaced everywhere by the group multiplication Template:Math.

Reversible and quantum modular exponentiationEdit

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.<ref>Template:Cite journal</ref>

Software implementationsEdit

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 [1] 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 Template:Javadoc:SE 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 [2] to perform modular exponentiation
Raku has a built-in routine expmod.
Go's big.Int type contains an Exp() (exponentiation) method [3] whose third parameter, if non-nil, is the modulus
PHP's BC Math library has a bcpowmod() function [4] to perform modular exponentiation
The GNU Multiple Precision Arithmetic Library (GMP) library contains a mpz_powm() function [5] 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 [6] to perform modular exponentiation.