求周期序列线性复杂度的快速算法

A fast algorithm for determining the linear complexity in periodic sequences

基于有限域GF(q)上的分圆多项式理论,提出和证明了求周期为qnpm的GF(q)上序列的线性复杂度和极小多项式的一个快速算法,这里p与q均为素数,且q是模p2的本原根.该算法既推广了求周期为pm的GF(q)上周期序列的线性复杂度的一个快速算法,也推广了求周期为2npm的二元周期序列的线性复杂度的一个快速算法.

Based on the theory of cyclotomic polynomial over finite field GF（q）, a fast algorithm wasderived for determining the linear complexity and the minimal polynomial of periodic sequences overGF（q） with period qnpm , where p and q are prime numbers, and q is a primitive root modulo p2. Thealgorithm presented here covers both the algorithm determining the linear complexity of periodic se-quences over GF（q） with period pm and the algorithm determining the linear complexity of binary periodic sequences with period 2npm.