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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An Improved Algorithm for Code Equivalence

  • Julian Nowakowski

摘要

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.