On Thursday 03 February 2011, Francois Maltey wrote: > Thomas Gueuning wrote : > > 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. > > You also can type : > > sage: RR.<x,y> = GF(2)[] # it means that variables are x and y. > > You may add ideal generators : y^2-y and x^2-x. > In the polynomial space x^2 != x : degree aren't the same. > But in the quotient you have x^2=x as you expect if x==0 or x==1. > > Then the Groebner basis is almost what you want : > > sage: ideal([x**2+y**2+1,x*y,x^2-x,y^2-y]).groebner_basis() > [y^2 + y, x + y + 1] > > The second polynom is x+y+1 and you may forgot y^2+y. > > I don't know how you can proof that you get exactly the right result. > Order over degree changes the Groebner basis... > > > F. who maybe makes a mistake...
Hi, perhaps a look at the introduction of http://www.sagemath.org/doc/reference/sage/rings/polynomial/pbori.html will help to clarify things a bit (also in terms of what you use in Sage) Let P = F[x_1,...,x_n]. Essentially, there is a one-to-one correspondence between ideals I in P/Q and J = I + Q if Q is an ideal in P. Since the OP mentions cryptanalysis I assume he wants to solve systems of equations over the base field GF(2). In this case, the quotient P/<x_1^2 - x_1,...x_n^2-x_n> is precisely the right one to use since x_i^2 - x_i has the roots 0, 1 and no root in the extension. Thus, the only possible solutions to the common system have components in GF(2). More details for example in my thesis (Section 3.6): http://martinralbrecht.files.wordpress.com/2010/10/phd.pdf 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
