Solving systems of polynomial equations over binary fields: State-of-the-art algorithms and selected methods.

Abstract

The literature on the topic of methods for solving polynomial systems over F2 is extensively developed but lacks internal consistency: there are, for example, di erent choices of formulations of the underlying problem, the notion of complexity and of what assumptions about the input system are warranted. Therefore making comparisons between the di erent methods can be quite challenging, especially for the novice to the eld. In this thesis, an attempt to systemise the knowledge in the eld through a survey is made. The survey begins with discussions on, amongst other topics, di erent formulations of the problem, views on e ciency and reasonable assumptions and then moves on to comparisons between the di erent methods available. Hopefully these comparisons may serve as a guide for understanding what methods might be most relevant for any speci c use case and as a structurising contribution to the literature.