Previous: Normal Powering Algorithm, Up: Powering Algorithms [Index]

Modular powering is implemented using a *2^k*-ary sliding window
algorithm, as per “Handbook of Applied Cryptography” algorithm 14.85
(see References). *k* is chosen according to the size of the
exponent. Larger exponents use larger values of *k*, the choice being
made to minimize the average number of multiplications that must supplement
the squaring.

The modular multiplies and squarings use either a simple division or the REDC method by Montgomery (see References). REDC is a little faster, essentially saving N single limb divisions in a fashion similar to an exact remainder (see Exact Remainder).