FCSR序列的伪随机性及线性复杂度

【作者】 徐洪；

【导师】 戚文峰；

【作者基本信息】 中国人民解放军信息工程大学 ， 密码学， 2003， 硕士

【摘要】 带进位反馈移位寄存器序列简称FCSR序列，其中最重要的是极大周期FCSR序列，即l-序列．它有许多类似于m-序列的伪随机性质．令q=p^e，若2为模q的本原元，则以q为联接数的极大周期FCSR序列是l-序列，周期为T=φ（q）． 本文首先研究了l-序列在部分周期中（即一个周期内任意连续一段）的0、1分布，给出了估计值，指出当寄存器的级数较大时，其0、1个数大约各占一半．特别的，若联接数为素数p，则l-序列在长为μT（0＜μ＜1）的任意一段中出现1的个数所占的比例（?）（1）满足： 其次讨论了l-序列的线性复杂度，指出它有紧的上界T／2+1，并给出了一个下界．特别当e≥2时，其线性复杂度有下界2^t-1+1+T／p，其中2^t‖（p-1）．更多还原

【Abstract】 FCSR sequences are the abbreviation for feedback with carry shift register sequences. Among these, the most important are maximum-period FCSR sequences, that is, l-sequences. They have many good pseudorandom properties similar to m-sequences. Set q =pe, if 2 is a primitive element modulo q, then the maximum-period sequence generated by a FCSR with connection integer q is an l-sequence, with period T= (q).In this paper, the distribution of 0 and 1 in a partial period of l-sequences, that is, in a segment shorter than the period, is estimated. It was showed that the 0.’s and 1 ’s are almost equal when the size of the register is large enough. In particular, if the connection integer is a prime number p, then the proportion of 1’s in a segment of l-sequence with length T(0< <1) satisfiesNext the linear complexity of l-sequences is discussed. A tight upper bound (772 + 1) and a lower bound are presented. It is showed that if e 2, then the linear complexity of the l-sequenceis at least 2t-1 +l + T/p, where 2t|| (p-1).更多还原