Abstract Skew polynomials are a class of non-commutative polynomials that have several applications in computer science, coding theory and cryptography. In particular, skew polynomials can be used to construct and decode evaluation codes in several metrics, like e.g. the Hamming, rank, sum-rank and skew metric. We propose a fast divide-and-conquer variant of Kötter–Nielsen–Høholdt (KNH) interpolation algorithm: it inputs a list of linear functionals on skew polynomial vectors, and outputs a reduced Gröbner basis of their kernel intersection. We show, that the proposed KNH interpolation can be used to solve the interpolation step of interpolation-based decoding of interleaved Gabidulin codes in the rank-metric, linearized Reed–Solomon codes in the sum-rank metric and skew Reed–Solomon codes in the skew metric requiring at most $${\widetilde{O}}\left( s^\omega {\mathfrak {M}}(n)\right) $$ O ~ s ω M ( n ) operations in $${\mathbb {F}}_{q^m}$$ F q m , where n is the length of the code, $$s$$ s the interleaving order, $${\mathfrak {M}}(n)$$ M ( n ) the complexity for multiplying two skew polynomials of degree at most n, $$\omega $$ ω the matrix multiplication exponent and $${\widetilde{O}}\left( \cdot \right) $$ O ~ · the soft-O notation which neglects log factors. This matches the previous best speeds for these tasks, which were obtained by top–down minimal approximant bases techniques, and complements the theory of efficient interpolation over free skew polynomial modules by the bottom-up KNH approach. In contrast to the top–down approach the bottom-up KNH algorithm has no requirements on the interpolation points and thus does not require any pre-processing.

In this article, we present a new construction of evaluation codes in the Hamming metric, which we calltwisted Reed–Solomoncodes. Whereas Reed–Solomon (RS) codes are MDS codes, this need not be the case for twisted RS codes. Nonetheless, we show that our construction yields several families of MDS codes. Further, for a large subclass of (MDS) twisted RS codes, we show that the new codes are not generalized RS codes. To achieve this, we use properties of Schur squares of codes as well as an explicit description of the dual of a large subclass of our codes. We conclude the paper with a description of a decoder, that performs very well in practice as shown by extensive simulation results.

We present an efficient list decoding algorithm in the style of Guruswami-Sudan for algebraic geometry codes. Our decoder can decode any such code using$\tilde{\mathcal {O}} (s\ell ^{\omega }\mu ^{\omega -1}(n+g))$operations in the underlying finite field, where$n$is the code length,$g$is the genus of the function field used to construct the code,$s$is the multiplicity parameter,$\ell $is the designed list size and$\mu $is the smallest positive element in the Weierstrass semigroup at some chosen place; the “soft-O” notation$\tilde{\mathcal {O}} (\cdot)$is similar to the “big-O” notation$\mathcal {O}(\cdot)$, but ignores logarithmic factors. For the interpolation step, which constitutes the computational bottleneck of our approach, we use known algorithms for univariate polynomial matrices, while the root-finding step is solved using existing algorithms for root-finding over univariate power series.

We propose the first non-trivial generic decoding algorithm for codes in the sum-rank metric. The new method combines ideas of well-known generic decoders in the Hamming and rank metric. For the same code parameters and number of errors, the new generic decoder has a larger expected complexity than the known generic decoders for the Hamming metric and smaller than the known rank-metric decoders. Furthermore, we give a formal hardness reduction, providing evidence that generic sum-rank decoding is computationally hard. As a by-product of the above, we solve some fundamental coding problems in the sum-rank metric: we give an algorithm to compute the exact size of a sphere of a given sum-rank radius, and also give an upper bound as a closed formula; and we study erasure decoding with respect to two different notions of support.

Linearized Reed-Solomon (LRS) codes are sum-rank metric codes that fulfill the Singleton bound with equality. In the two extreme cases of the sum-rank metric, they coincide with Reed-Solomon codes (Hamming metric) and Gabidulin codes (rank metric). List decoding in these extreme cases is well-studied, and the two code classes behave very differently in terms of list size, but nothing is known for the general case. In this paper, we derive a lower bound on the list size for LRS codes, which is, for a large class of LRS codes, exponential directly above the Johnson radius. Furthermore, we show that some families of linearized Reed-Solomon codes with constant numbers of blocks cannot be list decoded beyond the unique decoding radius.

