2-adic roots (Re: bdiv vs redc)

[Niels Möller]

Replying to myself yet again...

> For the power x^n, I currently use mpn_powlo. But the least significant
> half is known from the previous iteration, so wraparound would be
> desirable. To me it would make some sense with a pow function for (mod
> (2^k - 1)), i.e., using mpn_mulmod_bnm1 and mpn_sqrmod_bnm1.

On second though, I don't think that would work. One would need to do
the wraparound reconstruction for each square and multiply during the
powering algorithm. And then it's not enough to store the low half of
x^n from the previous iteration, one needs to store *all* the
intermediate values from the earlier (mod B^k) powering.

The subproblem here is: Compute x^n (mod B^{2k}), taking maximun
advantage of a previous computation of x^n (mod B^k).

I could well be missing some simpler trick.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.