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
ni...@lysator.liu.se (Niels Möller) writes:
Correction: Each iteration gets from \ell to 2 \ell-2, and it needs 2
\ell-1 bits of precision for intermediate values.
Yet another correction, after more work on the implementation.
For numbers x = 1 (mod 8), there are four square roots mod 2^k. If
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