Harald, thank you for reminding us of this post.
Raphael,
Actually I started an answer a while ago, but thought it wouldn't be
helpful and therefore didn't post it.
On 27 Jul., 19:01, lesshaste <drr...@gmail.com> 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();
This is of course a good starting point.
There is the "solve" command, but as much as I know,
- this can only work with symbolic expressions (hence, one must
transform the polynomials into symbolic expressions),
- it ignores that you work over GF(2), which is worse.
So, probably the following is not a solution for your problem:
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: B= I.groebner_basis()
sage: B
[a111*a122*b111*b212*c112 + a121*a122*b211*b212*c112 + a111*b111,
a122*b112*b211*c112 + a122*b111*b212*c112 + b111, a112*a121*b212*c112
+ a111*a122*b212*c112 + a111, a111*b111*c111 + a122*b212*c112,
a121*b111*c111 + a122*b112*c112, a111*b211*c111 + a112*b212*c112,
a121*b211*c111 + a122*b212*c112 + 1, a112*b112*c112 + a122*b212*c112 +
1, a112*b111 + a122*b211, a111*b112 + a121*b212]
sage: X = var(','.join(R.variable_names()))
sage: solve([symbolic_expression(t)==0 for t in B],X)
[[a111 == 0, a112 == -1/(r1*r4), a121 == -1/(r2*r3), a122 == 0, b111
== 0, b112 == r1, b211 == r2, b212 == 0, c111 == r3, c112 == r4],
[a111 == 1/(r5*r7), a112 == 0, a121 == 0, a122 == -1/(r6*r8), b111 ==
r5, b112 == 0, b211 == 0, b212 == r6, c111 == r7, c112 == r8]]
> 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, I don't know.
> Also, I read back in April that there was a plan to implement
> Faugere's F4 algorithm. 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?)
Do you mean F5?
I was involved in the F5 toy implementation. But it really isn't more
than a toy, that might be useful for teaching. For example, one can
demonstrate that there are really only few reductions to zero in the
F5 algorithm.
But certainly the non-F5 algorithms in Singular are **much** (I mean
***MUCH***) better than our toy-F5.
If I understand correctly, not only your coefficients are in GF(2),
but the variables are in GF(2) as well, hence, you have in fact the
equation x==x^2 for any variable x, right?
Then you could start with
sage:
RB.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112>=BooleanPolynomialRing
()
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)*RB
sage: B= I.groebner_basis()
sage: B
[a111 + b212, a112 + b211, a121 + b112, a122 + b111, b111*b112 + b111
+ b112 + 1, b111*b211 + b111 + b211 + 1, b111*b212 + b112*b211 + 1,
b112*b212 + b112 + b212 + 1, b211*b212 + b211 + b212 + 1, c111 + 1,
c112 + 1]
As far as I know, this uses PolyBoRi in the background, which is
specialised for Groebner basis computations over GF(2) with the
relations x^2==x. And I think this could deal with pretty big
examples.
But again, I don't know how to actually find a solution.
Best regards,
Simon
--~--~---------~--~----~------------~-------~--~----~
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
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
