Difference between revisions of "Exponentiation by squaring"

Latest revision as of 11:07, 18 May 2022

Exponentiation by squaring is a fast way to raise a base to an integer exponent by considering the binary digits of the exponent.

Algorithm

Begin with a partial product $P$ , initially empty (equal to $1$ ) and a factor $F$ , initially equal to the base.

Starting on the rightmost binary digit of the exponent and ending on the leftmost digit,

If the exponent digit is $1$ , multiply $P$ by $F$ ; if the digit is $0$ , leave $P$ as is,
Square $F$ ,
Move left one digit.

The final value of $P$ is the result. When considering the leftmost digit, the step of squaring $F$ can be skipped, since no future multiplications of $F$ into $P$ will occur.

Efficiency

The speed gained by exponentiation by squaring over simply repeatedly multiplying the base by itself is analogous to the speed gained during multiplication by distributing and multiplying the digits of both factors rather than repeatedly adding one factor to itself. In other words, the concept of "square and multiply" is similar to "shift (multiply by $2$ ) and add", and offers similar improvement to efficiency.

Applications

For ordinary powers of integer bases, exponentiation by squaring is not immediately effective because the rapidly growing sizes of the partial product and the squared factor essentially cancel out the advantage of using fewer multiplications. However, it is tremendously helpful in exponentiation of an integer modulo another integer, in which the size of the partial products remains contained. Also, exponentiation by squaring can be effective when the base is a floating point number, whose length in significant figures remains the same after multiplication by another floating point number, although precision errors can accumulate if the exponent is large enough.

Example with modular exponentiation

Problem: Verify Fermat's Little Theorem for $a = 5$ and $p = 19$ .

Solution: We want to find $5^{19} \pmod {19}$ . Doing eighteen multiplications would be tedious, but we can accomplish the calculation more quickly. We write $5^{19} = 5^{10011_2}$ .

The rightmost binary digit is $1$ , so we multiply a $5$ into the result (partial product). To advance the digit in consideration leftward, we square $5$ , obtaining $25 \equiv 6 \pmod {19}$ .

Now the digit in consideration is again a $1$ , so we multiply the result (currently $5$ ) by $6$ to obtain $11$ . We square $6$ to prepare for the next digit, obtaining $17$ .

This time, the digit is a $0$ , so we square $17$ (producing $4$ ) and do not alter the result. Likewise, the next digit is a $0$ , so we square again to get $16$ . Now the digit in consideration (the leftmost digit) is $1$ , so we multiply the result $11$ by $16$ . There is no need to square after the final, leftmost digit; $11 \cdot 16 = 176 \equiv 5 \pmod {19}$ , so $5^{19} \equiv 5 \pmod {19}$ , as desired.

The following table provides a summary of the variable values throughout the calculation, where $P$ is the partial product and $F$ is the current factor after squaring.

$\mathrm{Digit}$	$P$	$F$
$\mathrm{initial}$	$1$	$5$
$1$	$1 \cdot 5 \equiv 5$	$5^2 \equiv 6$
$1$	$5 \cdot 6 \equiv 11$	$6^2 \equiv 17$
$0$	$11$	$17^2 \equiv 4$
$0$	$11$	$4^2 \equiv 16$
$1$	$11 \cdot 16 \equiv 5$

The approach may be visualized as using the fact that $5^{19} = 5^{16+2+1} = (5^{16})(5^2)(5^1)$ and that exponents that are themselves powers of $2$ can all be easily managed using a single course of repeated squaring.

@@ Line 22: / Line 22: @@
 Solution: We want to find <math>5^{19} \pmod {19}</math>. Doing eighteen multiplications would be tedious, but we can accomplish the calculation more quickly. We write <math>5^{19} = 5^{10011_2}</math>.
-The rightmost binary digit is <math>1</math>, so we multiply a <math>5</math> into the result (partial product). To advance the digit in consideration leftward, we square <math>5</math>, obtaining <math>25 \pmod {19} = 6</math>.
+The rightmost binary digit is <math>1</math>, so we multiply a <math>5</math> into the result (partial product). To advance the digit in consideration leftward, we square <math>5</math>, obtaining <math>25 \equiv 6 \pmod {19}</math>.
 Now the digit in consideration is again a <math>1</math>, so we multiply the result (currently <math>5</math>) by <math>6</math> to obtain <math>11</math>. We square <math>6</math> to prepare for the next digit, obtaining <math>17</math>.

Page

Toolbox

Search