mpz_nextprime
paul zimmermann
Paul.Zimmermann at inria.fr
Wed Sep 4 15:47:28 UTC 2019
Torbjörn,
> With k-ary modexp, the number of multiplications is log2(n)/k,
> while the number of squarings are log(n). Therefore a small b will not
> make a huge difference.
>
> As Marco points implies, one may handle some special values like b = 2
> also in REDC coding and still not pay the price of a full
> multiplication.
with a small base, no need of k-ary modexp. In the REDC domain, instead of
computing a'*b'/r mod n, where b' = r*b mod n is the REDC encoding of the
base b, just compute a'*b mod n.
Another trick is to use a base b such that b' is small, then you don't even
need to modify the REDC code (assuming it recognizes small multipliers).
Paul
More information about the gmp-devel
mailing list