GNU Info

(gmp.info)Modular Powering Algorithm

---

Prev: Normal Powering Algorithm Up: Powering Algorithms

---

Enter node , (file) or (file)node

Modular Powering
----------------

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