Small-base modexp

[Marco Bodrato]

Ciao,

Il 2019-10-04 14:31 nisse at lysator.liu.se ha scritto:
> Depends on the details... Say we start with r in canonical

> Additive redc:
> 
>   r' = (r^2 + q m) / B < m^2 / B + m

> Subtractive redc:
> 
>   r' = (r^2 - qm) / B, -m < r' < m^2 / B
> 
> This can obviously underflow, and if we check for that and add back m,
> we get canonical representation, 0 <= r' < m.
> 
> A subtle advantage of subtractive redc is that in the double-limb
> subtraction r^2 - qm, the low limb always cancel, with no borrow, so we
> only need to subtract the high libms.

Thanks for the details! I tried the subrtactive redc for MPN_REDC_0 in 
mpn/generic/powm.c, and the resulting code seems cleaner and a little 
bit faster.

We are arguing again about the time spent in Miller-Rabin for 
nextprime... and we just released... so now we can experiment brand new 
code... That's why I pushed an implementation to specialise mpn_powm for 
the case base==2.
https://gmplib.org/repo/gmp/rev/63e53ddfd210

Comments are welcome.

Ĝis,
m