Small-base modexp (was: Re: mpz_nextprime)

[Marco Bodrato]

Ciao,

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.

Ĝis,
m

-- 
http://bodrato.it/papers/