Welcome to the resource topic for
**2024/1272**

**Title:**

An Improved Algorithm for Code Equivalence

**Authors:**
Julian Nowakowski

**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 heuristic algorithm that solves LEP over large finite fields (with q = \Omega(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 2^{\Theta(n)}.

We present an improved and provably correct 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 \geq 7. For a wide range of parameters, this improves over the runtime of all previously known algorithms by an exponential factor.

**ePrint:**
https://eprint.iacr.org/2024/1272

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .