mpz_nextprime

[paul zimmermann]

       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