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

[Torbjörn Granlund]

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."
  https://gmplib.org/manual/Block_002dWise-Barrett-Division.html#Block_002dWise-Barrett-Division,
  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.

-- 
Torbjörn
Please encrypt, key id 0xC8601622