Re: computing all square root modulo a composite

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

* Karim Belabas [2024-10-12 17:41]:
> * 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.

Should have tested: this function returns NULL when -B is not a
quadratic residue mod N, which will crash gp. So one needs a 2 lines
wrapper to cater for this case.

When not NULL, output format is [M, v] where x is a square root of
B mod N iff x mod M belongs to the vector v. When (4B, N) = 1, we have M = N,
else it will be a proper divisor.

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/