Re: computing all square root modulo a composite

Bill,

Thank you for the idea with isNULL!

Now, PARI does beat SageMath when Zn_quad_roots is called on [N,factor(N)].

However, PARI is much slower when Zn_quad_roots is called on just N even if default(factor_add_primes,1) is set:

? default(factor_add_primes,1);
? install(Zn_quad_roots, GGG);
? NF = [1000000000000001000000000000001, factor(1000000000000001000000000000001)];
? myisNULL(x=[0,[]])=x;
? sum(r=0,10^5,#myisNULL(Zn_quad_roots(NF,0,-r))[2])
%6 = 111953
? ##
*** last result: cpu time 283 ms, real time 283 ms.

? sum(r=0,10^5,#myisNULL(Zn_quad_roots(NF[1],0,-r))[2])
%7 = 111953
? ##
*** last result: cpu time 6,970 ms, real time 6,974 ms.

Regards,

Max

On Sat, Oct 12, 2024 at 12:42 PM Bill Allombert <Bill.Allombert@math.u-bordeaux.fr> wrote:

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.