Bill Allombert on Wed, 06 Apr 2011 18:39:04 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Polynomial divisibility |
On Wed, Apr 06, 2011 at 11:56:40AM -0400, Charles Greathouse wrote: > I wanted to know if there's an efficient way to count the number of > residue classes (mod p) for which the polynomial is divisible by p. > The straightforward approach > > sum(n=1,p,substpol(P,x,Mod(n,p))==0) > > is slow. > > In my case the polynomial is reducible and of degree 62 with > 'reasonable' coefficients (wordsize on a 64-bit machine, the largest > is 44 bits). I could test the smaller polynomials first but I think > the overhead would be more expensive than the benefit -- it's rare > that p will divide any given value of the polynomial. Assuming that p is prime and P has integral coefficients, why not use polrootsmod ? You can do a bit better though: poldegree(FpX_gcd(P,FpXQ_pow(x,p,P,p)-x)) with the suitable install() invocation. Cheers, Bill.