About sqrt_exact...

[Niels Möller]

marco.bodrato at tutanota.com writes:

>> 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.
>>
> There are exactly 4. Let's say that the highest 2 bits can be 00, 01, 10 or 11.
> This means that if you search the square roots mod 2*B^n, you will
> find exactly 2 that fit in n limbs, and they are one the negation of
> the other one.

Seems I've forgotten much of bsqrt (even though I think I was involved
somehow when it was added). And it's for odd numbers only, right? Thanks
for reminding me.

So then a sqrt_exact could first process trailing zero bits (must be an
even number). So say what remains is an odd number of 4n limbs. Call
bsqrt on the low n + 1 limbs (one extra for overlap), and sqrtrem on the
top 2n limbs (middle quarter of the input completely ignored). Use the
overlapping limb to select the right sqrt from binv and check that result
can be glued in a consistent way with the high part. Other variants of
splitting are possble, e.g, bsqrt on low third, sqrtrem on top third.

I think that would qualify as a bidirectional algorithm. If it's
actually useful, I don't know.

Regards,
/Niels

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