2013/09/20 by Peter Horák, Peter Horak, Horak, Peter +3
Computer Science · Mathematics · #68Q25) #94A60 (05C65 #Coding theory and cryptography #Combinatorics (math.CO) #Cryptography and Residue Arithmetic #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Polynomial and algebraic computation #cs.CR #math.CO #msc:94A60
paper · pdf · doi:10.48550/arxiv.1309.5292
arxiv created 2013/09/20 · openalex publication_date 2013/09/20 · arxiv updated 2013/09/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \vert ∪1kXj\vert -k), where m is the total number of equations, and ∪1kXj 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 \vert ∪1mXj\vert of unknowns is equal to m, then the best achievable exponent is between c1m and c2m for some positive constants c1 and c2.