Reducing the Computation of Linear Complexities of Periodic Sequences Over ${\hbox {GF}}(p^m)$
Hao Chen · IEEE Transactions on Information Theory · 2006
The linear complexity of a periodic sequence over ${\hbox{GF}}(p^m)$ plays an important role in cryptography and communication (see Menezes, van Oorschort, and Vanstone, Handbook of Applied Cryptography. Boca Raton, FL: CRC, 1997 ). In this correspondence, we prove a result which reduces the computation of the linear complexity and minimal connection polynomial of a period un sequence over ${\hbox{GF}}(p^m)$ to the computation of the linear complexities and minimal connection polynomials of $u$ period $n$ sequences. The conditions $u\,\vert\,p^m-1$ and ${\rm gcd}(n,p^m-1)=1$ are required for the result to hold. Some applications of this reduction in fast algorithms to determine the linear complexities and minimal connection polynomials of sequences over ${\hbox{GF}}(p^m)$ are presented.