On Thursday 03 February 2011, Thomas Gueuning wrote:
> First of all, congratulations for this free and wonderfull software.
>
> I have a question about GF(2).This is maybe a bit stupid but I cannot find
> the answer anywere.
>
> When I use this code, I don't understand why y^3 is still there because I
> think this is equal to y for both 0 and 1. So why the Groebner basis is
> [y^3 + y, x^2 + y^2 + 1, x*y] and not [x+y+1,x*y], which should be reduced
> to [x+y+1]. I tried to add a modulus but it does'nt seem to work. I am
> quite disappointed because all the interest of Groebner basis in
> cryptanalysis is that the degree of polynomes don't grow a lot due to the
> fact that x^2 + x =0.
>
> sage: Q.<x,y> = PolynomialRing(GF(2))
> sage: R2 = GF(2,name='x,y')
> sage: R2
> Finite Field of size 2
> sage: e=[x**2+y**2+1,x*y]
> sage: e
> [x^2 + y^2 + 1, x*y]
> sage: I=ideal(e)
> sage: I
> Ideal (x^2 + y^2 + 1, x*y) of Multivariate Polynomial Ring in x, y over
> Finite Field of size 2
> sage: B=I.groebner_basis(); B
> [y^3 + y, x^2 + y^2 + 1, x*y]
>
> So my question is : why SAGE doesn't take into account the fact that x^2 =
> x in GF(2) and how do force him to do it.
You are confusing the ring P = F_2[x,y] with the ring
Q = F_2[x,y]/<x^2 + x, y^2 + y>,
that is the polynomial ring over GF(2) with the Boolean polynomial ring. In
the former, x^2 is not reduced by x, but that happens in the latter. In sage
you should construct
B.<x,y> = BooleanPolynomialRing()
Cheers,
Martin
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://martinralbrecht.wordpress.com/
_jab: martinralbre...@jabber.ccc.de
--
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
