Polynomial divisibility

[Charles Greathouse <charles.greathouse@case.edu>]

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