Re: computing all square root modulo a composite

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

On Sun, Oct 13, 2024 at 11:21:43AM -0400, Max Alekseyev wrote:
> 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.

issquare/ispower are about the only GP functions with this bug.
The best course of action is to remove support for composite moduli to both.
Then we can add two functions, znissquare and znispower that allow to pass
factor(N).

This will fix the performance problem without requiring
an overengineered addprime.

In the worst can, you can easily rewrite issquare in GP using the
factorisation, so it is not a big loss.

Cheers,
Bill.