Modular exponentiation

From BitcoinWiki
This is the approved revision of this page, as well as being the most recent.
Jump to: navigation, search

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 2<sup>20</sup> = 1048576, this algorithm would have 20 steps instead of 1048576 steps.

Left-to-right binary method[edit]

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[edit]

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 = x<sup>3</sup> in two multiplications and then x<sup>15</sup> = y<sup>5</sup> 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[edit]

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 primality testing of large numbers , for example.

Pseudocode[edit]

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[edit]

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[edit]

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.

In programming languages[edit]

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 <tt>pow()</tt> (exponentiation) function [1] takes an optional third argument which is the number to modulo by
  • .NET Framework's <tt>BigInteger</tt> class has a <tt>ModPow()</tt> method to perform modular exponentiation
  • 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 [2] to perform modular exponentiation
  • Perl 6 has a built-in routine <tt>expmod</tt>.
  • Go's <tt>big.Int</tt> type contains an <tt>Exp()</tt> (exponentiation) method [3] whose third parameter, if non-nil, is the number to modulo by
  • PHP's BC Math library has a <tt>bcpowmod()</tt> function [4] to perform modular exponentiation
  • The GNU Multiple Precision Arithmetic Library (GMP) library contains a <tt>mpz_powm()</tt> function [5] to perform modular exponentiation
  • Custom Function <tt>@PowerMod()</tt> for FileMaker Pro (with 1024-bit RSA encryption example)
  • Ruby's <tt>openssl</tt> package has the <tt>OpenSSL::BN#mod_exp</tt> method [6] to perform modular exponentiation.

See Also on BitcoinWiki[edit]

Source[edit]

http://wikipedia.org/