Re: computing all square root modulo a composite

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Max Alekseyev [2024-10-12 16:50]:
> On Tue, Oct 1, 2024 at 4:56 AM Bill Allombert <
> Bill.Allombert@math.u-bordeaux.fr> wrote:
> 
> >
> > Internally, we have a function Zn_quad_roots that compute all the solution
> > of x^2+b*x+c mod N
> > for composite N.
> > Maybe we could add it to GP if we find a GP interface to it.
> >
> >
> Bill, I'd truly appreciate having such a function.

You have it already:

  install(Zn_quad_roots, GGG)
  Zn_quad_roots([N, factor(N)], 0, -B)

should output all square roots of B mod N. (Didn't test :-)
Of course, [N, factor(N)] should be precomputed.

Cheers,

    K.B.
-- 
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/