非线性组合序列的线性复杂度

Linear Complexity of Nonlinear Combination Sequences

流密码系统中常用的一种滚动密钥生成器由n个线性移位寄存器组成,这n个线性移位寄存器的输出序列用一个非线性函数组合后产生密钥流。因而控制非线性组合序列线性复杂度的问题是非常重要的。证明任意多最大长度GF(q)序列的乘积有最大线性复杂度如果它们的极小多项式有两两互素的次数。这个结果被扩展到乘积序列的任意线性组合。早期关于布尔形组合序列的结果被推广。

A common type of running-key generator employed in stream cipher systems consists of n linear feedback shift registers whose output sequences are combined in a nonlinear function to produce the key stream. In this paper, we prove that the product of any ntL-nber of maximum-length GF（q） sequences has maximum linear complexity if their minimal polynomial have pair wise relatively prime degrees. This result is extended to arbitrary linear combinations of product sequences. The earlier result on the linear complexity of Boolean form combination sequences is generalized.