Re: Roots mod a composite

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

On Sun, Sep 11, 2016 at 02:17:57PM -0400, Charles Greathouse wrote:
> GP has a very convenient function polrootsmod which gives the roots of a
> polynomial mod a prime. Is there a way to find -- or just count -- the
> roots of a polynomial mod a composite with a known factorization?
> 
> With squarefree moduli this is simple -- count the solutions mod each prime
> and multiply, or find the solutions mod each and CRT back together if you
> want each solution. So I guess the question is just about handling prime
> powers.

If N is small, you can use the naive method:
count(P,N)=my(s);for(x=0,N-1,if(subst(P,variable(P),x)%N==0,s++));s
(or better, use a table of difference)

If N is large the number of solutions can be quite large even for a
quadratic polynomial: x^2 mod 4^n has 2^n solutions... so it is not
realistic to return them all in such case.

The function polrootspadic(P,p,e) returns the p-adic roots of P.
This is the same as the roots of P mod p^e if P is squarefree modulo p
Otherwise you can miss some solutions.
For example x^2-3*x has 6 solution mod 27, while only 2 3-adic
solutions. (The number of p-adic solutions is bounded by the degree of
the polynomial).

Cheers,
Bill.