Can someone give a small example of how the XL algorithm is used to solve an overdetermined system, with numbers and variables along with the steps if possible as apposed to just a general case? This is so i can make more sense of it.

I would like to test the algorithm on a simple over determined system, but i don't know how to come up with such a system that has a unique solution.

I have a fairly good understanding of how steps of the algorithm work, extending the system, then linearizing the system in the hopes of obtaining a univariate polynomial which is then solved but whenever i come to to an example of this (i.e by hand) i seem to get stuck somewhere, how do i come up with a overdetermined system that has a unique solution set to test the algorithm on? I just feel like a small example with numbers and variables over a finite field would help me to see what's going on and understand the algorithm more.

  • $\begingroup$ To come up with such a system just choose $f_1,\ldots,f_m$ multivariate polynomials in $n$ variables with $n<m$, evaluate them at some point $\mathbf{a}$ to get $(c_1,\ldots,c_m)$, and then use the polynomials $(f_1-c_1,\ldots,f_m-c_m)$ $\endgroup$ – Daniel Mar 18 '18 at 1:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.