Re: computing all square root modulo a composite

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

On Sat, Oct 12, 2024 at 12:52:08PM -0400, Max Alekseyev wrote:
> 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.

? factor(N)
%12 = [3,1;238681,1;333667,1;4185502830133110721,1]

but addprimes is not intended for such small primes like 238681 and 333667.
In fact factor_add_primes only keep factors larger than 2^24.

? N=1000000000000001000000000000001
%8 = 1000000000000001000000000000001
? addprimes(factor(N)[,1])
%9 = [3,238681,333667,4185502830133110721]
? for(i=1,10^5,factor(N))
? ##
  ***   last result computed in 1,552 ms.
? for(i=1,10^5,factor(N,3))
? ##
  ***   last result computed in 46 ms.

Cheers,
Bill