Charles Greathouse on Wed, 06 Apr 2011 19:42:14 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Polynomial divisibility


Thank you both.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

On Wed, Apr 6, 2011 at 12:32 PM, Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr> wrote:
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.