Pseudorandomness Of Fcsr Sequences And Linear Complexity,

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).