Modular exponentiation

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.

Contents

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

The and 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 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

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 , modular exponentiation appears as the bottleneck of , where it must be computed by a circuit consisting of , which can be further broken down into 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‘s built-in <tt>pow()</tt> (exponentiation) function [1] takes an optional third argument which is the number to modulo by
  • ‘s <tt>BigInteger</tt> class has a <tt>ModPow()</tt> method to perform modular exponentiation
  • ‘s <tt>java.math.BigInteger</tt> class has a method to perform modular exponentiation
  • ‘s <tt>Math::BigInt</tt> module has a <tt>bmodpow()</tt> method [2] to perform modular exponentiation
  • has a built-in routine <tt>expmod</tt>.
  • ‘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
  • ‘s BC Math library has a <tt>bcpowmod()</tt> function [4] to perform modular exponentiation
  • The (GMP) library contains a <tt>mpz_powm()</tt> function [5] to perform modular exponentiation
  • Custom Function <tt>@PowerMod()</tt> for (with 1024-bit encryption example)
  • ‘s <tt>openssl</tt> package has the <tt>OpenSSL::BN#mod_exp</tt> method [6] to perform modular exponentiation.

See Also on BitcoinWiki

  • , 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/