Loading web-font TeX/Main/Regular
Reducing the Computation of Linear Complexities of Periodic Sequences Over - | IEEE Journals & Magazine | IEEE Xplore

Reducing the Computation of Linear Complexities of Periodic Sequences Over {\hbox {GF}}(p^m)


Abstract:

The linear complexity of a periodic sequence over {\hbox{GF}}(p^m) plays an important role in cryptography and comm...Show More

Abstract:

The linear complexity of a periodic sequence over <formula formulatype="inline"> <tex>{\hbox{GF}}(p^m)</tex></formula> plays an important role in cryptography and communication (see Menezes, van Oorschort, and Vanstone, <emphasis>Handbook of Applied Cryptography. Boca Raton, FL: CRC, 1997</emphasis>). 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 <formula formulatype="inline"> <tex>{\hbox{GF}}(p^m)</tex></formula> to the computation of the linear complexities and minimal connection polynomials of <formula formulatype="inline"><tex>u</tex> </formula> period <formula formulatype="inline"><tex>n</tex></formula> sequences. The conditions <formula formulatype="inline"><tex>u\,\vert\,p^m-1</tex> </formula> and <formula formulatype="inline"><tex>{\rm gcd}(n,p^m-1)=1</tex> </formula> 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 <formula formulatype="inline"><tex>{\hbox{GF}}(p^m)</tex> </formula> are presented.
Published in: IEEE Transactions on Information Theory ( Volume: 52, Issue: 12, December 2006)
Page(s): 5537 - 5539
Date of Publication: 31 December 2006

ISSN Information:


I. Introduction

For a period sequence over a finite field , its linear complexity is defined to be the length of the shortest linear feedback shift register to generate it, i.e., the smallest positive integer such that there exist some in and hold for all . The polynomial is called the minimal connection polynomial [12].

References

References is not available for this document.