Research On Some Properties Of Primitive σ -LFSR Sequences

The design of driven component is an important part in stream cipher design. The aim of the driven component is to produce sequences with large period and good pseudo randomness properties, and the driven component's efficiency and resource consumption must also be considered.σ-Linear Feedback Shift Register(σ-LFSR) is a large class of Linear Shift Registers based on words. It takes the word of CPU as basic operation uint. Meanwhile, it can construct maximal period sequences with better cryptographic properties on fewer basic instructions of the computer, which could be another new choice for the design of software oriented driven component with giving attentions to cryptographic properties, efficiency and resource consumption.In this paper, we focus on the construction, enumeration, interval vectors'calculation and decimation properties of primitiveσ-LFSR sequences and properties of a class of multi-sequences. Our contributions are as follows:The first part studies the construction and enumeration of a class ofσ-LFSR primitive sequences—Z primitiveσ-LFSR sequences. We studies the calculation of interval vectors of Z primitiveσ-LFSR sequences and presents an improved method to calculate the interval vectors of Z primitiveσ-LFSR sequences of order n over F_2^m , which uses the interval vectors of Z primitiveσ-LFSR sequences of order 1 to calculate that of Z primitiveσ-LFSR sequences of order n over F_2^m and is more effective than other existing methods. Most importantly, the new method can also be applied to the calculation of interval vectors of m-sequences over F_2^m . The enumeration formula of Z primitiveσ-LFSR sequences of order n over 2mF is also presented, which shows that the number of Z primitiveσ-LFSR sequences of order n is much larger than the number of m-sequences of order n over F_2^m .The second part discusses the calculation of interval vectors of primitive sequences. Firstly, the equivalence between calculation of interval vectors of primitiveσ-LFSR sequences and calculation of discrete logarithms over finite field is proved, at the same time a calculation method for interval vectors of primitiveσ-LFSR sequences is given. Secondly, another calculation method for interval vectors of a class of primitiveσ-LFSR sequences was obtained, which converted the calculation of discrete logarithms over finite field to its subfield and the complexity was much lower. Lastly, the interval vector of primitiveσ-LFSR sequence in stream cipher Sober-t32 is calculated.The third part analyzes the decimations of primitive sequences. Firstly, it is proved that for aσ-LFSR primitive sequences s of order n over F_2^m , every 2^mj-th decimation of s is shift equivalent with s if and only if s is a Z primitiveσ-LFSR sequence where 0≤j≤n ? 1. Then we prove that for a Z primitive s of period T, every d-th decimation of s is also a Z primitiveσ-LFSR sequences s of period T, where ( d , T ) = 1. Lastly, some decimation properties of Z primitiveσ-LFSR sequences are also discussed.In the last part, the pseudorandom properties and linear complexity of a class of multi-sequences over F₂ , whose coordinate sequences are mn stages m-sequences with the same minimal polynomial, are studied. Firstly, we proved that the multisequences have the good pseudo randomness properties if their coordinate sequences are linear relevant. Secondly, the linear complexity of the multisequences is obtained, which is kn, where 1≤k≤m.