Re: computing all square root modulo a composite

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

On Sun, Oct 13, 2024 at 12:07:56AM -0400, Max Alekseyev wrote:
> 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?

factor() first perform trial division and then check the primetab table.
So any primes less that factorlimit will be found before primetab is 
looked at.

This is by design. Checking whether a number is divisible by entries in
primetab, without more information, is inefficient.

The true answer is that issquare should probably not support non prime moduli.
sqrt does not for example.
Support them slows down the case where the modulus is prime and is inefficient
when it is composite.

Cheers,
Bill.