15.4.2 Modular Powering

Modular powering is implemented using a 2^k-ary sliding window algorithm, as per “Handbook of Applied Cryptography” algorithm 14.85 (see section 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 section References). REDC is a little faster, essentially saving N single limb divisions in a fashion similar to an exact remainder (see section Exact Remainder).

This document was generated on March 31, 2014 using texi2html 5.0.