## Repeated squaring algorithm

How hard do you think it would be to compute by hand ? If you guess too hard, you're wrong. The algorithm described below shows how such seemingly difficult calculations are actually quite easy. In preparation for computing with Fermat's little theorem and Euler's theorem, both of which will be stated later, we show how to efficiently compute the power of an integer modulo .

One way to compute modulo is simply to compte then to reduce modulo . This is relatively hard to do if is large since there are a lot of digits to keep track of. We describe an alternative method.

Repeated squaring algorithm

To compute modulo :

step 1: write is binary,

where each is either 0 or .

step 2: Compute

(in that order).

step 3: Compute .

Example 1.7.10   We compute . First, , so we compute
• ,
• ,
• ,
• .
Thus .

David Joyner 2007-09-03