Linearized Shift-Register Synthesis

An efficient algorithm synthesizing all shortest q -linearized-feedback shift-registers generating a given sequence of length N over a finite field BBFqm is derived and its correctness is proved. This algorithm, which is a generalization of the Berlekamp-Massey algorithm, has time complexity O(lN) <;~O(N²) operations in BBFqm, where l is the linearized complexity of the sequence. The algorithm can be applied for efficiently solving the key equation when decoding Gabidulin codes.