Re: computing all square root modulo a composite

[Max Alekseyev <maxale@gmail.com>]

Bill, thank you for clarification. 

It is unfortunate that trial division is unconditionally prioritized over the primetab look-up. I think a smarter strategy is possible here - e.g. rely not just on primelimit but also on the size of prmetab. Say, assuming that #primetab < primepi(primelimit), make trivial division over the first #primetab primes, then try division by then primes in primetab, then continue trial division with other primes below primelimit. Ideally, PARI could provide a few different strategies (including the current one) about factor priorities for the user to choose from.

From a different perspective, it should be possible to extend a kind-of "[N,factor(N)]" interface to all functions internally using factor() by creating a system-wide Map() that will map (some) N to their factorizations. Then, factor(N) would first check if that Map contains a handy factorization for N. So, adding the factorization of N to that Map will make N efficiently factorable by any function, without explicitly providing the factorization of N to that function. This would be similar to primetab, but storing not just primes but whole factorizations for the numbers of interest.

Regards,

Max

On Sun, Oct 13, 2024 at 3:04 AM Bill Allombert <Bill.Allombert@math.u-bordeaux.fr> wrote:

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.