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

I need to implement the XL algorithm in sage, which i can use to solve over-determined systems of polynomial equations (more equations than variables). Any help on how to do this?

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`

: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`pol`

s $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.