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 .