This paper builds a novel bridge between algebraic coding theory and mathematical knot theory, with applications in both directions. We give methods to construct error-correcting codes starting from the colorings of a knot, describing through a series of results how the properties of the knot translate into code parameters. We show that knots can be used to obtain error-correcting codes with prescribed parameters and an efficient decoding algorithm.

Abstract The extended coset leader weight enumerator of the generalized Reed–Solomon $$[q+1,q-3,5]_q$$ [ q + 1 , q - 3 , 5 ] q code is computed. In this computation methods in finite geometry, combinatorics and algebraic geometry are used. For this we need the classification of the points, lines and planes in the projective three space under projectivities that leave the twisted cubic invariant. A line in three space determines a rational function of degree at most three and vice versa. Furthermore, the double point scheme of a rational function is studied. The pencil of a true passant of the twisted cubic, not in an osculation plane gives a curve of genus one as double point scheme. With the Hasse–Weil bound on $${\mathbb F}_q$$ F q -rational points we show that there is a 3-plane containing the passant.

Quantum error-correcting codes play the role of suppressing noise and decoherence in quantum systems by introducing redundancy. Some strategies can be used to improve the parameters of these codes. For example, entanglement can provide a way for quantum error-correcting codes to achieve higher rates than the one obtained by means of the traditional stabilizer formalism. Such codes are called entanglement-assisted quantum error-correcting (EAQEC) codes. In this paper, we utilize algebraic geometry codes to construct several families of EAQEC codes derived from the Euclidean and the Hermitian construction. Three families constructed here consist of codes whose quantum Singleton defect is equal to zero, one, or two. We also construct families of EAQEC codes with an encoding rate exceeding the quantum Gilbert-Varshamov bound. Additionally, asymptotically good towers of linear complementary dual codes are used to obtain asymptotically good families of EAQEC codes consuming maximal entanglement. Furthermore, a simple comparison with the quantum Gilbert-Varshamov bound demonstrates that, by utilizing the proposed construction, it is possible to generate an asymptotically family of EAQEC codes that exceeds this bound.

Quantum error correcting codes play the role of suppressing noise and decoherence in quantum systems by introducing redundancy. Some strategies can be used to improve the parameters of these codes. For example, entanglement can provide a way for quantum error correcting codes to achieve higher rates than the one obtained via traditional stabilizer formalism. Such codes are called entanglement-assisted quantum (QUENTA) codes. In this paper, we use algebraic geometry codes to construct two families of QUENTA codes, where one of them has maximal entanglement and is maximal distance separable. In the end, we show that for any asymptotically good tower of algebraic function fields there is an asymptotically good family of maximal entanglement QUENTA codes with nonzero rate, relative minimal distance, and relative amount of entanglement.

Linear codes with complementary duals (LCD) are linear codes whose intersection with their dual are trivial. When they are binary, they play an important role in armoring implementations against side-channel attacks and fault injection attacks. Nonbinary LCD codes in characteristic 2 can be transformed into binary LCD codes by expansion. In this paper, we introduce a general construction of LCD codes from any linear codes. Further, we show that any linear code over Fq(q > 3) is equivalent to a Euclidean LCD code and any linear code over Fq2(q > 2) is equivalent to a Hermitian LCD code. Consequently an [n, k, d]-linear Euclidean LCD code over Fqwith q > 3 exists if there is an [n, k, d]-linear code over Fqand an [n, k, d]-linear Hermitian LCD code over Fq2with q > 2 exists if there is an [n, k, d]-linear code over Fq2. Hence, when q > 3 (resp. q > 2) q-ary Euclidean (resp. q2-ary Hermitian) LCD codes possess the same asymptotical bound as q-ary linear codes (resp. q2-ary linear codes). This gives a direct proof that every triple of parameters [n, k, d] which is attainable by linear codes over Fqwith q > 3 (resp. over Fq2with q > 2) is attainable by Euclidean LCD codes (resp. by Hermitian LCD codes). In particular there exist families of q-ary Euclidean LCD codes (q > 3) and q2-ary Hermitian LCD codes (q > 2) exceeding the asymptotical Gilbert-Varshamov bound. Further, we give a second proof of these results using the theory of Gröbner bases. Finally, we present a new approach of constructing LCD codes by extending linear codes.

