Re: computing all square root modulo a composite

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* 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/