chapter  2
3 Pages

Power algorithm

Continuing this, we obtain a sequence of integers P i, P2 , . . . Pn, where Pn = ae. Of course, if we are computing in Zn, we will reduce each product modulo n at every step of the calculation.

Note that, at every step, either we square a number or we compute the product a2% Pi for i = 1 , 2 , . . . , n. Moreover, if at step i we have bi = 0, then it is not necessary to compute a2%Pi.