Editing Modular exponentiation (section)

=== Pseudocode ===

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 <var>base</var>, <var>exponent</var>, and <var>modulus</var> correspond to {{mvar|b}}, {{mvar|e}}, and {{mvar|m}} in the equations given above.

 '''function''' modular_pow(base, exponent, modulus) '''is'''
     '''if''' modulus = 1 '''then'''
         '''return''' 0
     [[Assertion (computing)|Assert]] :: (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 <var>base</var> is equivalent to {{mvar|b}}.  However, the repeated squaring in the third line of code ensures that at the completion of every loop, the variable <var>base</var> is equivalent to {{math|''b''{{sup|2{{sup|''i''}}}} mod ''m''}}, where {{mvar|i}} is the number of times the loop has been iterated.  (This makes {{mvar|i}} the next working bit of the binary exponent <var>exponent</var>, where the least-significant bit is <var>exponent<sub>0</sub></var>).

The first line of code simply carries out the multiplication in <math>\prod_{i=0}^{n-1} b^{a_i 2^i}\pmod m</math>.  If {{mvar|a}} is zero, no code executes since this effectively multiplies the running total by one.  If {{mvar|a}} instead is one, the variable <var>base</var> (containing the value {{math|''b''{{sup|2{{sup|''i''}}}} mod ''m''}} of the original base) is simply multiplied in.

In this example, the base {{mvar|b}} is raised to the exponent {{math|1=''e'' = 13}}.
The exponent is 1101 in binary. There are four binary digits, so the loop executes four times, with values {{math|1=''a''<sub>0</sub> = 1, ''a''<sub>1</sub> = 0, ''a''<sub>2</sub> = 1}}, and {{math|1=''a''<sub>3</sub> = 1}}.

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

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

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

The running time of this algorithm is {{math|O(log }}<var>exponent</var>{{math|)}}.  When working with large values of <var>exponent</var>, this offers a substantial speed benefit over the previous two algorithms, whose time is {{math|O(}}<var>exponent</var>{{math|)}}. For example, if the exponent was 2<sup>20</sup> = 1048576, this algorithm would have 20 steps instead of 1048576 steps.