Fast Algorithms for Determining the Minimal Polynomials of Sequences with Period kn over GF(P(superscript m))

10.6633/IJNS.200807.7(1).05

Jian-Qin Zhou

Cryptography ； linear complexity ； minimal polynomial ； stream cipher

International Journal of Network Security

7卷1期（2008 / 07 / 01）

38 - 41

英文

A fast algorithm is derived for determining the linear complexity and the minimal polynomials of sequences over GF(p(superscript m)) with period kn, where p is a prime number, gcd(n, p(superscript m)-1)=1 and p(superscript m)-1=ku, n, k and u are integers. The algorithm presented here covers the algorithm proposed by Chen for determining the minimal polynomials of sequences over GF(p(superscript m)) with period 2(superscript t)n, where p is a prime, gcd(n, p(superscript m)-1)=1 and p(superscript m)-1=2(superscript t)u, n and u are integers. Combining our result with some known algorithms, it is possible to determine the linear complexity of sequences over GF(p(superscript m)) with period kn more efficiently. Finally an example applying this algorithm is presented.