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 F(q)(m) is derived and its correctness is proved. This algorithm, which is a generalization of the Berlekamp-Massey algorithm, has time complexity O(lN) less than or similar to O(N(2)) operations in, where F(q)(m), where l is the linearized complexity of the sequence. The algorithm can be applied for efficiently solving the key equation when decoding Gabidulin codes.
shift-register synthesis linearized complexity key equation gabidulin codes linearized-feedback