Bill Allombert on Sun, 11 Sep 2016 21:14:05 +0200

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Roots mod a composite

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:
(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).