2-adic roots (Re: bdiv vs redc)

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

> I haven't really looked into the perfpow code or theory, but let me
> think aloud...

I've looked a bit more into this. This is my current understanding:

1. Powers of two have to be handled specially, so consider only odd
   numbers, we'll be working with the multiplicative group Z_{2^k}^*.

2. An odd number has a square root (or in fact two) if and only if it's
   = 1 (mod 4).

3. A reasonable square root algorithm is the standard Newton iteration
   x_j which converges to a^{-1/2}, each step extending from \ell bits
   of precision to 2 \ell - 1. I think which root we'll converge to has
   to be determined by the initial value, if it's 1 or 3 (mod 4).

3. When n is odd, all odd numbers have exactly one nth root mod 2^k.
   It's a^{n'} (mod 2^k), where n' = n^{-1} (mod 2^{k-1}), since
   \phi(2^k) = 2^{k-1}. This formula also makes it practical to tabulate
   the roots for small k and *arbitrary* n, since only the k-1 lowest
   bits of n matter.

4. A reasonable nth root algorithm is a newton iteration x_j converging
   to x = a^{1/n-1}, so we get the nth root as x a. The iteration
   extends \ell bits of precision to 2\ell, I think. And the iteration
   only needs division by n. (Since this is not how it's usually done
   for plain nth roots, I guess the iteration gets impractical in that
   setting, due to large intermediate values or something like that. Or
   maybe I'm missing something?).

Does this seem right?

Regards,
/Niels

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