HOME

TheInfoList



OR:

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 In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log'' ...
– 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
bit The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represented ...
s. 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: : e = \sum_^ a_i 2^i 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: : b^e = b^ = \prod_^ b^ The solution is therefore: : c \equiv \prod_^ b^ \pmod m


Pseudocode

The following is an example in pseudocode based on Applied Cryptography by
Bruce Schneier Bruce Schneier (; born January 15, 1963) is an American cryptographer, computer security professional, privacy specialist, and writer. Schneier is a Lecturer in Public Policy at the Harvard Kennedy School and a Fellow at the Berkman Klein Cent ...
. Schneier 1996, p. 244. 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 Assertion or assert may refer to: Computing * Assertion (software development), a computer programming technique * assert.h, a header file in the standard library of the C programming language * Assertion definition language, a specification lan ...
:: (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 \prod_^ b^\pmod m. 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 R to 1 and preserve the value of in the variable : : R \leftarrow 1 \, ( = b^0) \text x \leftarrow b . : Step 1) bit 1 is 1, so set R \leftarrow R \cdot x \text(= b^1) ; :: set x \leftarrow x^2 \text(= b^2) . : Step 2) bit 2 is 0, so do not reset ; :: set x \leftarrow x^2 \text(= b^4) . : Step 3) bit 3 is 1, so set R \leftarrow R \cdot x \text(= b^5) ; :: set x \leftarrow x^2 \text(= b^8) . : Step 4) bit 4 is 1, so set R \leftarrow R \cdot x \text(= b^) ; :: This is the last step so we don't need to square . We are done: is now b^. Here is the above calculation, where we compute to the power , performed modulo 497. Initialize: : R \leftarrow 1 \, ( = b^0) and x \leftarrow b = 4 . : Step 1) bit 1 is 1, so set R \leftarrow R \cdot 4 \equiv 4 \pmod ; :: set x \leftarrow x^2 \text(= b^2) \equiv 4^2 \equiv 16 \pmod . : Step 2) bit 2 is 0, so do not reset ; :: set x \leftarrow x^2 \text(= b^4) \equiv 16^2\equiv 256 \pmod . : Step 3) bit 3 is 1, so set R \leftarrow R \cdot x \text(= b^5) \equiv 4 \cdot 256 \equiv 30 \pmod ; :: set x \leftarrow x^2 \text(= b^8) \equiv 256^2 \equiv 429 \pmod . : Step 4) bit 4 is 1, so set R \leftarrow R \cdot x \text(= b^) \equiv 30 \cdot 429 \equiv 445 \pmod ; We are done: is now 4^ \equiv 445 \pmod, 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 b^ 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: r \leftarrow 1 \, ( = b^0). : Step 1) r \leftarrow r^2 \, ( = b^0); bit 1 = 1, so compute r \leftarrow r \cdot b \,( = b^1); : Step 2) r \leftarrow r^2 \, ( = b^2); bit 2 = 1, so compute r \leftarrow r \cdot b \, ( = b^3); : Step 3) r \leftarrow r^2 \, ( = b^6); bit 3 = 0, so we are done with this step; : Step 4) r \leftarrow r^2 \, ( = b^); bit 4 = 1, so compute r \leftarrow r \cdot b \, ( = b^).


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 ''x''3 in two multiplications, then ''x''6 by squaring ''x''3, then ''x''12 by squaring ''x''6, and finally ''x''15 by multiplying ''x''12 and ''x''3, 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 In mathematics and theoretical computer science, a constant-recursive sequence is an infinite sequence of numbers where each number in the sequence is equal to a fixed linear combination of one or more of its immediate predecessors. A constan ...
(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 In linear algebra, the Frobenius companion matrix of the monic polynomial : p(t)=c_0 + c_1 t + \cdots + c_t^ + t^n ~, is the square matrix defined as :C(p)=\begin 0 & 0 & \dots & 0 & -c_0 \\ 1 & 0 & \dots & 0 & -c_1 \\ 0 & 1 & \dots & 0 & -c_2 ...
. The above methods adapt easily to this application. This can be used for
primality testing A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating wh ...
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 Shor's algorithm is a quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. On a quantum computer, to factor an integer N , Shor's algorithm runs in polynomial ...
, where it must be computed by a circuit consisting of reversible gates, which can be further broken down into
quantum gate In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate (or simply quantum gate) is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, lik ...
s 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 Python may refer to: Snakes * Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia ** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia * Python (mythology), a mythical serpent Computing * Python (pr ...
's built-in pow() (exponentiation) functio

takes an optional third argument, the modulus *
.NET Framework The .NET Framework (pronounced as "''dot net"'') is a proprietary software framework developed by Microsoft that runs primarily on Microsoft Windows. It was the predominant implementation of the Common Language Infrastructure (CLI) until bein ...
's BigInteger class has a ModPow()
/code> method to perform modular exponentiation * Java's java.math.BigInteger class has a method to perform modular exponentiation *
MATLAB MATLAB (an abbreviation of "MATrix LABoratory") is a proprietary multi-paradigm programming language and numeric computing environment developed by MathWorks. MATLAB allows matrix manipulations, plotting of functions and data, implementatio ...
's powermod function from Symbolic Math Toolbox *Wolfram Language has th
PowerMod
function * Perl's Math::BigInt module has a bmodpow() metho

to perform modular exponentiation * Raku (programming language), Raku has a built-in routine expmod. * Go's big.Int type contains an Exp() (exponentiation) metho

whose third parameter, if non-nil, is the modulus * PHP's BC Math library has a bcpowmod() functio

to perform modular exponentiation * The GNU Multiple Precision Arithmetic Library (GMP) library contains a mpz_powm() functio

to perform modular exponentiation * Custom Function @PowerMod()
/code> for FileMaker Pro (with 1024-bit RSA encryption example) * Ruby's openssl package has the OpenSSL::BN#mod_exp metho

to perform modular exponentiation. * The HP Prime Calculator has the CAS.powmod() functio

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 Kochanski multiplication is an algorithm that allows modular arithmetic (multiplication or operations based on it, such as exponentiation) to be performed efficiently when the modulus is large (typically several hundred bits). This has particular ap ...
, serializable method for calculating the remainder when the modulus is very large *
Barrett reduction In modular arithmetic, Barrett reduction is a reduction algorithm introduced in 1986 by P.D. Barrett. A naive way of computing :c = a \,\bmod\, n \, would be to use a fast division algorithm. Barrett reduction is an algorithm designed to optimi ...
, algorithm for calculating the remainder when the modulus is very large. $

$ R\sim-T$$

References

Lr(~x, ~ωr) = Z Ωi fr(~x, ~ωi → ~ωr)Li(~x, ~ωi) cos θidωi


External links

* * Paul Garrett
Fast Modular Exponentiation Java Applet
* {{number theoretic algorithms Cryptographic algorithms Number theoretic algorithms Modular arithmetic Articles with example pseudocode