Generalizing Montgomery mod algorithm

Torbjorn Granlund tg at
Thu Jun 14 16:17:40 CEST 2012

One appliction of this new reduction algorithm might be for computing
a^b mod c when a is small.

When using Montgomery representaton for such bases, a^1, a^3, ... will
become log(c) bits large.  We could save lots of time by keeping many
such a powers limb sized.


More information about the gmp-devel mailing list