Re: computing all square root modulo a composite

On Sat, Oct 12, 2024 at 10:49 AM Max Alekseyev <maxale@gmail.com> wrote:

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.

On a related note, below is my naive function computing all square roots of a given t_INTMOD. Somehow it badly loses to SageMath's built-in sqrt() function that provides an ability to get all the roots out of the box.
While there is no built-in alternative in PARI/GP, is there a way to speed up my function?
Thanks,
Max

? sum(r=0,10^5, #asqrtintmod(Mod(r,1000000000000001000000000000001)) )
%14 = 111953
? ##
*** last result: cpu time 16,544 ms, real time 16,580 ms.

sage: %time sum(len(sqrt(Mod(r,1000000000000001000000000000001),all=True,extend=False)) for r in (0..10^5))
CPU times: user 1.92 s, sys: 280 µs, total: 1.92 s
Wall time: 1.92 s
111953

I've played more with my code and Zn_quad_roots and now know whom to blame for the bad performance - it's issquare(). See experiments below.

Now the question is how to avoid using it - what would be the right way to wrap Zn_quad_roots and catch cases when no roots exist?

Or, relatedly, can the performance of issquare() be improved?

Regards,

Max

===

? default(factor_add_primes,1);
? install(Zn_quad_roots, GGG);
? NF = [1000000000000001000000000000001, factor(1000000000000001000000000000001)];
? sum(r=0,10^5, if(issquare(Mod(r,NF[1])),#(Zn_quad_roots(NF,0,-r)[2])))
%4 = 111953
? ##
*** last result: cpu time 15,263 ms, real time 15,266 ms.
? R = select(x->issquare(Mod(x,NF[1])),vector(10^5+1,r,r-1));
? ##
*** last result: cpu time 15,932 ms, real time 15,944 ms.
? foreach(R,r,Zn_quad_roots(NF,0,-r))
? ##
*** last result: cpu time 105 ms, real time 105 ms.
? #R
%7 = 9425

===