Re: computing all square root modulo a composite

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.

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?

Regards,

Max

===

? default(factor_add_primes,1);
? install(Zn_quad_roots, GGG);
? NF = [1000000000000001000000000000001, factor(1000000000000001000000000000001)];
? addprimes(NF[2][,1])
%4 = [3, 238681, 333667, 4185502830133110721]
? myisNULL(x=[0,[]])=x;
? sum(r=0,10^5,#myisNULL(Zn_quad_roots(NF,0,-r))[2]!=0)
%6 = 9425
? ##
*** last result: cpu time 840 ms, real time 843 ms.
? sum(r=0,10^5,issquare(Mod(r,NF[1])))
%7 = 9425
? ##
*** last result: cpu time 39,901 ms, real time 39,960 ms.

On Sat, Oct 12, 2024 at 1:43 PM Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> wrote:

* Max Alekseyev [2024-10-12 18:08]:
> On Sat, Oct 12, 2024 at 11:46 AM Karim Belabas <
> Karim.Belabas@math.u-bordeaux.fr> wrote:
> > * Max Alekseyev [2024-10-12 16:58]:
> > > PS. I forgot to mention that I do have
> > > default(factor_add_primes,1);
> > > and so it's not repetitive factoring that slows things down.
> >
> > Using this default is easy but usually not best. Either use the
> > [N,factor(N)] format for the functions that support it, i.e., most
> > arithmetic
> > functions. Or use addprimes(factor(N)[,1]).
> >
> >
> Karim,
> Could you please elaborate on your last comment?
> How explicit calling addprimes(factor(N)[,1]) is better than just having
> default(factor_add_primes,1) and not calling addprimes() ?

Please read the documentation: factor_add_primes will help you by
storing largish primes (larger than 2^24). For tiny numbers like
yours, trial division does all the work; since smaller primes are not
stored, you still pay the bulk of the factoring effort is still
undertaken.

As any "automatic" feature, factor_add_primes is a compromise and makes
some choices which should be OK by default: storing too many primes will
blow up the memory AND slow down factorization (in effect, you''d be
extending the range of trial division beyond what's optimal on average).

With addprimes, *you* make the choices. Should be an improvement :-)

Cheers,

K.B.
--
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/