Can someone give an example of how the XL algorithm is used to solve an overdetermined system as apposed to just a general case?

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