Pitfalls of implementing rank-metric codes (and skew polynomials)

[Johan S. R. Nielsen]

Hi sage-coding-theory

In the hope that the GSoC project "Rank-metric codes" will be sponsored, I'd like to discuss pitfalls wrt. the design and implementation that we should be aware of. This can also assist the prospective students in writing their project description.

The project should cover at least:
- Support skew polynomials natively in Sage (see #13215).
- Mirror LinearCode and the related classes to get the rank metric
analogue.
- Gabidulin codes, encoding, decoding and obvious queries.

#13215 looks like very solid code, and though it has been stale for some years, I think it will fit our purpose very well (note that it doesn't support skew polynomial rings with derivation, but that's probably OK). It will be a chore to review it, but it sure seems worth it! I've Cc'ed the author Xavier Caruso, and I'm hoping he has some input and is interested in helping out with finally getting his code reviewed.

In Gabidulin codes, we jump between the GF(q^m) and the GF(q)^m descriptions all the time. This should be supported elegantly and efficiently, even when q is not prime. A mechanism for this, for a specific choice of basis of GF(q^m) over GF(q), is implemented in #20039.

Once everything is correct and working, a concern is speed: most literature on Gabidulin codes suggest using normal bases to represent GF(q^m) over GF(q), so the Frobenius automorphism can be done very fast. Frobenius Endomorphisms for finite fields were in general implemented in #13214 (by Caruso, author of #13215). We might want to look into this.

Comments? Experiences?
Best,
Johan

[Johan S. R. Nielsen]

Since we will be using the skew polynomial description of Gabidulin codes, here are a few articles that use that description:

- The following describe some of the algebraic link between the linearized and skew polynomials, and goes on to construct new codes using skew polynomials with derivations:

  Boucher, D., and F. Ulmer. n.d. “Linear Codes Using Skew Polynomials with Automorphisms and Derivations.” Designs, Codes and Cryptography, 1–27. doi:10.1007/s10623-012-9704-4.
  https://hal.archives-ouvertes.fr/hal-00597127/document

- This paper doesn't describe the link but just uses the description of skew polynomials to decode:

  Sidorenko, Vladimir, Lan Jiang, and Martin Bossert. 2011.
  “Skew-Feedback Shift-Register Synthesis and Decoding Interleaved
  Gabidulin Codes.” IEEE Transactions on Information Theory 57 (2):
  621–632.

- A paper I coauthored, where we use the skew polynomial language. We mention the link but do not really spend much time on it:

  http://jsrn.dk/publications.html#2016-dcc-skew-module

The algorithm in the latter paper, the Mulders-Storjohann for skew polynomials, is quite likely the conceptually easiest way to implement a decoding algorithm. (decoding a standard Gabidulin code is then done by doing a single shift register, where the l=1 in Section 5 of my paper. An error-erasure decoding is also described; it is restricted to only certain "nice" Gabidulin codes).

Best,
Johan