Node:Modular Powering Algorithm, Previous:Normal Powering Algorithm, Up:Powering Algorithms
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 squares 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). The current REDC has some limitations.
It's only O(N^2) so above POWM_THRESHOLD division becomes faster
and is used. It doesn't attempt to detect small bases, but rather always uses
a REDC form, which is usually a full size operand. And lastly it's only
applied to odd moduli.