GF(2)上伪随机序列s~∞与~∞的复杂性分析

The complexity of pseudo-random sequences s~∞ and~∞ over GF(2)

提出了域GF(2 )上伪随机序列s∞ 的极小多项式fs(x)与s∞ 按位取反后所得序列 s∞ 的极小多项式f s(x)之间的关系表达式 .关系表明f s(x)等于 (1+x)fs(x) ,若x =1不是fs(x)的根 ;f s(x)等于 (1+x)f1(x) ,若x =1是fs(x)的单根且fs(x)等于 (1+x)f1(x) ;f s(x)等于fs(x) ,若x =1是fs(x)的重根 .利用上述关系分析了域GF(2 )上伪随机序列sN 与 sN 的重量复杂度之间的关系 ,结果表明重量复杂度WCu(sN)和WCN-u(sN)的差不超过 1,这样可使重量复杂度的计算量减少一半 .文中所提出的关系可用于分析域GF(2 )

The relation between f s(x) and f (x) over field GF(2) is presented, in which f s(x) and f (x) are the minimum generate polynomials of the pseudo random sequences s ∞ and its bit wise negative sequences ∞ respectively. The relation shows that f (x) equals (1+ x) f s(x) when x= 1 is not the root of f s(x),that f (x) equals (1+ x) f 1(x) when f s(x) equals (1+ x) f 1(x) and x= 1 is the single root of f s(x), and that f (x) equals f s(x) when x= 1 is the multiple root of f s(x). The conclusion is that the difference between the linear complexity of s ∞ and ∞ is not greater than one. With the above relation the weight complexity of the pseudo random sequences s N over field GF(2) is discussed, and the result shows that the difference of weight complexity between W C u (s N) and W C N-u s N) is not greater than one. The relation presented can be used to analyze the complexity of pseudo random sequences over GF(2).