Fast algorithms for determining the linear complexity of sequences over GF(p/sup m/) with period 2/sup t

摘要

We prove a result which reduces the computation of the linear complexity of a sequence over GF(p/sup m/) (p is an odd prime) with period 2n (n is a positive integer such that there exists an element b/spl isin/GF(p/sup m/), b/sup n/=-1) to the computation of the linear complexities of two sequences with period n. By combining with some known algorithms such as the Berlekamp-Massey algorithm and the Games-Chan algorithm we can determine the linear complexity of any sequence over GF(p/sup m/) with period 2/sup t (such that 2/sup t/|p/sup m/-1 and gcd(n,p/sup m/-1)=1) more efficiently.