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

asked 2018-03-29 07:45:45 -0600

Dalvir gravatar image

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?

edit retag flag offensive close merge delete

Comments

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:

dan_fulea gravatar imagedan_fulea ( 2018-03-29 08:07:57 -0600 )edit

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 :/

Dalvir gravatar imageDalvir ( 2018-03-29 08:40:59 -0600 )edit

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.

dan_fulea gravatar imagedan_fulea ( 2018-03-29 20:56:50 -0600 )edit