We give polynomial time attacks on the McEliece public key cryptosystem-based either on algebraic geometry (AG) codes or on small co-dimensional subcodes of AG codes. These attacks consist in the blind reconstruction either of an error correcting pair (ECP), or an error correcting array (ECA) from the single data of an arbitrary generator matrix of a code. An ECP provides a decoding algorithm, that corrects up to ((d* - 1 - g)/2) errors, where d* denotes the designed distance and g denotes the genus of the corresponding curve, while with an ECA the decoding algorithm corrects up to ((d* - 1)/2) errors. Roughly speaking, for a public code of length n over Fq, these attacks run in O(n4log(n)) operations in Fqfor the reconstruction of an ECP and O(n5) operations for the reconstruction of an ECA. A probabilistic shortcut allows to reduce the complexities respectively to O(n3±ε log(n)) and O(n4±ε). Compared with the previous known attack due to Faure and Minder, our attack is efficient on codes from curves of arbitrary genus. Furthermore, we investigate how far these methods apply to subcodes of AG codes.

We give a polynomial time attack on the McEliece public key cryptosystem based on algebraic geometry codes. Roughly speaking, this attacks runs in O(n4) operations in Fq, where n denotes the code length. Compared to previous attacks, the present one allows to recover a decoding algorithm for the public key even for codes from high genus curves.

We propose a simple and efficient deterministic extractor for an ordinary elliptic curve E, defined over $$\mathbb{F}_{2^n}$$ , where n = 2ℓ and ℓ is a positive integer. Our extractor, for a given point P on E, outputs the first $${\mathbb{F}}_{2^\ell}$$ -coefficient of the abscissa of the point P. We also propose a deterministic extractor for the main subgroup G of E, where E has minimal 2-torsion. We show that if a point P is chosen uniformly at random in G, the bits extracted from the point P are indistinguishable from a uniformly random bit-string of length ℓ.

The q-ary Reed-Muller (RM) codes RM/sub q/(u,m) of length n=q/sup m/ are a generalization of Reed-Solomon (RS) codes, which use polynomials in m variables to encode messages through functional encoding. Using an idea of reducing the multivariate case to the univariate case, randomized list-decoding algorithms for RM codes were given in and . The algorithm in Sudan et al. (1999) is an improvement of the algorithm in , it is applicable to codes RM/sub q/(u,m) with u<q/2 and works for up to E

Improved geometric Goppa codes have a smaller redundancy and the same bound on the minimum distance as ordinary algebraic-geometry codes. For an asymptotically good sequence of function fields we give a formula for the redundancy.

The order bound on generalized Hamming weights is introduced in a general setting of codes on varieties which comprises both the one point geometric Goppa codes as well as the q-ary Reed-Muller codes. For the latter codes it is shown that this bound is sharp and that they satisfy the double chain condition.

This paper provides a survey of the existing literature on the decoding of algebraic-geometric codes. Definitions, theorems, and cross references will be given. We show what has been done, discuss what still has to be done, and pose some open problems.

The concept of an error-correcting array gives a new bound on the minimum distance of linear codes and a decoding algorithm which decodes up to half this bound. This gives a unified point of view which explains several improvements on the minimum distance of algebraic-geometric codes. Moreover, it is explained in terms of linear algebra and the theory of semigroups only.

Decoding geometric Goppa codes can be reduced to solving the key congruence of a received word in an affine ring. If the codelength is smaller than the number of rational points on the curve, then this method can correct up to 1.2 (d*-L)/2-s errors, where d* is the designed minimum distance of the code and s is the Clifford defect. The affine ring with respect to a place P is the set of all rational functions which have no poles except at P, and it is somehow similar to a polynomial ring. For a special kind of geometric Goppa code, namely C/sub Omega /(D,mP), the decoding algorithm is reduced to solving the key equation in the affine ring, which can be carried out by the subresultant sequence in the affine ring with complexity O(n/sup 3/), where n is the length of codewords.>

An infinite series of curves is constructed in order to show that all linear codes can be obtained from curves using Goppa's construction. If conditions are imposed on the degree of the divisor use, then criteria are derived for linear codes to be algebraic-geometric. In particular. the family of q-ary Hamming codes is investigated, and it is proven that only those with redundancy one or two and the binary (7,4,3) code are algebraic-geometric in this sense. For these codes. the authors explicitly give a curve, rational points, and a divisor. It is proven that this triple is in a certain sense unique in the case of the (7,4,3) code.>

A decoding algorithm for algebraic geometric codes that was given by A.N. Skorobogatov and S.G. Vladut (preprint, Inst. Problems of Information Transmission, 1988) is considered. The author gives a modified algorithm, with improved performance, which he obtains by applying the above algorithm a number of times in parallel. He proves the existence of the decoding algorithm on maximal curves by showing the existence of certain divisors. However, he has so far been unable to give an efficient procedure of finding these divisors.>