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