I know the answer to (2): the exporession you get from x*y is a polynomial in the xi which can be expressed as 1-prod(xi-1) which is 1 if not all the xi are nonzero (i.e. if x is nonzero) and 0 if all xi are zero (i.e. if x=0). Which is exactly right, when you think about it.
To force x to represent an arbitray nonzero element of the field (as opposed to just an arbitrary element) you could add the element expr-1 to the generators of the ideal used to define S, where expr is the above expression. John 2008/5/30 vpv <[EMAIL PROTECTED]>: > > Thanks a lot for the code and the detailed explanations, John! I got > the code running, and it computes the y-s which I need. > > About (1) and (2): > >> (1) the expression for y output is a polynomial in the xi with >> coefficients pollys in z, while I expect you hoped that would be the >> other way round; > > Yes. Indeed I need the polynomial coefficients to be expressions of xi- > s. Maybe I can try to fix this with some symbolic manipulations. As to > (2): > >> (2) The expression x*y does not simplify to 1, but it does satisfy >> (x*y)^2==x*y. >> > > I wonder if this means that the expression I get for y is not in fact > the multiplicative inverse of x mod the polynomial? > > Thank you very much for your time and help! > > I On May 29, 5:44 pm, "John Cremona" <[EMAIL PROTECTED]> wrote: >> Here is what I was talking about in my first reply. It does not do >> exactly what you want, in two ways: >> (1) the expression for y output is a polynomial in the xi with >> coefficients pollys in z, while I expect you hoped that would be the >> other way round; >> (2) The expression x*y does not simplify to 1, but it does satisfy >> (x*y)^2==x*y. >> >> If someone else can suggest how to deal with (2) this might make a >> nice worked examples for the documentation. >> >> John >> >> # Define the field with 2 elements and the polynomial ring over it >> # with variable Z >> >> F2=GF(2) >> R.<Z>=PolynomialRing(F2) >> >> # Define the polynomial f and check that it is irreducible: >> >> f=Z^8+Z^4+Z^3+Z+1 >> assert f.is_irreducible() >> >> # Define the field GF(2^8) with generator z satisfying f as its >> # minimal polynomial: >> >> F256.<z>=GF(256,'z',f) >> >> # Define a polynomial ring in 8 variables over F2 >> >> S=PolynomialRing(F256,8,'x') >> >> # Quotient out by the ideal containing xi^2-xi for all 8 generators. >> # The variables in the quotient are called x0,x1,...,x7 >> >> I=S.ideal([xi^2-xi for xi in S.gens()]) >> Sbar.<x0,x1,x2,x3,x4,x5,x6,x7>=S.quo(I) >> >> # Define the "generic" element x: >> >> x = x0+x1*z^1+x2*z^2+x3*z^3+x4*z^4+x5*z^5+x6*z^6+x7*z^7 >> >> # If all is well this should be true: >> >> assert x^256 == x >> >> # >> >> y = x^254 >> >> # ideally, we should have x*y = x^255 = 1, but unfortunately not: >> >> assert not x*y==1 >> assert not x^255==1 >> >> # However >> >> one = x*y >> assert one^2==one >> >> 2008/5/28 vpv <[EMAIL PROTECTED]>: >> >> >> >> > Hello, >> >> > I am trying to solve the following equation for y in SAGE: >> >> > x*y = 1 (mod z^8+z^4+z^3+z+1) >> >> > where >> >> > x = x0+x1*z^1+x2*z^2+x3*z^3+x4*z^4+x5*z^5+x6*z^6+x7*z^7 >> > y = ? >> >> > x0,...,x7 are elements of GF(2). I do not know their values. I am >> > searching for y in parametric form i.e. as a polynomial of z of degree >> > 7 with coefficients - some functions of x0,...,x7. >> >> > I define in SAGE: >> >> > P.<x0,x1,x2,x3,x4,x5,x6,x7> = BooleanPolynomialRing(8, order='lex') >> > Z.<z> = PolynomialRing(P) >> >> > I try to do the following in SAGE >> >> > y = inverse_mod(x0+x1*z^1+x2*z^2+x3*z^3+x4*z^4+x5*z^5+x6*z^6+x7*z^7, >> > z^8+z^4+z^3+z+1) >> >> > but it does not work. >> >> > Alternatively, I try to define a ring of univariate polynomials of z >> > with coeffients in P, every element of which is reduced (mod >> > z^8+z^4+z^3+z+1), but I am not able to get the right syntax to do this >> > in SAGE. >> >> > Any help is appreciated. >> >> > Thanks! > > > > --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
