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


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
Case Western Reserve University