# 2-adic roots (Re: bdiv vs redc)

Niels Möller nisse at lysator.liu.se
Fri Jul 20 00:03:05 CEST 2012

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.