Speeding up Deciphering by Hypergraph Ordering

The “Gluing Algorithm” of Semaev [Des.\ Codes Cryptogr.\ 49 (2008), 47–60] — that finds all solutions of a sparse system of linear equations over the Galois field $GF(q)$ — has average running time $O(mq^{\max \left\vert \cup_{1}^{k}X_{j}\right\vert -k}), $where$m$ is the total number of equations, and ${\cup }_1^k{X}_j$ is the set of all unknowns actively occurring in the first $k$ equations. Our goal here is to minimize the exponent of $q$ in the case where every equation contains at most three unknowns. %Applying hypergraph-theoretic methods we prove The main result states that if the total number $\mid {\cup }_1^m{X}_j\mid$ of unknowns is equal to $m$, then the best achievable exponent is between $c_{1}m$ and $c_{2}m$ for some positive constants $c_1$ and $c_2\mathrm{.}$