Re: computing all square root modulo a composite

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sat, Oct 12, 2024 at 05:52:09PM +0200, Karim Belabas wrote:
> * 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.

Well, one can alway use isNULL :) it never get old!

? install(Zn_quad_roots, GGG)
? isNULL(x=[])=x;
? f(N,B)=isNULL(Zn_quad_roots([N, factor(N)], 0, -B))
%3 = (N,B)->isNULL(Zn_quad_roots([N,factor(N)],0,-B))
? f(92,7)
%4 = []
? f(92,11)
%5 = []
? f(92,12)
%6 = [46,[14,32]]

Cheers,
Bill.