Possible to optimize for base 2 fermat primality test using shifts?

Torbjörn Granlund tg at gmplib.org
Tue May 21 10:09:54 UTC 2019

Hans L <thehans at gmail.com> writes:

  Looking into these algorithms some more, it found it interesting that "For
  the largest divisions, a block-wise Barrett division algorithm is used."
  however, this doesn't seem to apply to modular exponentiation, since that
  only supports REDC?  I wonder if there is some possible speedup to be
  gained from that.  If so, it wouldn't really be specific to base-2
  exponentiation either, since I think most of the Barrett operations already
  take advantage of shifts.

We do "REDC" for even the largest number.  We implemented a
generalisation of Barrett's algorithm for 2-adic norm.

REDC is nothing but a pre-multiply by a suitable power of 2, then 2-adic
reduction during the many multipy operations, and at the end removal of
the pre-multiply factor.

Please encrypt, key id 0xC8601622

More information about the gmp-discuss mailing list