Re: computing all square root modulo a composite

[Max Alekseyev <maxale@gmail.com>]

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

> 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.

I understand that there are reasons for the 2^24 threshold value, but why not let users adjust this threshold if needed.

 

> 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.

What does this mean exactly?

Karim said earlier that the concern with small primes is that there are a lot of them, while adding too many primes via addprimes() would have a negative impact on the performance. I understand that. However, what if I'm interested in fast recurring factoring of just a few fixed numbers - wouldn't it be helpful to call addprimes() on their prime factors irrespectively of whether they are large or small?

 

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.

I understand that issquare(Mod(a,[N,factor(N)])) is not available, but why a comparable performance cannot be achieved for issquare(Mod(a,N)) by providing the prime factors of N via addprimes() beforehand? 

 

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.

Thank you for this alternative. This is helpful as I'm about to abandon using issquare() on t_INTMODs, although I still have a hope that it can be redeemed somehow.

Regards,

Max