Admin: Created page with "'''Modular}} mod ''m''}} of the original base) is simply multiplied in. In this example, the base <tt>b</tt> is raised to the exponent <tt>e = 13</tt>..."

2019-06-16T12:22:47Z

Created page with "'''Modular}} mod ''m''}} of the original base) is simply multiplied in. In this example, the base <tt>b</tt> is raised to the exponent <tt>e = 13</tt>..."

New page

'''Modular}} mod ''m''}} of the original base) is simply multiplied in.

In this example, the base <tt>b</tt> is raised to the exponent <tt>e = 13</tt>.
The exponent is 1101 in binary. There are four binary digits, so the loop executes four times.
The bits in right-to-left order are 1, 0, 1, 1.

First, initialize the result <math>R</math> to 1 and preserve the value of <tt>b</tt> in the variable <tt>x</tt>:
: <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 <tt>R</tt>;
:: 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 <tt>x</tt>.
We are done: <tt>R</tt> is now <math>b^{13}</math>.

Here is the above calculation, where we compute <tt>b = 4</tt> to the power <tt>e = 13</tt>, 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 \pmod {497} \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 <tt>R</tt>;
:: set <math> x \leftarrow x^2 \text{ }(= b^4) \equiv 16^2 \pmod{497} \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 \pmod{497} \equiv 30 \pmod{497} </math>;
:: set <math> x \leftarrow x^2 \text{ }(= b^8) \equiv 256^2 \pmod{497} \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 \pmod{497} \equiv 445 \pmod{497} </math>;

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

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

==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 <tt>m</tt>. In that case, we would reduce each multiplication result <tt>(mod m)</tt> 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 multiplications===
In ''The Art of Computer Programming, Vol. 2, Seminumerical Algorithms'', page 463, Professor Knuth notes that contrary to some assertions, this method does ''not'' always give the minimum possible number of multiplications. The smallest counterexample is for a power of 15, when the binary method needs six multiplications, yet forming ''y = x3'' in two multiplications and then ''x15 = y5'' in three more, achieves the desired result with only five multiplications. However, many pages follow describing how such sequences might be contrived in general.

==Matrices==
The [[Fibonacci numbers]] and [[Perrin numbers]] modulo can be computed efficiently by computing for a certain and a certain matrix . The above methods adapt easily to this application. This can be used for [[Fibonacci number#Primality testing|primality testing]] of large numbers , for example.

===Pseudocode===
A recursive algorithm for <tt>ModExp(A, b, c)</tt> = , where is a square matrix.
'''function''' Matrix_ModExp(Matrix A, int b, int c)
'''if''' (b == 0):
'''return''' I // The identity matrix
'''if''' (b '''mod''' 2 == 1):
'''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 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.

==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 [https://docs.python.org/library/functions.html#pow] takes an optional third argument which is the number to modulo by
* [[.NET Framework]]'s <tt>BigInteger</tt> class has a <tt>[http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.modpow%28v=vs.100%29.aspx#pow ModPow()]</tt> method to perform modular exponentiation
* [[Java (programming language)|Java]]'s <tt>java.math.BigInteger</tt> class has a 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
* [[Perl 6]] has a built-in routine <tt>expmod</tt>.
* [[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)
* [[Ruby (programming language)|Ruby]]'s <tt>openssl</tt> package has the <tt>OpenSSL::BN#mod_exp</tt> method [http://ruby-doc.org/stdlib-trunk/libdoc/openssl/rdoc/OpenSSL/BN.html#method-i-mod_exp] to perform modular exponentiation.

==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

==Source==

[http://wikipedia.org/ http://wikipedia.org/]
[[Category:Cryptographic algorithms]]

Modular exponentiation - Revision history

Admin: Created page with "'''Modular}} mod ''m''}} of the original base) is simply multiplied in. In this example, the base <tt>b</tt> is raised to the exponent <tt>e = 13</tt>..."