Re: computing all square root modulo a composite

[Max Alekseyev <maxale@gmail.com>]

On Sat, Oct 12, 2024 at 12:05 PM Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> wrote:

* Max Alekseyev [2024-10-12 17:56]:
> As for the name, maybe sqrtall() ?

sqrtmod rather. Also note that function gives you all roots of any
monic quadratic polynomial, not only square roots.

And it has a weird output format, which makes perfect sense if you
think of it (you get the most precise mathematical information). It
does not give you all solutions mod N but modulo M | N, whose
lifts + k (N/M) mod N, 0 <= k < M are the solutions mod N.

Yes, it makes perfect sense. In fact, my custom function may have varying moduli in the result as well.

 

I don't think we want that as a GP function.

That's a pity.

Regards,

Max