[GAP Forum] Bug showing up in computations with polynomials over finite fields.
Richard Todd
rmtodd at servalan.servalan.com
Tue May 22 19:16:39 BST 2012
I've been working on some stuff involving polynomials over fields GF(2^m),
and have come across a most peculiar bug where sometimes the
GcdRepresentation function fails. This is on GAP 4.4.12 on FreeBSD 10-CURRENT
on amd64, but the same result appears with GAP 4.4.12 on Ubuntu 10.04.4/i386.
I've come up with the following test
case: consider this function:
----------------------------------------------------------------------
Test1 := function()
local f, x, y, t;
x := Indeterminate(GF(2), "x");
y := Indeterminate(GF(4), "y");
f := x^75+x^74+x^73+x^72+x^69+x^68+x^65+x^63+x^61+x^57+x^53+x^51+x^49+x^48+x^47+x^4\
6+x^44+x^43+x^41+x^40+x^38+x^36+x^35+x^32+x^31+x^28+x^26+x^24+x^20+x^16+x^14+x\
^12+x^11+x^10+x^9+x^7+x^6+x^4+x^3+Z(2)^0;
t:= y^3+Z(2^2)*y^2+Z(2^2)*y+Z(2)^0;
Print(GcdRepresentation(f, (x^111+1)/f), "\n");
Print(GcdRepresentation(t, (y^5+1)/t), "\n");
Print(GcdRepresentation(f, (x^111+1)/f), "\n");
end;
----------------------------------------------------------------------
When run, we get the following result:
gap> Test1();
[ x^35+x^31+x^29+x^21+x^17+x^13+x^7+x^3,
x^74+x^72+x^68+x^48+x^46+x^44+x^40+x^38+x^36+x^32+x^28+x^26+x^24+x^20+x^16+x\
^14+x^12+x^10+x^6+x^4+Z(2)^0 ]
[ Z(2^2)*y, Z(2^2)*y^2+Z(2)^0 ]
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `PROD' on 2 arguments called from
tmp[2] * ns[i] called from
GcdRepresentation( f, (x ^ 111 + 1) / f ) called from
<function>( <arguments> ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> tmp[2];
fail
brk>
Note that the third call to GcdRepresentation in Test1() fails, even though
it's the exact same polynomial used in the *first* call, which worked and
gave the correct result. Further investigation finds that taking out the
*second* call to GcdRepresentation (the one with a polynomial over GF(4))
allows the last call to GcdRepresentation to succeed -- somehow the 2nd
call is messing things up for the subsequent call.
Diving into the GAP code a bit further, I came up with the following test,
using a copy of the GCDRepresentationOp function with some debugging
prints and assertions hacked in:
----------------------------------------------------------------------
GRO:=
function( R, x, y )
local f, g, h, fx, gx, hx, q, t, i;
i:=0;
f := x; fx := One( R );
g := y; gx := Zero( R );
while g <> Zero( R ) do
i:=i+1;
t := QuotientRemainder( R, f, g );
h := g; hx := gx;
g := t[2]; gx := fx - t[1] * gx;
Assert(0, gx + t[1]*hx = fx);
f := h; fx := hx;
Print(i, " t=", t, " f=", f, " fx=", fx, " g=", g, " gx=", gx, "\n");
od;
q := Quotient(R, StandardAssociate(R, f), f);
Print("q=", q, "\n");
if y = Zero( R ) then
return [ q * fx, Zero( R ) ];
else
Print(" q*(f-fx*x)=", q * (f - fx * x), " y=", y, "\n");
return [ q * fx, Quotient( R, q * (f - fx * x), y ) ];
fi;
end;
Test1 := function()
local f, x, y, t;
x := Indeterminate(GF(2), "x");
y := Indeterminate(GF(4), "y");
f := x^75+x^74+x^73+x^72+x^69+x^68+x^65+x^63+x^61+x^57+x^53+x^51+x^49+x^48+x^47+x^4\
6+x^44+x^43+x^41+x^40+x^38+x^36+x^35+x^32+x^31+x^28+x^26+x^24+x^20+x^16+x^14+x\
^12+x^11+x^10+x^9+x^7+x^6+x^4+x^3+Z(2)^0;
t:= y^3+Z(2^2)*y^2+Z(2^2)*y+Z(2)^0;
Print(GRO(DefaultRing(f), f, (x^111+1)/f), "\n");
Print(GRO(DefaultRing(t), t, (y^5+1)/t), "\n");
Print(GRO(DefaultRing(f), f, (x^111+1)/f), "\n");
end;
----------------------------------------------------------------------
On executing this test, we get the result that at a certain point in the
GCD computation, doing computations on polynomials over GF(2) gives the
entirely wrong result caught by the Assert() I added (see log output
below). Note, again, that the first call to the GCD routine on the
polynomial works, and gives the correct results all through the
computation, but the final GCD computation goes off the rails at the
point indicated by the Assert() I added.
Any suggestions what's going on here? It looks like something's off
somewhere in the low-level routines for handling +/- operations on
these polynomials....
Richard
gap> Test1();
1 t=[ x^39+x^37+x^35+x^33+x^27+x^25+x^19+x^15+x^11+x^3,
x^31+x^30+x^25+x^24+x^21+x^17+x^15+x^12+x^11+x^9+x^4+Z(2)^0
] f=x^36+x^35+x^32+x^31+x^30+x^29+x^26+x^22+x^21+x^20+x^18+x^17+x^16+x^14+x^1\
3+x^12+x^8+x^7+x^4+x^3+Z(2)^0 fx=0*Z(2) g=x^31+x^30+x^25+x^24+x^21+x^17+x^15+x\
^12+x^11+x^9+x^4+Z(2)^0 gx=Z(2)^0
2 t=[ x^5+x, x^26+x^25+x^22+x^21+x^16+x^10+x^9+x^8+x^7+x^4+x^3+x+Z(2)^0
] f=x^31+x^30+x^25+x^24+x^21+x^17+x^15+x^12+x^11+x^9+x^4+Z(2)^0 fx=Z(2)^0 g=x\
^26+x^25+x^22+x^21+x^16+x^10+x^9+x^8+x^7+x^4+x^3+x+Z(2)^0 gx=x^5+x
3 t=[ x^5+x, x^25+x^24+x^23+x^22+x^14+x^13+x^10+x^9+x^6+x^2+x+Z(2)^0
] f=x^26+x^25+x^22+x^21+x^16+x^10+x^9+x^8+x^7+x^4+x^3+x+Z(2)^0 fx=x^5+x g=x^2\
5+x^24+x^23+x^22+x^14+x^13+x^10+x^9+x^6+x^2+x+Z(2)^0 gx=x^10+x^2+Z(2)^0
4 t=[ x, x^24+x^23+x^22+x^21+x^16+x^15+x^14+x^11+x^9+x^8+x^4+x^2+Z(2)^0
] f=x^25+x^24+x^23+x^22+x^14+x^13+x^10+x^9+x^6+x^2+x+Z(2)^0 fx=x^10+x^2+Z(2)^\
0 g=x^24+x^23+x^22+x^21+x^16+x^15+x^14+x^11+x^9+x^8+x^4+x^2+Z(2)^0 gx=x^11+x^5\
+x^3
5 t=[ x, x^17+x^16+x^15+x^14+x^13+x^12+x^6+x^5+x^3+x^2+Z(2)^0
] f=x^24+x^23+x^22+x^21+x^16+x^15+x^14+x^11+x^9+x^8+x^4+x^2+Z(2)^0 fx=x^11+x^\
5+x^3 g=x^17+x^16+x^15+x^14+x^13+x^12+x^6+x^5+x^3+x^2+Z(2)^0 gx=x^12+x^10+x^6+\
x^4+x^2+Z(2)^0
6 t=[ x^7+x^3+x, x^16+x^15+x^12+x^11+x^10+x^9+x^5+x^2+x+Z(2)^0
] f=x^17+x^16+x^15+x^14+x^13+x^12+x^6+x^5+x^3+x^2+Z(2)^0 fx=x^12+x^10+x^6+x^4\
+x^2+Z(2)^0 g=x^16+x^15+x^12+x^11+x^10+x^9+x^5+x^2+x+Z(2)^0 gx=x^19+x^17+x^15+\
x^13+x^11+x^7+x^5+x^3+x
7 t=[ x, x^15+x^14+x^11+x^10+x^5+x+Z(2)^0
] f=x^16+x^15+x^12+x^11+x^10+x^9+x^5+x^2+x+Z(2)^0 fx=x^19+x^17+x^15+x^13+x^11\
+x^7+x^5+x^3+x g=x^15+x^14+x^11+x^10+x^5+x+Z(2)^0 gx=x^20+x^18+x^16+x^14+x^10+\
x^8+Z(2)^0
8 t=[ x, x^10+x^9+x^6+x^5+Z(2)^0
] f=x^15+x^14+x^11+x^10+x^5+x+Z(2)^0 fx=x^20+x^18+x^16+x^14+x^10+x^8+Z(2)^0 g\
=x^10+x^9+x^6+x^5+Z(2)^0 gx=x^21+x^13+x^9+x^7+x^5+x^3
9 t=[ x^5, x+Z(2)^0
] f=x^10+x^9+x^6+x^5+Z(2)^0 fx=x^21+x^13+x^9+x^7+x^5+x^3 g=x+Z(2)^0 gx=x^26+x\
^20+x^16+x^12+Z(2)^0
10 t=[ x^9+x^5, Z(2)^0
] f=x+Z(2)^0 fx=x^26+x^20+x^16+x^12+Z(2)^0 g=Z(2)^0 gx=x^35+x^31+x^29+x^21+x^\
17+x^13+x^7+x^3
11 t=[ x+Z(2)^0, 0*Z(2)
] f=Z(2)^0 fx=x^35+x^31+x^29+x^21+x^17+x^13+x^7+x^3 g=0*Z(2) gx=x^36+x^35+x^3\
2+x^31+x^30+x^29+x^26+x^22+x^21+x^20+x^18+x^17+x^16+x^14+x^13+x^12+x^8+x^7+x^4\
+x^3+Z(2)^0
q=Z(2)^0
q*(f-fx*x)=x^110+x^109+x^108+x^107+x^106+x^105+x^104+x^103+x^102+x^101+x^99+x\
^97+x^96+x^95+x^94+x^93+x^91+x^90+x^88+x^87+x^86+x^84+x^83+x^82+x^81+x^79+x^78\
+x^77+x^76+x^75+x^72+x^71+x^69+x^66+x^65+x^63+x^62+x^61+x^60+x^57+x^55+x^54+x^\
53+x^52+x^51+x^48+x^47+x^45+x^44+x^43+x^42+x^41+x^39+x^38+x^36+x^33+x^31+x^30+\
x^27+x^26+x^24+x^22+x^21+x^19+x^18+x^15+x^13+x^12+x^11+x^9+x^6+x^3+Z(2)^0 y=x^\
36+x^35+x^32+x^31+x^30+x^29+x^26+x^22+x^21+x^20+x^18+x^17+x^16+x^14+x^13+x^12+\
x^8+x^7+x^4+x^3+Z(2)^0
[ x^35+x^31+x^29+x^21+x^17+x^13+x^7+x^3,
x^74+x^72+x^68+x^48+x^46+x^44+x^40+x^38+x^36+x^32+x^28+x^26+x^24+x^20+x^16+x\
^14+x^12+x^10+x^6+x^4+Z(2)^0 ]
1 t=[ y, Z(2^2)^2*y+Z(2)^0
] f=y^2+Z(2^2)*y+Z(2)^0 fx=0*Z(2) g=Z(2^2)^2*y+Z(2)^0 gx=Z(2)^0
2 t=[ Z(2^2)*y, Z(2)^0 ] f=Z(2^2)^2*y+Z(2)^0 fx=Z(2)^0 g=Z(2)^0 gx=Z(2^2)*y
3 t=[ Z(2^2)^2*y+Z(2)^0, 0*Z(2)
] f=Z(2)^0 fx=Z(2^2)*y g=0*Z(2) gx=y^2+Z(2^2)*y+Z(2)^0
q=Z(2)^0
q*(f-fx*x)=Z(2^2)*y^4+Z(2^2)^2*y^3+Z(2^2)^2*y^2+Z(2^2)*y+Z(2)^0 y=y^2+Z(2^2)*\
y+Z(2)^0
[ Z(2^2)*y, Z(2^2)*y^2+Z(2)^0 ]
1 t=[ x^39+x^37+x^35+x^33+x^27+x^25+x^19+x^15+x^11+x^3,
x^31+x^30+x^25+x^24+x^21+x^17+x^15+x^12+x^11+x^9+x^4+Z(2)^0
] f=x^36+x^35+x^32+x^31+x^30+x^29+x^26+x^22+x^21+x^20+x^18+x^17+x^16+x^14+x^1\
3+x^12+x^8+x^7+x^4+x^3+Z(2)^0 fx=0*Z(2) g=x^31+x^30+x^25+x^24+x^21+x^17+x^15+x\
^12+x^11+x^9+x^4+Z(2)^0 gx=Z(2)^0
2 t=[ x^5+x, x^26+x^25+x^22+x^21+x^16+x^10+x^9+x^8+x^7+x^4+x^3+x+Z(2)^0
] f=x^31+x^30+x^25+x^24+x^21+x^17+x^15+x^12+x^11+x^9+x^4+Z(2)^0 fx=Z(2)^0 g=x\
^26+x^25+x^22+x^21+x^16+x^10+x^9+x^8+x^7+x^4+x^3+x+Z(2)^0 gx=x^5+x
3 t=[ x^5+x, x^25+x^24+x^23+x^22+x^14+x^13+x^10+x^9+x^6+x^2+x+Z(2)^0
] f=x^26+x^25+x^22+x^21+x^16+x^10+x^9+x^8+x^7+x^4+x^3+x+Z(2)^0 fx=x^5+x g=x^2\
5+x^24+x^23+x^22+x^14+x^13+x^10+x^9+x^6+x^2+x+Z(2)^0 gx=x^10+x^2+Z(2)^0
4 t=[ x, x^24+x^23+x^22+x^21+x^16+x^15+x^14+x^11+x^9+x^8+x^4+x^2+Z(2)^0
] f=x^25+x^24+x^23+x^22+x^14+x^13+x^10+x^9+x^6+x^2+x+Z(2)^0 fx=x^10+x^2+Z(2)^\
0 g=x^24+x^23+x^22+x^21+x^16+x^15+x^14+x^11+x^9+x^8+x^4+x^2+Z(2)^0 gx=x^11+x^5\
+x^3
5 t=[ x, x^17+x^16+x^15+x^14+x^13+x^12+x^6+x^5+x^3+x^2+Z(2)^0
] f=x^24+x^23+x^22+x^21+x^16+x^15+x^14+x^11+x^9+x^8+x^4+x^2+Z(2)^0 fx=x^11+x^\
5+x^3 g=x^17+x^16+x^15+x^14+x^13+x^12+x^6+x^5+x^3+x^2+Z(2)^0 gx=x^12+x^10+x^6+\
x^4+x^2+Z(2)^0
6 t=[ x^7+x^3+x, x^16+x^15+x^12+x^11+x^10+x^9+x^5+x^2+x+Z(2)^0
] f=x^17+x^16+x^15+x^14+x^13+x^12+x^6+x^5+x^3+x^2+Z(2)^0 fx=x^12+x^10+x^6+x^4\
+x^2+Z(2)^0 g=x^16+x^15+x^12+x^11+x^10+x^9+x^5+x^2+x+Z(2)^0 gx=x^19+x^17+x^15+\
x^13+x^11+x^7+x^5+x^3+x
7 t=[ x, x^15+x^14+x^11+x^10+x^5+x+Z(2)^0
] f=x^16+x^15+x^12+x^11+x^10+x^9+x^5+x^2+x+Z(2)^0 fx=x^19+x^17+x^15+x^13+x^11\
+x^7+x^5+x^3+x g=x^15+x^14+x^11+x^10+x^5+x+Z(2)^0 gx=x^20+x^18+x^16+x^14+x^10+\
x^8+Z(2)^0
8 t=[ x, x^10+x^9+x^6+x^5+Z(2)^0
] f=x^15+x^14+x^11+x^10+x^5+x+Z(2)^0 fx=x^20+x^18+x^16+x^14+x^10+x^8+Z(2)^0 g\
=x^10+x^9+x^6+x^5+Z(2)^0 gx=x^21+x^13+x^9+x^7+x^5+x^3
9 t=[ x^5, x+Z(2)^0
] f=x^10+x^9+x^6+x^5+Z(2)^0 fx=x^21+x^13+x^9+x^7+x^5+x^3 g=x+Z(2)^0 gx=x^26+x\
^20+x^16+x^12+Z(2)^0
Assertion failure at
Assert( 0, gx + t[1] * hx = fx );
called from
GRO( DefaultRing( f ), f, (x ^ 111 + 1) / f ) called from
<function>( <arguments> ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you may 'return;' to continue
brk> fx;
x^21+x^13+x^9+x^7+x^5+x^3
brk> hx;
x^26+x^20+x^16+x^12+Z(2)^0
brk> t[1]
> ;
x^9+x^5
brk> t[1]*hx;
x^35+x^31+x^29+x^17+x^9+x^5
brk> gx;
x^35+x^31+x^29+x^23+x^21+x^17+x^13+x^7+x^3
brk> gx+t[1]*hx;
x^23+x^21+x^13+x^9+x^7+x^5+x^3
brk> fx;
x^21+x^13+x^9+x^7+x^5+x^3
brk>
More information about the Forum
mailing list