Does anyone know how to implement a simple XL Algorithm in sage?

savecancel

Is this relevant:

http://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/multi_polynomial_sequence.html

Here, there is a line...

Using these building blocks we can implement a simple XL algorithm easily:

I have had a look at that but i don't really understand what is going on there because it doesn't seem to provide a solution, also i need to do it for a polynomial system. They define a polynomial system with the following

sr = mq.SR(1,1,1,4, gf2=True, polybori=True, order='lex')

F,s = sr.polynomial_system()and i don't really get what kind of polynomial system has actually been implemented there :/

The structure in encapsulated. To see the $36$ polynomials in F:

for pol in F: print pol

There are 20 variables in F.variables(). So there are $\binom{20}2=190$ monomials $ab$, where $a,b$ are variables, $a\ne b$.

Then we build F2 = Sequence(map(mul, cartesian_product_iterator((monomials, F)))). The cartesian product of all monomials $ab$ and all pols $f$ has then $190\cdot 36$ elements, we map them via mul getting all$ab\;f$ of this shape.

The tricky F2.coefficient_matrix(sparse=False) isolates the corresponding matrix, try F2.coefficient_matrix? to see in examples how this works.

From here, standard linear algebra gets the hands on it...

This example may not be related to the own problem, but then we have to know this other problem / situation.