Fast Root Finding for Interpolation-Based Decoding of Interleaved Gabidulin Codes

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 Fq^m, where ℓ is the interleaving degree, n the code length, Fq^m the base field of the code, 2 ≤ ω ≤ 3 the matrix multiplication exponent, and M(n) O(n¹⁶³⁵) 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(ℓ³n²), in some cases O(ℓ²n²).