Project topics and materials
Get Complete Project Material File(s) Now! »
Shortest Vectors in Polynomial Lattices Over Galois Rings and Application to List Decoding
This chapter contains the most recent results I obtained. It has not been submitted. It concerns the interpolation step of the Guruswami-Sudan algorithm and is included here for the completeness of this part of the PhD thesis.
Introduction
In this chapter we adapt the algorithm of [Ale05], which works over nite elds, over discrete valuation rings. Given a nite eld Fq and a lattice in Fq[X]n, the algorithm in [Ale05] gives in polynomial time the shortest vector of . The \norm » used here is the degree of the polynomial of greatest degree among all the components of a vector of . It is interesting to note that the nding of the shortest vector of a lattice in Fq[X]m can be done in polynomial time whereas, a priori, no polynomial time algorithm is known to nd the shortest vector of a lattice in Zm.
We follow the presentation given in Alekhnovich’s paper [Ale05]. We rst recall the de nition and properties of discrete valuation rings. Then we give a naive algorithm which computes the shortest vector of a lattice (A=( r))n where A is a DVR with uniformizing parameter . Finally we apply this algorithm to the Sudan list decoding algorithm for Reed-Solomon codes over A=( r).
Related work
Given a lattice in 0 Rm it is NP-hard [Ajt98] to nd a shortest vector. However in the early 1980s a polynomial time algorithm for nding a short vector in 0 was given in [LLL82]. The situation for polynomial lattices is much simpler. Let [X]m be a polynomial lattice over the eld . One can compute a shortest vector of in polynomial time [MS03]. In [Ale05] the author applies a shortest vector nding algorithm to the Guruswami-Sudan problem. Related work of shortest vector in polynomial lattices includes [GJV03, JV05, SV05, JV06].
Prerequisites
Complexity model
The \soft-Oh » notation f(n) 2 ~ O(1) (3 + g(n)). It
O(g(n)) means that f(n) 2 g(n) log
is well known [Fur07]
that the time needed to multiply two integers of bit-size at most
n in binary representation is O(n). The cost of multiplying two polynomials of degree
at most n over a ring A is O(n) in terms of the number of arithmetic operations in A.
Thus the bit-cost of multiplying two elements of the nite eld Fpn is O(n log p).
Discrete valuation rings
De nition 51. A discrete valuation ring (DVR) is a principal ideal domain which has one and only one prime ideal m. Any element 2 A such that ( ) = m is called a uniformizing parameter of A. Let a 2 A be a nonzero element. The greatest integer i 2 N such that a 2 mi n mi+1 is called the valuation of a and denoted by v(a). We let v(0) = +1.
De nition 52. Let Zps be an unrami ed extension of Zp of degree s. Then Zps is a DVR with uniformizing parameter p [Ser62, Chapter 1]. Let r be a positive integer. Then the quotient ring
GR(pr; s) := Zps (pr)
is called a Galois ring.
Proposition 53. Let a; b 2 GR(pr; s). Then the product ab 2 GR(pr; s) can be computed with a number of O (s log s log log sr log p log(r log p) log log(r log p))
or O(rs log p) bit-operations.
Proposition 54. Let Fq[[t]] be the power series ring over Fq. It is a DVR with uni-formizing parameter t. Let a; b 2 Fq[[t]]=(tr). Then the product ab 2 Fq[[t]]=(tr) can be computed with a number of O(r log r log log r) or O(r) arithmetic operations in Fq.
Proof. Proposition 52 and 53 are in [GG03, Chapter 8].
Reed-Solomon codes over valuation rings
Let A be a DVR. Reed-Solomon codes over rings are de ned in a slightly di erent way than their eld counterparts. We let A[X]<k denote the submodule of A[X] consisting of all the polynomials of degree at most k 1 of A[X].
De nition 55. Let x1; : : : ; xn be elements of A such that xi xj 2 A 6 r i = j
(where A is the group of units of A). The submodule of An generated by the vectors (f(x1); : : : ; f(xn)) 2 A n where f 2 A[X]<k is called a Reed-Solomon code over A. The n-tuple (x1; : : : ; xn) is called the support of the RS code.
Proposition 56. Let C be a RS code over A. Then C has parameters [n; k; d = n k+1]A.
Proposition 57. Let C be a RS code with parameters [n; k; d = n k + 1]A over a discrete valuation ring A with uniformizing parameter . Then C= rC is a RS code with parameters [n; k; d]A=( r) over A=( r). Moreover of (x1; : : : ; xn) is the support of C then (x1 mod r; : : : ; xn mod r) is the support of C= rC.
Table of contents :
Introduction
I The Classical List Decoding Framework for Finite Rings
1 Shortest Vectors in Polynomial Lattices Over Galois Rings and Application to List Decoding
1.1 Introduction
1.1.1 Related work
1.2 Prerequisites
1.2.1 Complexity model
1.2.2 Discrete valuation rings
1.2.3 Reed-Solomon codes over valuation rings
1.3 Computing the shortest vector
1.3.1 Preliminaries
1.3.2 The naive algorithm
1.4 Application to list decoding of Reed-Solomon codes
1.4.1 Preliminaries
1.4.2 Application to the Sudan algorithm
1.5 Conclusion
2 Polynomial root nding over local rings and application to error correcting codes
2.1 Introduction
2.1.1 Application to list decoding
2.1.2 Complexity model
2.1.3 Our contributions
2.1.4 Related works
2.2 Algorithm with linear convergence
2.2.1 Local multiplicities
2.2.2 Representation of the set of roots
2.2.3 Naive local solver
2.2.4 Cumulative cost of steps 1
2.2.5 Cumulative cost of steps 2
2.2.6 Cumulative cost of steps 3
2.2.7 Cumulative cost of steps 4
2.2.8 Total cost of Algorithm 9
2.3 Faster algorithm with splitting
2.3.1 Quasi-homogeneous Hensel lifting
2.3.2 Quasi-homogeneous multifactor Hensel lifting
2.3.3 Local solver with splitting
2.3.4 Total cost of Algorithm 13
2.3.5 Implementation and timings
2.3.6 Cost analysis in higher dimension
2.4 Application to error correcting codes
2.4.1 Algorithm
2.4.2 Experiments
II A Lifting Framework for List Decoding over some Finite Rings
3 On Generalized Reed-Solomon Codes Over Commutative and Non-commutative Rings
3.1 Introduction
3.1.1 Our contributions
3.1.2 Related work
3.2 Prerequisites
3.2.1 Error correcting codes
3.2.2 Galois rings
3.2.3 Complexity model
3.3 Generalized Reed-Solomon codes
3.4 Unique decoding of generalized Reed-Solomon codes
3.4.1 Unique decoding over certain valuation rings
3.4.2 The Welch-Berlekamp algorithm
3.5 List decoding of generalized Reed-Solomon codes
3.5.1 List-decoding over certain valuation rings
3.5.2 The Guruswami-Sudan algorithm
3.5.3 Complexities for list decoding algorithms
3.6 Conclusion
4 A Lifting Decoding Scheme and its Application to Interleaved Linear Codes
4.1 Introduction
4.1.1 Our contributions
4.1.2 Related work
4.2 Prerequisites
4.2.1 Complexity model
4.2.2 Error correcting codes
4.2.3 Reed-Solomon codes over rings
4.3 Improved -adic lifting
4.4 Application to interleaved linear codes
4.5 Conclusion
III Related work on error correcting codes
5 On Quasi-Cyclic Codes as a Generalization of Cyclic Codes
5.1 Introduction
5.1.1 Context
5.1.2 First denitions
5.2 Properties of quasi-cyclic codes
5.2.1 The one-to-one correspondence
5.2.2 The generator polynomial of an `-quasi-cyclic code
5.2.3 A property of generator polynomials
5.3 Quasi-BCH
5.3.1 Denition
5.4 Decoding scheme for quasi-BCH codes
5.4.1 The key equation
5.5 Evaluation codes
5.5.1 Denition and parameters
5.5.2 New good codes
5.6 Conclusion
6 An algorithm for list decoding number eld codes
6.1 Introduction
6.2 Generalities on number elds
6.3 Decoding with Coppersmith’s theorem
6.4 Johnson-type bound for number elds codes
6.5 General description of the algorithm
6.6 Existence of the decoding polynomial
6.7 Computation of the decoding polynomial
6.8 Good weight settings
6.9 Conclusion
IV Implementation
7 Implementation within Mathemagix
7.1 Introduction
7.2 Overview of the C++ side of Mathemagix
7.2.1 The directory tree of Mathemagix
7.2.2 C++ classes and variants
7.3 The mgf2x package
7.4 The finitefieldz package
7.4.1 Prime elds
7.4.2 Extensions of nite elds
7.4.3 Variants available for ffe
7.4.4 Finite elds of characteristic 2
7.5 The quintix package
7.5.1 Prime Galois rings
7.5.2 Extensions of Galois rings
7.5.3 Galois rings of characteristic 2r
7.5.4 Implementation of univariate root nding over Galois rings
8 The decoding Library for List Decoding
8.1 Overview of decoding
8.1.1 Introduction and motivation
8.1.2 The implementation
8.1.3 Presentation
8.2 More details on decoding
8.2.1 The directory tree of decoding
8.2.2 The internals of the library
8.2.3 Customization of the library
8.2.4 Rings provided by default with the library
8.2.5 Implemented algorithms
8.2.6 Timings
Bibliography
