could anyone give me a small example with actual numbers and variables over a finite field of how the XL algorithm is used to solve overdetermined systems? And the steps involved. I understand the algorithm but a simple example would make my life a lot easier. Also are there any implementations of the XL algorithm available?


  • 2
    $\begingroup$ If you understand the algorithm, one option is to use the magma online calculator [which works at high level] and try it out yourself. $\endgroup$ – kodlu Mar 8 '18 at 20:50
  • $\begingroup$ @kodlu What is the magma online calculator? $\endgroup$ – Daniel Mar 10 '18 at 11:46
  • $\begingroup$ Have a look at magma.maths.usyd.edu.au/calc $\endgroup$ – kodlu Mar 10 '18 at 13:33

I recommend to read book "Algebraic Cryptanalysis Book by Gregory Bard". it has a simple example of XL algorithm chapter 12 page 213 (12.4 The XL Algorithm).

after that you can develop sage/magma code for capturing the concept very well.

| improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.