2-adic roots (Re: bdiv vs redc)

[David Harvey]

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.

david