[GAP Forum] Bug showing up in computations with polynomials over finite fields.
Alexander Hulpke
hulpke at math.colostate.edu
Wed May 23 16:23:15 BST 2012
Dear Richard Todd,
Thank you for reporting and analyzing this bug. The error is indeed in an internal routine (polynomials store a factor x^n specially and thus need to shift coefficient lists. The bug was in the shift routine).
We have a fix for this that will be in the next release, as it involves a change of kernel code it is not easy to provide a patch.
If this problem however is holding your research please contact me privately and I will see what can be done.
Best wishes,
Alexander Hulpke
On May 22, 2012, at 5/22/12 12:16, Richard Todd wrote:
> 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>
>
>
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
More information about the Forum
mailing list