Skew and Linearized Polynomials

Open Source 2 Minutes

Gabidulin Codes, one of the primary modules of my GSoC project, are Maximum Rank Distance (MRD) codes analogous to Reed Solomon in Rank-Metric. In this post, I give a basic overview of the one of the preliminaries, Skew and Linearized Polynomials, required in their construction in Sage.

Consider a non-commutative ring {R = \mathbb{F}[X; \sigma, \delta]} where we have a ring A of usual polynomials in variable X, a ring endomorphism {\sigma} on A and a {\delta}-derivation which is essentially a map {\delta: A \rightarrow A} such that for all a, b in A,

{\delta(a + b) = \delta(a) + \delta(b)}
{\delta(a + b) = \delta(a)b + \sigma(a)\delta(b)}
This ring with the usual addition and modified multiplication subject to the relation above is called a Skew Polynomial Ring of Endomorphism type. Recall that, a Homomorphism is a structure preserving map from one mathematical object (such as group, ring, vector space) to another. And an Endomorphism is a homomorphism from a mathematical object onto itself.

Given a finite field {\mathbb{F}_q} of order q and its extension field {\mathbb{F}_{q^m}} for some fixed positive integer m, a Linearized Polynomial in variable X is given by

{L(X) = \sum_{i=0}^{n-1} a_i X^{q^i}}

where each of the coefficients {a_i} belongs to {\mathbb{F}_{q^m}} and the exponents of the monomials are powers of q. The degree of this polynomial, also called the q-degree, is n-1. The non-commutative univariate Linearized Polynomial Ring consisting of all such polynomials L(X) over {\mathbb{F}_{q^m}} is denoted by {\mathbb{L}_{q^m}}[X]. Ernst Gabidulin used this ring to build Gabidulin codes where codewords are given by the coefficients of the polynomials, i.e. {C = (a_0, a_1, . . . , a_{n-1}) \in \mathbb{F}_{q^m}^{n} }.

Linearized and Skew Polynomial Rings are isomorphic with matching evaluation maps. More specifically, when the derivation {\delta} is 0 and the endomorphism {\sigma} is a Frobenius Automorphism (recall that an automorphism is an endomorphism that admits an inverse and for a finite field, a Frobenius Endomorphism is always also a Frobenius Automorphism), the Skew Polynomial Ring becomes a Linearized Polynomial Ring. That is to say, the latter are a special case of the former.

Sage has an open ticket that already implements the Skew Polynomial Ring and provides functionality to evaluate a given polynomial and perform basic operations such as addition, subtraction, multiplication and division. Our aim therefore, is to complete the open ticket and use that to create the appropriate, required linearized polynomial ring.

 

 

Published by arpitdm

Published

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.