John Cremona on Wed, 06 Apr 2011 18:33:32 +0200

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Polynomial divisibility

 To: Charles Greathouse <charles.greathouse@case.edu>
 Subject: Re: Polynomial divisibility
 From: John Cremona <john.cremona@gmail.com>
 Date: Wed, 6 Apr 2011 09:26:44 0700
 Cc: pariusers@list.cr.yp.to
 Deliverydate: Wed, 06 Apr 2011 18:33:32 +0200
 Dkimsignature: v=1; a=rsasha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkeysignature:mimeversion:inreplyto:references:date :messageid:subject:from:to:cc:contenttype :contenttransferencoding; bh=tGMooy/giFm9eEbIQAKX62a2Tq9EQMAY76zv/qUTKH0=; b=pvBluLR04B9YrDGF+6DFGVwatdzNrX1myVmy1ElL+1iwK4T6NDZ0dH1IlV1LXgq5D/ Ov5tsaaH9wv8fTdYD+OVapWyQ4ee1KMSRxhisiKkzLjSdaykReKPEywmJt0OcZW9+3ui ElUYdZWRTeSTaTD8eRpl9HoN7SWUnbTnyfLtA=
 Domainkeysignature: a=rsasha1; c=nofws; d=gmail.com; s=gamma; h=mimeversion:inreplyto:references:date:messageid:subject:from:to :cc:contenttype:contenttransferencoding; b=o62Kw95r6vz5AfiA1YxLwciLghmuD3uFCYHFFAaVcFEbuxP87tgEp1H2JRHAxJs76J vc9t1ncWWW+8dt15juzUBL4JJIE9Fe9dCDsmS7/SHUAE0sM5wWqqzlpxwD/IMV0kZV7f 9ewDEJ5dIvCHDlJF+0VvtSsqPzf4JbTVzYpv8=
 Inreplyto: <BANLkTi=t7FBTR=LHWUAjhTznCkA746O2vQ@mail.gmail.com>
 Mailinglist: contact pariusershelp@list.cr.yp.to; run by ezmlm
 References: <BANLkTi=t7FBTR=LHWUAjhTznCkA746O2vQ@mail.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^px).
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 64bit 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
>