About sqrt_exact...

[Niels Möller]

Torbjörn Granlund <tg at gmplib.org> writes:

> I have not followed this thread, but would something akin to Jebelean's
> bidirectional exact division algorithm work for sqrt_exact?

Interesting question. Let me think aloud.

Say input is 4n limbs, with square root of size 2n. Then top n limbs of
the outout would be (non-exact) square root of the top 2n limbs of the
input (rounded upwards, I think).

Low n limbs of the output would be a square root of the input mod B^n,
but since B is a power of two I'd expect that there are plenty of square
roots, so that doesn't seem so helpful. One could try to compute a
square root mod some odd number, e.g., B^n + 1, but if I remember a bit
of number theory there may still be plenty of square roots, depending on
how that odd number factors. And combining with the high part of the
root gets unobvious.

If one can find a prime p > B^2n (or maybe a prime power p^k, p odd?),
and there's some really efficient way to compute square roots modulo
that number, that would be an exact square root algorithm (but not a
"bidirectional" one). But I would be a bit surprised if that could beat
the current non-modular square root algorithm.

For prime powers, there seems to be a way to lift a square root mod p^k
to a root mod p^{k+1}. But to be able to compete with Newton iteration,
one would need an efficient way to lift to a square root mod p^{2k},
right?

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.