|
|
| Line 1: |
Line 1: |
| '''Modular exponentiation''' is a type of [[exponentiation]] performed over a [[modular arithmetic|modulus]]. It is particularly useful in [[computer science]], especially in the field of [[cryptography]].
| | Hello. Allow me introduce the author. Her name is Emilia Shroyer but it's not the most feminine title out there. Hiring is his occupation. Puerto Rico is where he's always been residing but she requirements to transfer because of her family. Playing baseball is the hobby he will never quit doing.<br><br>my weblog ... [http://www.htvalumni.com/members/kristeek/activity/177437/ over the counter std test] |
| | |
| A "modular exponentiation" calculates the remainder when a positive integer b (the base) raised to the e-th power (the exponent), <math> b^e </math>, is divided by a [[positive integer]] m, called the modulus. In symbols, given base ''b'', exponent ''e'', and modulus ''m'', the modular exponentiation ''c''
| |
| is: <math>c \equiv b^e \pmod{m}</math>
| |
| | |
| For example, given ''b'' = 5, ''e'' = 3, and ''m'' = 13, the solution, ''c'' = 8, is the remainder of dividing <math>5^3</math> by 13.
| |
| | |
| If ''b'', ''e'', and ''m'' are non-negative, and ''b'' < ''m'', then a unique solution ''c'' exists with the property 0 ≤ ''c'' < ''m''.
| |
| | |
| Modular exponentiation can be performed with a ''negative'' exponent ''e'' by finding the [[modular multiplicative inverse]] ''d'' of ''b'' modulo ''m'' using the [[extended Euclidean algorithm]]. That is:<br>
| |
| : <math>c \equiv b^{e} \equiv d^{\left|e\right|} \pmod{m}</math> where ''e'' < 0 and <math>b \cdot d \equiv 1 \pmod{m}</math>
| |
| | |
| Modular exponentiation problems similar to the one described above are considered easy to solve, even when the numbers involved are enormous. On the other hand, computing the [[discrete logarithm]] - that is, the task of finding the exponent ''e'' if given ''b'', ''c'', and ''m'' - is believed to be difficult. This [[one way function]] behavior makes modular exponentiation a candidate for use in cryptographic algorithms.
| |
| | |
| ==Straightforward method==
| |
| The most straightforward method of calculating a modular exponent is to calculate ''b''<sup>''e''</sup> directly, then to take this number modulo ''m''. Consider trying to compute ''c'', given ''b'' = 4, ''e'' = 13, and ''m'' = 497:<br/>
| |
| : <math>c \equiv 4^{13} \pmod{497}</math>
| |
| | |
| One could use a calculator to compute 4<sup>13</sup>; this comes out to 67,108,864. Taking this value modulo 497, the answer ''c'' is determined to be 445.
| |
| | |
| Note that ''b'' is only one digit in length and that ''e'' is only two digits in length, but the value ''b''<sup>''e''</sup> is 8 digits in length.
| |
| | |
| In strong cryptography, ''b'' is often at least 256 binary digits (77 decimal digits). Consider ''b'' = 5 × 10<sup>76</sup> and ''e'' = 17, both of which are perfectly reasonable values. In this example, ''b'' is 77 digits in length and ''e'' is 2 digits in length, but the value ''b''<sup>''e''</sup> 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 ''b'' and ''e'' increase even further to provide better security, the value ''b''<sup>''e''</sup> becomes unwieldy.
| |
| | |
| The time required to perform the exponentiation depends on the operating environment and the processor. The method described above requires [[Big O notation|O]](''e'') multiplications to complete.
| |
| | |
| ==Memory-efficient method==
| |
| A second method to compute modular exponentiation requires more operations than the first method. Because the required memory is substantially less, however, operations take less time than before. The end result is that the algorithm is faster.
| |
| | |
| This algorithm makes use of the fact that, given two integers ''a'' and ''b'', the following two equations are equivalent:<br/>
| |
| : <math>c \equiv (a \cdot b) \pmod{m}</math>
| |
| : <math>c \equiv (a \cdot (b\ (\mbox{mod}\ m))) \pmod{m}</math>
| |
| | |
| The algorithm is as follows:
| |
| # Set ''c'' = 1, ''e′'' = 0.
| |
| # Increase ''e′'' by 1.
| |
| # Set <math>c \equiv (b \cdot c) \pmod{m}</math>.
| |
| # If ''e′'' < ''e'', goto step 2. Else, ''c'' contains the correct solution to <math>c \equiv b^e \pmod{m}</math>.
| |
| | |
| Note that in every pass through step 3, the equation <math>c \equiv b^{e'} \pmod{m}</math> holds true. When step 3 has been executed ''e'' times, then, ''c'' contains the answer that was sought. In summary, this algorithm basically counts up ''e′'' by ones until ''e′'' reaches ''e'', doing a multiply by b and the modulo operation each time it adds one (to ensure the results stay small).
| |
| | |
| The example ''b'' = 4, ''e'' = 13, and ''m'' = 497 is presented again. The algorithm passes through step 3 thirteen times:
| |
| * ''e′'' = 1. ''c'' = (1 * 4) mod 497 = 4 mod 497 = '''4'''.
| |
| * ''e′'' = 2. ''c'' = (4 * 4) mod 497 = 16 mod 497 = '''16'''.
| |
| * ''e′'' = 3. ''c'' = (16 * 4) mod 497 = 64 mod 497 = '''64'''.
| |
| * ''e′'' = 4. ''c'' = (64 * 4) mod 497 = 256 mod 497 = '''256'''.
| |
| * ''e′'' = 5. ''c'' = (256 * 4) mod 497 = 1024 mod 497 = '''30'''.
| |
| * ''e′'' = 6. ''c'' = (30 * 4) mod 497 = 120 mod 497 = '''120'''.
| |
| * ''e′'' = 7. ''c'' = (120 * 4) mod 497 = 480 mod 497 = '''480'''.
| |
| * ''e′'' = 8. ''c'' = (480 * 4) mod 497 = 1920 mod 497 = '''429'''.
| |
| * ''e′'' = 9. ''c'' = (429 * 4) mod 497 = 1716 mod 497 = '''225'''.
| |
| * ''e′'' = 10. ''c'' = (225 * 4) mod 497 = 900 mod 497 = '''403'''.
| |
| * ''e′'' = 11. ''c'' = (403 * 4) mod 497 = 1612 mod 497 = '''121'''.
| |
| * ''e′'' = 12. ''c'' = (121 * 4) mod 497 = 484 mod 497 = '''484'''.
| |
| * ''e′'' = 13. ''c'' = (484 * 4) mod 497 = 1936 mod 497 = '''445'''.
| |
| | |
| The final answer for ''c'' is therefore 445, as in the first method.
| |
| | |
| Like the first method, this requires O(''e'') 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 O(''e'') in this method.
| |
| | |
| In pseudocode, this method can be performed the following way:
| |
| '''function''' modular_pow(base, exponent, modulus)
| |
| c := 1
| |
| '''for''' e_prime = 1 '''to''' exponent
| |
| 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 ''e'' be [[Binary numeral system#Decimal|converted to binary notation]]. That is, ''e'' can be written as:<br/>
| |
| : <math>e = \sum_{i=0}^{n-1} a_i 2^i</math>
| |
| | |
| In such notation, the ''length'' of ''e'' is ''n'' bits. ''a''<sub>''i''</sub> can take the value 0 or 1 for any ''i'' such that 0 ≤ ''i'' < ''n'' - 1. By definition, ''a''<sub>''n'' - 1</sub> = 1.
| |
| | |
| The value ''b''<sup>''e''</sup> can then be written as:<br/>
| |
| : <math>b^e = b^{\left( \sum_{i=0}^{n-1} a_i 2^i \right)} = \prod_{i=0}^{n-1} \left( b^{2^i} \right) ^ {a_i}</math>
| |
| | |
| The solution ''c'' is therefore:
| |
| : <math>c \equiv \prod_{i=0}^{n-1} \left( b^{2^i} \right) ^ {a_i}\ (\mbox{mod}\ m)</math>
| |
| | |
| The following is an example in pseudocode based on Applied Cryptography by [[Bruce Schneier]].<ref name="schneier96p244">[[#Schneier96|Schneier 1996]], p. 244.</ref> The inputs ''base'', ''exponent'', and ''modulus'' correspond to ''b'', ''e'', and ''m'' in the equations given above.
| |
| | |
| '''function''' modular_pow(base, exponent, modulus)
| |
| result := 1
| |
| '''while''' exponent > 0
| |
| '''if''' (exponent '''mod''' 2 == 1):
| |
| 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 <math>b\ </math>. However, the repeated squaring in the third line of code ensures that at the completion of every loop, the variable ''base'' is equivalent to <math>b^{2^i}\ (\mbox{mod}\ m)</math>, where ''i'' is the number of times the loop has been iterated. (This makes ''i'' the next working bit of the binary exponent ''exponent'', where the least-significant bit is ''exponent''<sub>0</sub>).
| |
| | |
| The first line of code simply carries out the multiplication in <math>\prod_{i=0}^{n-1} \left( b^{2^i} \right) ^ {a_i}\ (\mbox{mod}\ m)</math>. If ''a''<sub>''i''</sub> is zero, no code executes since this effectively multiplies the running total by one. If ''a''<sub>''i''</sub> instead is one, the variable ''base'' (containing the value <math>b^{2^i}\ (\mbox{mod}\ m)</math> of the original base) is simply multiplied in.
| |
| | |
| Example: ''base'' = 4, ''exponent'' = 13, and ''modulus'' = 497. Note that ''exponent'' is 1101 in binary notation. Because ''exponent'' is four binary digits in length, the loop executes only four times:
| |
| * Upon entering the loop for the first time, variables ''base'' = 4, ''exponent'' = 1101 (binary), and ''result'' = 1. Because the right-most bit of ''exponent'' is 1, ''result'' is changed to be (1 * 4)% 497, or '''4'''. ''exponent'' is right-shifted to become 110 (binary), and ''base'' is squared to be (4 * 4)% 497, or 16.
| |
| * The second time through the loop, the right-most bit of ''exponent'' is 0, causing ''result'' to retain its present value of '''4'''. ''exponent'' is right-shifted to become 11 (binary), and ''base'' is squared to be (16 * 16)% 497, or 256.
| |
| * The third time through the loop, the right-most bit of ''e'' is 1. ''result'' is changed to be (4 * 256)% 497, or '''30'''. ''exponent'' is right-shifted to become 1, and ''base'' is squared to be (256 * 256)% 497, or 429.
| |
| * The fourth time through the loop, the right-most bit of ''exponent'' is 1. ''result'' is changed to be (30 * 429)% 497, or '''445'''. ''exponent'' is right-shifted to become 0, and ''base'' is squared to be (429 * 429)% 497, or 151.
| |
| | |
| The loop then terminates since ''exponent'' is zero, and the result '''445''' is returned. This agrees with the previous two algorithms.
| |
| | |
| The running time of this algorithm is O(log ''exponent''). When working with large values of ''exponent'', this offers a substantial speed benefit over both of the previous two algorithms.
| |
| | |
| ==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 computing|reversible gates]], which can be further broken down into [[quantum gate]]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.<ref>Igor L. Markov, Mehdi Saeedi, "Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation", Quantum Information and Computation, Vol. 12, No. 5&6, pp. 0361-0394, 2012.http://arxiv.org/abs/1202.6614</ref>
| |
| | |
| ==In programming languages==
| |
| 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 (programming language)|Python]]'s built-in <tt>pow()</tt> (exponentiation) function [http://docs.python.org/library/functions.html#pow] takes an optional third argument which is the number to modulo by
| |
| * [[Java (programming language)|Java]]'s <tt>java.math.BigInteger</tt> class has a {{Javadoc:SE|name=modPow()|java/math|BigInteger|modPow(java.math.BigInteger,%20java.math.BigInteger)}} method to perform modular exponentiation
| |
| * [[Perl]]'s <tt>Math::BigInt</tt> module has a <tt>bmodpow()</tt> method [http://perldoc.perl.org/Math/BigInt.html#bmodpow%28%29] to perform modular exponentiation
| |
| * [[Go (programming language)|Go]]'s <tt>big.Int</tt> type contains an <tt>Exp()</tt> (exponentiation) method [http://golang.org/pkg/big/#Int.Exp] whose third parameter, if non-nil, is the number to modulo by
| |
| * [[PHP]]'s BC Math library has a <tt>bcpowmod()</tt> function [http://www.php.net/manual/en/function.bcpowmod.php] to perform modular exponentiation
| |
| * The [[GNU Multiple Precision Arithmetic Library]] (GMP) library contains a <tt>mpz_powm()</tt> function [http://gmplib.org/manual/Integer-Exponentiation.html] to perform modular exponentiation
| |
| * Custom Function <tt>[http://www.briandunning.com/cf/1482 @PowerMod()]</tt> for [[FileMaker|FileMaker Pro]] (with 1024-bit [[RSA (algorithm)|RSA]] encryption example)
| |
| | |
| ==See also==
| |
| * [[Montgomery reduction]], for calculating the remainder when the modulus is very large.
| |
| | |
| ==References==
| |
| {{reflist}}
| |
| {{cite book|title=Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition|last=Schneier|first=Bruce|authorlink=Bruce Schneier|year=1996|publisher=Wiley|edition=2nd|isbn=978-0-471-11709-4|ref=Schneier96}}
| |
| | |
| ==External links==
| |
| * [http://www.math.umn.edu/~garrett/crypto/a01/FastPow.html Fast Modular Exponentiation Java Applet] - [[University of Minnesota]] Math Department
| |
| | |
| {{number theoretic algorithms}}
| |
| | |
| [[Category:Cryptographic algorithms]]
| |
| [[Category:Number theoretic algorithms]]
| |
| [[Category:Modular arithmetic]]
| |