Re: Polynomials modulo p
- To: mathgroup at smc.vnet.net
- Subject: [mg37837] Re: [mg37816] Polynomials modulo p
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Thu, 14 Nov 2002 06:12:18 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
It's clearly a bug. I have nto investigated it carefully, but a quick look at Trace seem to suggest that the bug will occur only when the two polynomials are not relatively prime. If so it is easy to fix it without going into the details of the code. The built in function PolynomialGCD accepts the option Modulus and hasno bug so you can always divide your polynomials by the PolynomialGCD it gives you and apply ExtendedPolynomialGCD to the relatively prime polynomials that will result. I think it will then return the right answer and then you can get the answer to the original problem by multiplication. So here is my fix: << Algebra`PolynomialExtendedGCD` MyPolynomialExtendedGCD[a_, b_, p_] := With[{gcd = PolynomialGCD[a, b, \ Modulus -> p]}, { gcd, 1}*PolynomialMod[PolynomialExtendedGCD[##, Modulus -> p] & @@ Cancel[{a, b}/gcd, Modulus -> p], p]] It works in your case: d=2+x+x^2; a=Expand[d*(10+x),Modulus->11]; b=d*x; In[8]:= MyPolynomialExtendedGCD[a, b, 11] Out[8]= {2 + x + x^2, {10, 1}} Let me know if you discover it doesn't solve the problem in all cases. Andrzej Kozlowski Yokohama, Japan http://www.mimuw.edu.pl/~akoz/ http://platon.c.u-tokyo.ac.jp/andrzej/ On Wednesday, November 13, 2002, at 03:13 PM, Enric Meinhardt Llopis wrote: > Hi, I'm starting to use Mathematica 4.0 to work on polynomials. > > I'm having some problems with the package "PolynomialExtendedGCD" > (version 1.1), as it seems to fail on some inputs. Being unable to > contact Matthew Markert, the author of the package, I write to this > list asking for advice. > > It does not seem difficult to implement this function, but before > doing so I would like to know if anybody has had this problem before, > and how did she solve it. > > Or maybe I'm just doing something fundamentally wrong... > > A piece of code that shows unexpected behaviour follows: > > << Algebra`PolynomialExtendedGCD` > p := 11 > d = 2 + X + X^2 > a = Expand[d * (10 + X),Modulus->p] > b = d * X > PolynomialExtendedGCD[a,b,Modulus->p] > > It issues an error trying to calculate a negative power of zero. I > would be very grateful if anyone could help me. > > Thanks in advance (and sorry for the bad english). > Enric Meinhardt Llopis > > >