Paper 2024/1272

An Improved Algorithm for Code Equivalence

Abstract

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=\mathrm{\Omega }(n)$) in time $2^{\frac{1}{2}\mathrm{H}\left(\frac{k}{n}\right)n}$, where $\mathrm{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}\mathrm{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.