Improved Algorithms for Solving Polynomial Systems over GF(2) by Multiple Parity-Counting

Itai Dinur

We consider the problem of finding a solution to a multivariate polynomial equation system of degree $d$ in $n$ variables over ${\mathbb{F}}_2$. For $d=2$, the best-known algorithm f…