Possible to optimize for base 2 fermat primality test using shifts?
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