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 <email@example.com>
- Subject: Re: Polynomial divisibility
- From: John Cremona <firstname.lastname@example.org>
- Date: Wed, 6 Apr 2011 09:26:44 -0700
- Cc: email@example.com
- Delivery-date: Wed, 06 Apr 2011 18:33:32 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type :content-transfer-encoding; bh=tGMooy/giFm9eEbIQAKX62a2Tq9EQMAY76zv/qUTKH0=; b=pvBluLR04B9YrDGF+6DFGVwatdzNrX1myVmy1ElL+1iwK4T6NDZ0dH1IlV1LXgq5D/ Ov5tsaaH9wv8fTdYD+OVapWyQ4ee1KMSRxhisiKkzLjSdaykReKPEywmJt0OcZW9+3ui ElUYdZWRTeSTaTD8eRpl9HoN7SWUnbTnyfLtA=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; b=o62Kw95r6vz5AfiA1YxLwciLghmuD3uFCYHFFAaVcFEbuxP87tgEp1H2JRHAxJs76J vc9t1ncWWW+8dt15juzUBL4JJIE9Fe9dCDsmS7/SHUAE0sM5wWqqzlpxwD/IMV0kZV7f 9ewDEJ5dIvCHDlJF+0VvtSsqPzf4JbTVzYpv8=
- In-reply-to: <BANLkTi=t7FBTR=LHWUAjhTznCkA746O2vQ@mail.gmail.com>
- Mailing-list: contact firstname.lastname@example.org; 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
If so then it is the degree of gcd(P,x^p-x).
On Wed, Apr 6, 2011 at 8:56 AM, Charles Greathouse
> 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