Power decoding is a partial decoding paradigm for arbitrary algebraic geometry codes for decoding beyond half the minimum distance, which usually returns the unique closest codeword, but in rare cases fails to return anything. The original version decodes roughly up to the Sudan radius, while an improved version decodes up to the Johnson radius, but has so far been described only for Reed-Solomon and one-point Hermitian codes. In this paper we show how the improved version can be applied to any algebraic geometry code.

We speed up existing decoding algorithms for three code classes in different metrics: interleaved Gabidulin codes in the rank metric, lifted interleaved Gabidulin codes in the subspace metric, and linearized Reed-Solomon codes in the sum-rank metric. The speed-ups are achieved by new algorithms that reduce the cores of the underlying computational problems of the decoders to one common tool: computing left and right approximant bases of matrices over skew polynomial rings. To accomplish this, we describe a skew-analogue of the existing PM-Basis algorithm for matrices over ordinary polynomials. This captures the bulk of the work in multiplication of skew polynomials, and the complexity benefit comes from existing algorithms performing this faster than in classical quadratic complexity. The new algorithms for the various decoding-related computational problems are interesting in their own and have further applications, in particular parts of decoders of several other codes and foundational problems related to the remainder-evaluation of skew polynomials.

We investigate algorithms for encoding of one-point algebraic geometry (AG) codes over certain plane curves called Cab curves, as well as algorithms for inverting the encoding map, which we call “unencoding”. Some Cab curves have many points or are even maximal, e.g. the Hermitian curve. Our encoding resp. unencoding algorithms have complexity Õ(n3/2) resp. Õ(qn) for AG codes over any Cabcurve satisfying very mild assumptions, where n is the code length and q the base field size, and Õ ignores constants and logarithmic factors in the estimate. For codes over curves whose evaluation points lie on a grid-like structure, for example the Hermitian curve and norm-trace curves, we show that our algorithms have quasi-linear time complexity Õ(n) for both operations. For infinite families of curves whose number of points is a constant factor away from the Hasse-Weil bound, our encoding and unencoding algorithms have complexities Õ(n5/4) and Õ(n3/2) respectively.

Interleaved Reed–Solomon codes admit efficient decoding algorithms which correct burst errors far beyond half the minimum distance in the random errors regime, e.g., by computing a common solution to the Key Equation for each Reed–Solomon code, as described by Schmidt et al. If this decoder does not succeed, it may eitherfailto return a codeword ormiscorrectto an incorrect codeword, and good upper bounds on the fraction of error matrices for which these events occur are known. The decoding algorithm immediately applies to interleaved alternant codes as well, i.e., the subfield subcodes of interleaved Reed–Solomon codes, but the fraction of decodable error matrices differs, since the error is now restricted to a subfield. In this paper, we present new general lower and upper bounds on the fraction of error matrices decodable by Schmidt et al.’s decoding algorithm, thereby making it the only decoding algorithm for interleaved alternant codes for which such bounds are known.

We propose the first non-trivial generic decoding algorithm for codes in the sum-rank metric. The new method combines ideas of well-known generic decoders in the Hamming and rank metric. For the same code parameters and number of errors, the new generic decoder has a larger expected complexity than the known generic decoders for the Hamming metric and smaller than the known rank-metric decoders.

Suppose K is a large enough field and P ⊂ K2 is a fixed, generic set of points which is available for precomputation. We introduce a technique called reshaping which allows us to design quasi-linear algorithms for both: computing the evaluations of an input polynomial f ∈ K [x, y] at all points of P and computing an interpolant f ∈ K[x, y] which takes prescribed values on P and satisfies an input y-degree bound. Our genericity assumption is explicit and we prove that it holds for most point sets over a large enough field. If P violates the assumption, our algorithms still work and the performance degrades smoothly according to a distance from being generic. To show that the reshaping technique may have an impact on other related problems, we apply it to modular composition: suppose generic polynomials M ∈ K[x] and A ∈ K[x] are available for precomputation, then given an input f ∈ K[x, y] we show how to compute f (x, A(x)) rem M(x) in quasi-linear time.

