About sqrt_exact...

[marco.bodrato at tutanota.com]

Ciao Paul,
16 giu 2026, 09:33 da Paul.Zimmermann at inria.fr:

> Hensel lifting should be able to lift a square root mod p to mod p^2.
>

The current code in mpn/generic/bsqrtinv.c actually compute the square root of the inverse.
Here are a couple of comments from that file:

   Iterates
     r' <-- (3r - r^3 y) / 2
   using Hensel lifting.  Since we divide by two, the Hensel lifting is
   somewhat degenerates.  Therefore, we lift from 2^b to 2^{b+1}-1.

   FIXME:
[...]
     (2) Rewrite iteration as
           r' <-- r - r (r^2 y - 1) / 2
         and take advantage of zero low part of r^2 y - 1.

Basically a Hensel lifting is already used, but it could be implemented more efficiently.

Ĝis,m