2-adic roots (Re: bdiv vs redc)

David Harvey d.harvey at unsw.edu.au
Tue Jul 31 01:10:00 CEST 2012

On Jul 31, 2012, at 7:42 AM, Niels Möller wrote:

> We currently have modular exponentation, powlo and "regular" powering
> with no reduction of any kind. I'm suggesting a pow_modbnm1. For
> euclidean square root, and for mpfr, it might also be useful with a
> pow_high, keeping only the n most significant limbs of each product, and
> returning the number of discarded low limbs. Another potential use is
> powm with moduli of special form, where the reduction can be done
> cheaper than with montgomery redc. Maybe the function could even be used
> for more complicated groups, e.g., if implementing elliptic curve
> operations on top of gmp. Or maybe it's easy enough to duplicate the
> code for each useful case, perhaps sharing some bit extraction macros in
> gmp-impl.h.

Related to this, you may also want to check out the paper "Fast convolutions meet Montgomery" by Mihailescu, I've always thought that would be an interesting algorithm to put in GMP, but maybe a bit tricky to implement.


More information about the gmp-devel mailing list