Linearized Shift-Register Synthesis
Vladimir R. Sidorenko, Gerd Richter, Martin Bossert · IEEE Transactions on Information Theory · 2011
An efficient algorithm synthesizing all shortestq-linearized-feedback shift-registers generating a given sequence of lengthNover a finite field \BBFqmis derived and its correctness is proved. This algorithm, which is a generalization of the Berlekamp-Massey algorithm, has time complexityO(lN)O(N2) operations in \BBFqm, wherelis the linearized complexity of the sequence. The algorithm can be applied for efficiently solving the key equation when decoding Gabidulin codes.