Editing Modular exponentiation (section)

== 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 {{math|''m''}}. In that case, we would reduce each multiplication result {{math|(mod ''m'')}} 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, [[Donald Knuth]] notes that contrary to some assertions, this method does {{em|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. Instead, form ''x''<sup>3</sup> in two multiplications, then ''x''<sup>6</sup> by squaring ''x''<sup>3</sup>, then ''x''<sup>12</sup> by squaring ''x''<sup>6</sup>, and finally ''x''<sup>15</sup> by multiplying ''x''<sup>12</sup> and ''x''<sup>3</sup>, thereby achieving the desired result with only five multiplications. However, many pages follow describing how such sequences might be contrived in general.