Interleaved Reed–Solomon codes admit efficient decoding algorithms which correct burst errors far beyond half the minimum distance in the random errors regime, e.g., by computing a common solution to the Key Equation for each Reed–Solomon code, as described by Schmidt et al. If this decoder does not succeed, it may either fail to return a codeword or miscorrect to an incorrect codeword, and good upper bounds on the fraction of error matrices for which these events occur are known. The decoding algorithm immediately applies to interleaved alternant codes as well, i.e., the subfield subcodes of interleaved Reed–Solomon codes, but the fraction of decodable error matrices differs, since the error is now restricted to a subfield. In this paper, we present new general lower and upper bounds on the fraction of decodable error matrices by Schmidt et al.’s decoding algorithm, thereby making it the only decoding algorithm for interleaved alternant codes for which such bounds are known.

We show that the root-finding step in interpolation-based decoding of interleaved Gabidulin codes can be solved by finding a so-called minimal approximant basis of a matrix over a linearized polynomial ring. Based on existing fast algorithms for computing such bases over ordinary polynomial rings, we develop fast algorithms for computing them over linearized polynomials. As a result, root finding costs O~(ℓωM(n)) operations in Fqm, where ℓ is the interleaving degree, n the code length, Fqm the base field of the code, 2 ≤ ω ≤ 3 the matrix multiplication exponent, and M(n) ∈ O(n1.635) is the complexity of multiplying two linearized polynomials of degree at most n. This is an asymptotic improvement upon the previously fastest algorithm of complexity O(ℓ3n2), in some cases O(ℓ2n2).

We present a generalisation of Twisted Reed-Solomon codes containing a new large class of MDS codes. We prove that the code class contains a large subfamily that is closed under duality. Furthermore, we study the Schur squares of the new codes and show that their dimension is often large. Using these structural properties, we single out a subfamily of the new codes which could be considered for code-based cryptography: These codes resist some existing structural attacks for Reed-Solomon-like codes, i.e. methods for retrieving the code parameters from an obfuscated generator matrix.

We consider the computation of two normal forms for matrices over the univariate polynomials: the Popov form and the Hermite form. For matrices which are square and nonsingular, deterministic algorithms with satisfactory cost bounds are known. Here, we present deterministic, fast algorithms for rectangular input matrices. The obtained cost bound for the Popov form matches the previous best known randomized algorithm, while the cost bound for the Hermite form improves on the previous best known ones by a factor which is at least the largest dimension of the input matrix.

We improve previously known lower bounds for the minimum distance of certain two-point AG codes constructed using a Generalized Giulietti-Korchmaros curve (GGK). Castellanos and Tizziotti recently described such bounds for two-point codes coming from the Giulietti-Korchmaros curve. Our results completely cover and in many cases improve on their results, using different techniques, while also supporting any GGK curve. Our method builds on the order bound for AG codes: to enable this, we study certain Weierstrass semigroups. This allows an efficient algorithm for computing our improved bounds. We find several new improvements upon the MinT minimum distance tables.

We present a new general construction of MDS codes over a finite field Fq. We describe two explicit subclasses which contain new MDS codes of length at least q/2 for all values of q ≥ 11. Moreover, we show that most of the new codes are not equivalent to a Reed-Solomon code.

We propose a new partial decoding algorithm for m-interleaved Reed-Solomon (IRS) codes that can decode, with high probability, a random error of relative weight 1 - Rm/m+1at all code rates R, in time polynomial in the code length n. For m > 2, this is an asymptotic improvement over the previous state-of-the-art for all rates, and the first improvement for R > 1/3 in the last 20 years. The method combines collaborative decoding of IRS codes with power decoding up to the Johnson radius.

