Charles Greathouse on Wed, 06 Apr 2011 18:12:19 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Polynomial divisibility |
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. I'm willing to code in PARI if GP does not suffice. It's possible that there's a different approach that doesn't enumerate cases but I don't know of one. Charles Greathouse Analyst/Programmer Case Western Reserve University