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
>
>
>