Let F[∂ ; σ, δ] be a ring of Ore polynomials over a field. We give a new deterministic algorithm for computing the Popov form P of a non-singular matrix A ∈ F[∂ ; σ, δ]n x n. Our main focus is to ensure controlled growth in the size of coefficients from F in the case F = K(z), and even K = Q. Our algorithms are based on constructing from A a linear system over F and performing a structured fraction-free Gaussian elimination. The algorithm is output sensitive, with a cost that depends on the orthogonality defect of the input matrix: the sum of the row degrees in A minus the sum of the row degrees in P. The resulting bit-complexity for the differential and shift polynomial case over Q(z) improves upon the previous best.

We give an algorithm for computing all roots of polynomials over a univariate power series ring over an exact field K. More precisely, given a precision d, and a polynomial Q whose coefficients are power series in x, the algorithm computes a representation of all power series f(x) such that Q(f(x)) = 0 mod xd. The algorithm works unconditionally, in particular also with multiple roots, where Newton iteration fails. Our main motivation comes from coding theory where instances of this problem arise and multiple roots must be handled. The cost bound for our algorithm matches the worst-case input and output size d deg(Q), up to logarithmic factors. This improves upon previous algorithms which were quadratic in at least one of d and deg(Q). Our algorithm is a refinement of a divide & conquer algorithm by Alekhnovich (2005), where the cost of recursive steps is better controlled via the computation of a factor of $Q$ which has a smaller degree while preserving the roots.

We describe how to solve simultaneous Padé approximations over a power series ring K[[x]] for a field K using O~(nω - 1 d) operations in K, where d is the sought precision and $n$ is the number of power series to approximate. We develop two algorithms using different approaches. Both algorithms return a reduced sub-bases that generates the complete set of solutions to the input approximations problem that satisfy the given degree constraints. Our results are made possible by recent breakthroughs in fast computations of minimal approximant bases and Hermite Padé approximations.

We present the first two sub-quadratic complexity decoding algorithms for one-point Hermitian codes. The first is based on a fast realization of the Guruswami-Sudan algorithm using state-of-the-art algorithms from computer algebra for polynomial-ring matrix minimization. The second is a power decoding algorithm: an extension of classical key equation decoding which gives a probabilistic decoding algorithm up to the Sudan radius. We show how the resulting key equations can be solved by the matrix minimization algorithms from computer algebra, yielding similar asymptotic complexities.

We model the decoding of Interleaved Chinese Remainder codes as that of finding a short vector in a Z-lattice. Using the LLL algorithm, we obtain an efficient decoding algorithm, correcting errors beyond the unique decoding bound and having nearly linear complexity. The algorithm can fail with a probability dependent on the number of errors, and we give an upper bound for this. Simulation results indicate that the bound is close to the truth. We apply the proposed decoding algorithm for decoding a single CR code using the idea of “Power” decoding, suggested for Reed-Solomon codes. A combination of these two methods can be used to decode low-rate Interleaved Chinese Remainder codes.

We show how to solve a generalised version of the Multi-sequence Linear Feedback Shift-Register (MLFSR) problem using minimisation of free modules over F[x]. We show how two existing algorithms for minimising such modules run particularly fast on these instances. Furthermore, we show how one of them can be made even faster for our use. With our modelling of the problem, classical algebraic results tremendously simplify arguing about the algorithms. For the non-generalised MLFSR, these algorithms are as fast as what is currently known. We then use our generalised MLFSR to give a new fast decoding algorithm for Reed Solomon codes.

We derive the Wu list-decoding algorithm for generalized Reed-Solomon (GRS) codes by using Gröbner bases over modules and the Euclidean algorithm as the initial algorithm instead of the Berlekamp-Massey algorithm. We present a novel method for constructing the interpolation polynomial fast. We give a new application of the Wu list decoder by decoding irreducible binary Goppa codes up to the binary Johnson radius. Finally, we point out a connection between the governing equations of the Wu algorithm and the Guruswami-Sudan algorithm, immediately leading to equality in the decoding range and a duality in the choice of parameters needed for decoding, both in the case of GRS codes and in the case of Goppa codes.