(gmp.info.gz) Modular Powering Algorithm

Info Catalog

(gmp.info.gz) Normal Powering Algorithm

(gmp.info.gz) Powering Algorithms

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

Info Catalog

(gmp.info.gz) Normal Powering Algorithm

(gmp.info.gz) Powering Algorithms