An Improved Algorithm for Code Equivalence
摘要
We study the linear code equivalence problem (LEP) for linear [n, k]-codes over finite fields \(\mathbb {F}_q\) . Recently, Chou, Persichetti and Santini gave an elegant algorithm that solves LEP over large finite fields (with \(q = \varOmega (n)\) ) in time \(2^{\frac{1}{2}\operatorname {H}\left( \frac{k}{n}\right) n}\) , where \(\operatorname {H}(\cdot )\) denotes the binary entropy function. However, for small finite fields, their algorithm can be significantly slower. In particular, for fields of constant size \(q = \mathcal {O}(1)\) , its runtime increases by an exponential factor in n. We present an improved version of their algorithm, which achieves the desired runtime of \(2^{\frac{1}{2}\operatorname {H}\left( \frac{k}{n}\right) n}\) for all finite fields of size \(q \ge 7\) . For a wide range of parameters, this improves over the runtime of all previously known algorithms by an exponential factor.