Re: computing all square root modulo a composite

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

On Sat, Oct 12, 2024 at 02:52:36PM -0400, Max Alekseyev wrote:
> Bill, Karim,
> 
> Thank you for clarifying the distinction between the factor_add_primes=1
> setting and manual calls to addprimes().
> I have a coupe of follow-up questions though:
> 
> 1) Can the threshold 2^24 be adjusted by the user? If not, I'd suggest
> using the value of factor_add_primes (when it's > 1) as this threshold.

No. 

I picked 2^24 so that the primetab array would not fill up too fast.

> 2) Even with all known prime factors of the modulus, the performance of
> issquare() on t_INTMOD's is unsatisfactory to my view.
> For example, the code below computes the number of quadratic residues below
> 10^5 modulo the same modulus via Zn_quad_roots() and via issquare(), and
> the latter is very bad.
> This makes me think that issquare() on t_INTMOD's with composite moduli
> should be totally avoided unless it's improved. Can it?

As I said, addprimes is not meant for small primes numbers.

The problem is that we cannot allow N to be replaced by
[N,factor(N)] in issquare since
issquare(Mod(a,[N,factor(N)])) is not valid GP syntax.

In C you can use Zn_issquare/Zn_ispower

? NF=[1000000000000001000000000000001,factor(1000000000000001000000000000001)];
? install(Zn_issquare,lGG)
? sum(r=0,10^5,Zn_issquare(r,NF[2]))
%5 = 9425
? ##
  ***   last result computed in 51 ms.

Cheers,
Bill.