Some Results On The Synthesis Algorithm And Cyclically Distinctness Of Primitive Sequences Over Z/(2~e-1)

Primitive sequences over integer residue ring Z/(2e1) are a class of pseudorandomsequences with important applications. The outputs of them are bit sequences with goodperiodicity and rich nonlinear structure. What’s more, every bit sequence contains allinformations of the original sequence. They had been chosen as the driving sequence of the ZUCalgorithm, a new cryptographic algorithm that was included in4G mobile standard in2011.Primitive sequences over Z/(2e-1) have been an important topic in stream cipher. In this thesis wediscuss the recovering algorithm and cyclically distinctness of the primitive sequences, the mainresults are as follows:1. In this thesis, a theoretical recovering algorithm is presented which can recover theoriginal sequence by using a number of bits of its known bit sequence. From it, we can get thenonlinear relation between the known coordinate sequence and the unknown one by study thecarry bits generated from module2e1. Using this relation, we can establish a series of nonlinearequations over GF(2). The algorithm transforms the recovering problem into the establishing andsolving of certain set of nonlinear equations.2. The cyclically distinctness between bit sequences of primitive sequences over Z/(2e1) isproposed and studied.In the design of cryptographic algorithm working on words, if two different bit sequencesare cyclically equivalent, it is easy to recover a sequence form the other one, which is a potentialthreat to use the two sequences simultaneously. If the sequences are strictly cyclically distinct,which says that any two of them are cyclically distinct, some bit sequences leak will take no riskto the other one. The strictly cyclically distinctness of bit sequences depicts the correlationproperty partially. And it provides a basis for the selections of these sequences.A simple judgment method is proposed by the study of the cyclically distinctness betweenbit sequences of primitive sequences over Z/(2e1). Furthermore, the necessary and sufficientconditions of the strictly cyclically distinctness of bit sequences are presented with the methodwhen e is powers of2or e is a prime number. It is easily to judge the cyclically distinctness ofprimitive sequences over Z/(2e1) by the canonical representation of2e1and the parameters ofthe chosen primitive polynomial.Furthermore, the whole results on the cyclically distinctness of bit sequences of primitivesequences over Z/(2e1) are got when e takes the word size of computer. They shows that:(1) Ife=2h（h=6,7,…,13）, or if e=4and the degree of primitive polynomial is even, the bit sequences are strictly cyclically distinct.(2) If e=2,8,16,32, or if e=4and the degree ofprimitive polynomial is odd, the bit sequences are cyclically equivalent with half period shiftsand cyclically distinct with any other shifts.