We present several new provable algorithms for two variants of the code equivalence problem on linear error-correcting codes, the Linear Code Equivalence Problem (LCE) and the Permutation Code Equivalence Problem (PCE). Specifically, for arbitrary codes of block lengthnand dimensionkover any finite field Fq, we show: 1) A deterministic algorithm running in 2n+o(n+q)time for LCE. 2) A randomized algorithm running in 2n/2+o(n+q)time for LCE and PCE. 3) A quantum algorithm running in 2n/3+o(n+q)time for LCE and PCE. The second two algorithms improve on recent work of Nowakowski (PQCrypto 2025), which gave algorithms with similar running times but only for code equivalence onrandomcodes and only over fields of orderq≥ 7.

We present several new provable algorithms for two variants of the code equivalence problem on linear error-correcting codes, the Linear Code Equivalence Problem (LCE) and the Permutation Code Equivalence Problem (PCE). Specifically, for arbitrary codes of block length$n$and dimension$k$over any finite field$\mathbb{F}_{q}$, we show: 1)A deterministic algorithm running in$2^{n+o(n+q)}$time for LCE. 2)A randomized algorithm running in$2^{n / 2+o(n+q)}$time for LCE and PCE. 3)A quantum algorithm running in$2^{n / 3+o(n+q)}$time for LCE and PCE. The second two algorithms improve on recent work of Nowakowski (PQCrypto 2025), which gave algorithms with similar running times but only for code equivalence on random codes and only over fields of order$q \geq 7$.

In this paper, we describe an efficient search-to-decision reduction for the permutation code equivalence problem. Given two linear codes ${\mathcal{C}_1}$, ${\mathcal{C}_2}$ of length n and dimension k over ${\mathbb{F}_q}$, we describe an algorithm that finds $\pi \in {\mathcal{S}_n}$ such that $\pi \left( {{\mathcal{C}_1}} \right) = {\mathcal{C}_2}$ by using a polynomial number of queries to an oracle that decides whether two codes are permutation-equivalent.

Abstract In this survey, the authors review the main quantum algorithms for solving the computational problems that serve as hardness assumptions for cryptosystem. To this end, the authors consider both the currently most widely used classically secure cryptosystems, and the most promising candidates for post‐quantum secure cryptosystems. The authors provide details on the cost of the quantum algorithms presented in this survey. The authors furthermore discuss ongoing research directions that can impact quantum cryptanalysis in the future.

This paper gives polynomial time quantum algorithms for computing the ideal class group (CGP) under the Generalized Riemann Hypothesis and solving the principal ideal problem (PIP) in number fields of arbitrary degree. These are are fundamental problems in number theory and they are connected to many unproven conjectures in both analytic and algebraic number theory. Previously the best known algorithms by Hallgren [20] only allowed to solve these problems in quantum polynomial time for number fields of constant degree. In a recent breakthrough, Eisenträger et al. [11] showed how to compute the unit group in arbitrary fields, thus opening the way to the resolution of CGP and PIP in the general case. For example, Biasse and Song [3] pointed out how to directly apply this result to solve PIP in classes of cyclotomic fields of arbitrary degree. The methods we introduce in this paper run in quantum polynomial time in arbitrary classes of number fields. They can be applied to solve other problems in computational number theory as well including computing the ray class group and solving relative norm equations. They are also useful for ongoing cryptanalysis of cryptographic schemes based on ideal lattices [5, 10]. Our algorithms generalize the quantum algorithm for computing the (ordinary) unit group [11]. We first show that CGP and PIP reduce naturally to the computation of S-unit groups, which is another fundamental problem in number theory. Then we show an efficient quantum reduction from computing S-units to the continuous hidden subgroup problem introduced in [11]. This step is our main technical contribution, which involves careful analysis of the metrical properties of lattices to prove the correctness of the reduction. In addition, we show how to convert the output into an exact compact representation, which is convenient for further algebraic manipulations.

We present an algorithm for list decoding codewords of algebraic number field codes in polynomial time. This is the first explicit procedure for decoding number field codes whose construction were previously described by Lenstra [1] and Guruswami [2]. We rely on a new algorithm for computing the Hermite normal form of the basis of an OK-module due to Biasse and Fieker [3] where OKis the ring of integers of a number field K.

We present a variation of the modular algorithm for computing the Hermite Normal Form of an OK-module presented by Cohen [4], where OK is the ring of integers of a number field K. An approach presented in [4] based on reductions modulo ideals was conjectured to run in polynomial time by Cohen, but so far, no such proof was available in the literature. In this paper, we present a modification of the approach of [4] to prevent the coefficient swell and we rigorously assess its complexity with respect to the size of the input and the invariants of the field K.