Research On Some Related Problems Of σ-LFSR Sequences

σ-Linear Feedback Shift Register(σ-LFSR) is a kind of word-oriented LFSR.It is suitable for fast software and hardware implementation in modern processors.There is a wide space to choose based on the conjecture about primitive σ-LFSR.The presented of σ-LFSR give us a new choice for the cryptographic system which is giving attentions to security,efficiency and resource consumption.In this paper, we focus on the study of some properties and the application of σ-LFSR sequences.Our contributions to the field of σ-LFSR are as follows:1.We made a classification about the interval vectors based on the character of it.We gave that σ-LFSR sequences were shift equivalent when the decimation sequences were shift equivalent.We constructed primitive σ-LFSR and Z primitive σ-LFSR.The population means of a class of primitive σ-LFSR’s interval vector was ED=(0,T/2,T/2,…,T/2).The decimation conjecture was dicussed.We proved that the decimation conjecture was correct in a special case and another conjecture about the decimation was wrong.The properties of the lz decimation of Z primitive σ-LFSR was studied and a algorithm was given to judge Z primitive σ-LFSR.2.We studied the cross-correlation properties of primitive σ-LFSR. The upper bound of the cross-correlation of σ-LFSR with the odd decimation was obtained using the exponential sums including Weil’s sum.Gave the five-value cross-correlation of σ-LFSR with the decimation d=22k+1/2k+1and the two-value cross-correlation of Z primitive σ-LFSR with the decimation d=qmi.3.We proved that the first invariant factor of the minimal polynomial matix of σ-LFSR was the unique minimal generator.Gave a sufficient and necessary condition which can be used to check whether a vector sequence was σ-LFSR sequence.Gave a method to judge whether a σ-LFSR sequence was primitive σ-LFSR through linear exchange sequences.A special class of m and n was given when the linear complexity of primitive σ-LFSR achieved mn.We discussed the relationship between interval vector and the linear complexity of the primitive σ-LFSR sequences.4. An application of σ-LFSR was studied. The permutation of block cipher was constructed using the primitive σ-LFSR,then three methods for fast implementation were given,the branch number of the permutation was analysed.