On Monday 27 July 2009, lesshaste wrote: > I am new to sage and am attempting to solve systems of multivariate > polys over GF(2). My first attempt with a small example is > > R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112>=GF(2)[] > I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 * c111 + > a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112 , > a121 * b211 * c111 + a122 * b212 * c112 - 1)*R > B= I.groebner_basis(); > > That works fine but how do I now solve B in sage to actually an > answer? In my case I only need one answer rather than the full list > of possible solutions.
Sorry, for the late reply, I am on vacation this week: If you are looking for solutions in GF(2) you should use the boolean polynomial ring. Also, your original system of equations has dimension 6, i.e. it does not have a finite set of solutions. You should definitely add the field polynomials (x_i^2 + x_i) to gain a system which is zero dimensional (the BooleanPolynomialRing does this implicitly btw.) Finally, for solving you should use a lexicographical term ordering: sage: R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112> = BooleanPolynomialRing(order='lex') sage: I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 * c111 + ....: a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112 , ....: a121 * b211 * c111 + a122 * b212 * c112 - 1)*R sage: I.groebner_basis() [a111 + b212, a112 + b211, a121 + b112, a122 + b111, c111 + 1, c112 + 1] Then, the Gröbner basis has a triangular shape and allows you to read the solution. The introduction of my Diplomarbeit describes this in more detail: http://bit.ly/B4zdT http://sage.math.washington.edu/home/malb/thesis-1.0.pdf (sorry for the self reference) Alternatively, you can use the variety() function -- a variety is a solution set to a set of polynomial equations -- which only works polynomial rings right now: sage: R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112>=GF(2)[] sage: I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 * c111 + ....: a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112 , ....: a121 * b211 * c111 + a122 * b212 * c112 - 1)*R sage: J = I + sage.rings.ideal.FieldIdeal(R) sage: J.variety() [{a112: 0, a111: 0, a122: 0, a121: 0, b211: 0, c111: 1, b212: 0, b112: 0, c112: 1, b111: 0}, {a112: 0, a111: 0, a122: 1, a121: 0, b211: 0, c111: 1, b212: 0, b112: 0, c112: 1, b111: 1}, {a112: 0, a111: 0, a122: 0, a121: 1, b211: 0, c111: 1, b212: 0, b112: 1, c112: 1, b111: 0}, {a112: 0, a111: 0, a122: 1, a121: 1, b211: 0, c111: 1, b212: 0, b112: 1, c112: 1, b111: 1}, {a112: 1, a111: 0, a122: 0, a121: 0,b211: 1, c111: 1, b212: 0, b112: 0, c112: 1, b111: 0}, {a112: 1, a111: 0, a122: 1, a121: 0, b211: 1, c111: 1, b212: 0, b112: 0, c112: 1, b111: 1}, {a112: 1, a111: 0, a122: 0, a121: 1, b211: 1, c111: 1, b212: 0, b112: 1, c112: 1, b111: 0}, {a112: 1, a111: 0, a122: 1, a121: 1, b211: 1, c111: 1, b212: 0, b112: 1, c112: 1, b111: 1}, {a112: 0, a111: 1, a122: 0, a121: 0, b211: 0, c111: 1, b212: 1, b112: 0, c112: 1, b111: 0}, {a112: 0, a111: 1, a122: 1, a121: 0, b211: 0, c111: 1, b212: 1, b112: 0, c112: 1, b111: 1}, {a112: 0, a111: 1, a122: 0, a121: 1, b211: 0, c111: 1, b212: 1, b112: 1, c112: 1, b111: 0}, {a112: 0, a111: 1, a122: 1, a121: 1, b211: 0, c111: 1, b212: 1, b112: 1, c112: 1, b111: 1}, {a112: 1, a111: 1, a122: 0, a121: 0, b211: 1, c111: 1, b212: 1, b112: 0, c112: 1, b111: 0}, {a112: 1, a111: 1, a122: 1, a121: 0, b211: 1, c111: 1, b212: 1, b112: 0, c112: 1, b111: 1}, {a112: 1, a111: 1, a122: 0, a121: 1, b211: 1, c111: 1, b212: 1, b112: 1, c112: 1, b111: 0}, {a112: 1, a111: 1, a122: 1, a121: 1, b211: 1, c111: 1, b212: 1, b112: 1, c112: 1, b111: 1}] > Also, I read back in April that there was a plan to implement > Faugere's F4 algorithm. There have been numerous attempts to implement F4 efficiently in the open- source world but non of them succeeded to satisfaction. However, PolyBoRi's SlimGB algorithm is heavily inspired by F4 and you can even use linear algebra. PolyBoRi is used behind the scene when you construct a BooleanPolynomialRing. > As the systems I want to solve are very large, > I would be particularly interested in that or any related tools that > are in development. (Anyone working on an XL variant?) Btw. XL is a redundant version of F4 and I have little faith in its performance. Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF _www: http://www.informatik.uni-bremen.de/~malb _jab: [email protected] --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] 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 -~----------~----~----~----~------~----~------~--~---
