Small-base modexp (was: Re: mpz_nextprime)
bodrato at mail.dm.unipi.it
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
More information about the gmp-devel