Research On The Pseudorandom Properties Of Maximal Period FCSR Sequences And Some Related Sequences

Feedback with carry shift register (FCSR) is a new kind of keystream generators proposed by Klapper and Goresky. The architecture determines that FCSR sequences possess high linear complexity naturally, while for linear feedback shift register (LFSR) sequences, some modifications, such as nonlinear filtering and clock-controlling, must be done to obtain high linear complexity. The maximal period sequence generated by an FCSR is called an l-sequence. Such sequences have many fine pseudorandom properties similar to m-sequences, such as 0?1 balanceness, and fine run properties etc.The 2-adic complexity of a binary sequence characterizes the size of the shortest FCSR that generates the sequence. Similar to BM algorithm, there also exists a corresponding 2-adic rational approximation algorithm, which can efficiently compute the 2-adic complexity of binary sequences. The FCSR sequences, such as l-sequences, cannot be used directly as keystream sequences because of their comparatively low 2-adic complexity. Up to now, the linear filter of FCSR (F-FCSR) is the most efficient stream cipher based on FCSR. In this dissertation, we make a further study on some other pseudorandom properties of l-sequences, which can be a valuable reference for the design of the FCSR-based stream ciphers.Let a be an l-sequence or its decimation with period T= pe-1(p-1) generated by an FCSR with connection integer q=pe,and let an= (A�gn (mod q)) (mod 2) be its exponential representation, where g is a primitive root modulo q, and gcd(A, q)=1.In the first part of this dissertation, with the help of estimate of exponential sums over residue rings, we discuss the autocorrelation property of l-sequences and their decimations. Our results show that such sequences have fine autocorrelation properties. The main results are as follows:1. We show that when the shift?runs through all integers between 1 and T-1, the expected autocorrelation value of the l-sequence or its decimation a is 0, and the variance is Var(Ca(?))= O(q ln4q). From Chebyshev's inequality we know that, when the connection integer q is a little larger, most autocorrelations of l-sequences and their decimations are low.2. When the connection integer is a prime number p, we show that the autocorrelation function Ca(?) of the l-sequence or its decimation a satisfies Thus by calculating such triangular sum, we can easily obtain an estimate of Ca(?). Especially, let?be the shift such that |g?(mod p)|= 2 or (p-1)/2, then the corresponding autocorrelation value of a is Ca(?)= O(ln2p), which is also very low when p is a little larger.3. When the connection integer is a prime power pe (e?2), we show that for any positive integer i,1?i?e/2, when the shift is?= kT/(2pi), the corresponding autocorrelation value of the l-sequence or its decimation a is where 1?k?2pi-1, and gcd(k, p)= 1. This result shows that there do exist some shifts, such that the corresponding autocorrelation values of the l-sequence or its decimation are high.In the second part of this dissertation, using the fine properties of the level sequences of primitive sequences over residue rings, we analyze the distinctness of decimations of l-sequences, and obtain the following result:4. When the connection integer is a prime power, we show that the decimations of any l-sequences are cyclically distinct, which verifies the conjecture (Conjecture 1.1) proposed by Goresky and Klapper several years ago in the case of prime powers.Let u be a primitive sequences over ring Z/(pe), generated by a primitive polynomial f(x) of degree n. Then call the sequence a= u (mod 2) a generalized l-sequence of order n derived by f(x), or call it a generalized l-sequence for simplicity. Such sequences can be seen as a natural generalization of l-sequences.In the third part of this dissertation, using the fine properties of the level sequences of primitive sequences over residue rings, we further analyze the distinctness of generalized l-sequences. Let f(x), g(x) be two different primitive polynomials of degree n over Z/(pe). The main results are as follows:5. On the basis of some existing result, we show that when e=1, almost for all odd prime numberp, the generalized l-sequences derived by f(x), g(x) are cyclically distinct.6. When e?2, we show that if f(x) (?) g(x)(mod p), then the generalized l-sequences derived by fix), g(x) are cyclically distinct. Furthermore, when f(x)(?) g(x) (mod p), almost for all such primitive polynomials, the corresponding generalized l-sequences are cyclically distinct. Particularly, the decimations of any generalized l-sequence are cyclically distinct.