Re: Polynomial divisibility

[John Cremona <john.cremona@gmail.com>]

Do you mean to count the number of roots P has modulo p, not counting
multiplicity?

If so then it is the degree of gcd(P,x^p-x).

John


On Wed, Apr 6, 2011 at 8:56 AM, Charles Greathouse
<charles.greathouse@case.edu> 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.
>
> 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
>