Speeding up deciphering by hypergraph ordering
The  Gluing Algorithm of Semaev (Des. Codes Cryptogr. 49:4760, 2008)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| \cup _{1}^{k}X_{j}\right| -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. In order to make the implementation of the algorithm faster, our goal here is to minimize the exponent of \(q\) in the case where every equation contains at most three unknowns. The main result states that if the total number \(\left| \cup _{1}^{m}X_{j}\right| \) 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}.\)
hypergraph ordering sparse systems of boolean equations 94a60 (05c65 68q25)