Small-base modexp (was: Re: mpz_nextprime)

Marco Bodrato bodrato at
Thu Sep 19 20:39:54 UTC 2019


Il Mer, 4 Settembre 2019 5:07 pm, Marco Bodrato ha scritto:
> Il Mer, 4 Settembre 2019 10:44 am, Niels Möller ha scritto:

>> I think I've seen comments in the literature saying that 2^e mod m is
>> "obviously" more efficient than general modular exponentiation. But as

> This means writing a special function for b=2, not for more general small
> bases. Currently I do not have the time to, anyone?

If nobody started or is willing to try... I'll try to write such a special
function for base=2.

Il Mer, 4 Settembre 2019 5:39 pm, Niels Möller ha scritto:

> And in the bit more general small-base case, that shift would be an
> mpn_mul_1. And I think the difference in speed between shift and mul_1
> is negligible, since in either case, almost all the cycles will be spent
> on the modular squarings.

A mul_1 and a divrem_1... But this can be another step, I'll try with
case=2  only.



More information about the gmp-devel mailing list