On The Distinctness Of Sequences Derived From Primitive Sequences Over Integer Residue Rings

Under the influence of NESSIE project and eSTREAM project, it is universally acceptedthat a secure stream cipher should be built on nonlinear driving blocks. Accordingly, how todesign and analyse sequences with desirable nonlinear structure naturally become one ofimportant topics in the field of stream ciphers.Since the existence of carry operations, the linear recurring sequences over integer residuerings （called sequences over rings in short） inherently have complex nonlinear structure. Inliterature, two kinds of compression mappings have been proposed to derive nonlinear sequences:one is based on e-variable functions over Z/（p）; the other is based on the modular operation. Thisdissertation is dedicated to study these two kinds of nonlinear sequences, in order to providemore theoretical foundations and technologies for their further applications.Let pebe an odd prime power, f （x） a strongly primitive polynomial over Z/（pe）, and a=a₀+a₁p++a_e-1 p^e-1a primitive sequence generated by f （x） over Z/（pe）. Let η (x₀, x₁,…, x_e-2) bean e1-variable function over Z/（p）. The first part of this dissertation focus on sequences of theform a_e-1+η(a₀, a₁,…, a_e-2) and investigates their information distribution law. The mainresult is as follow.1. If the coefficient of x_e-2^p-1 x₁^p-1x₀^p-1in η is not equal to （-1）^e （p+1）/2, then for any s∈Z/（p） and any k∈（Z/（p））*, the distribution of element s of a_e-1+η(a₀, a₁,…, a_e-2) at times twith α（t）=k contains all the information of the original sequence a. That is to say, if thedistribution of element s of a_e-1+η(a₀, a₁,…, a_e-2) is the same as that of b_e-1+η(b₀,b₁,…, b_e-2 at times t with α（t）=k, then a=b, where a and b are two primitive sequencesgenerated by f （x） over Z/（pe）, and α is an m-sequence over Z/（p） uniquely determined by f （x）and a₀. Moreover, it is shown that the two conditions: the coefficient of x_e-2^p-1 x₁^p-1x₀^p-1 in η isnot equal to （-1）^e （p+1）/2and k∈（Z/（p））*, are both necessary, since otherwise there existcounterexamples.The second part of this dissertation focus on the element distribution of primitive sequencesover Z/（M）, as well as the element distribution of their modulo2reductions, where M is an oddinteger that is composite and square-free. This part is not only independently interest, but alsoserves an important foundation for the next part. The main results we obtained are as follows.2. Based on the estimates of exponential sums over integer residue rings, a sufficientcondition is given for ensuring that every element in Z/（M） occurs in any given primitivesequence of order n over Z/（M）. Then it is shown that for any fixed M, the sufficient condition isalways satisfied if n is sufficiently large. Experimental data further implies that for the greatmajority of M, n≥7is already large enough. 3. Let a be a primitive sequence of order n over Z/（M） with period T and [a]mod2the modulo2reduction of a. For any s∈{0,1} and0<μ≤1, it is shown that the proportion of s within asegment of [a]mod2of length L=「μ·T」 tends to the average value （M+12s）/2M as n�'∞.This implies that the element distribution of [a]mod2is often imbalanced, and the bias of theproportion of0and1is about1/M. However the bias can be easily reduced to anundistinguishable grade since a termwise exclusive or of several phase-shifts of [a]mod2will havedesirable element distribution property.4. For any primitive sequence a of order1over Z/（M）, it is conjectured that there must be anonzero even element occurring in a, which has been verified for all square-free odd integersless than300,000. Based on the estimates of exponential sums over integer residue rings andseveral number theoretical functions, the conjecture is partial proven by showing that there is asubset of square-free odd integers with asymptotic density1such that the conjecture is alwaystrue.The third part of this dissertation focus on the distinctness of modular reductions ofprimitive sequences over Z/（M）. Let f （x） be a primitive polynomial of degree n over Z/（M）,H <M is an integer divisible by a prime number coprime with M. For any two primitivesequences a and b generated by f （x） over Z/（M）, if a=b iff a≡b （mod H）, then we say thatprimitive sequences generated by f （x） are pairwise distinct modulo H. Such "distinctnessproperty" is significant for the cryptographic applications of modular reductions of primitivesequences over Z/（M）. The main results obtained in this part are as follows.5. A new sufficient condition is given for ensuring that primitive sequences generated by aprimitive polynomial of degree n over Z/（pq） are pairwise distinct modulo2, where p and q aretwo distinct odd prime numbers. Comparing with the previous result obtained by H.J. Chen in2009, the set of primitive sequences that can be included by the new sufficient condition isgreatly enlarged.6. For e∈{4,8,16,32,64}, it is shown that primitive sequences generated by a primitivepolynomial f （x） of order n over Z/（2^e-1） are pairwise distinct modulo2. This result is obtainedbasing on the assumption that every element in Z/（2^e-1） occurs in any given primitive sequencegenerated by f （x） over Z/（2^e-1）, which it is known to be valid for7≤n≤10000.7. For a general odd integer M that is composite and square-free, a sufficient condition isgiven for ensuring that primitive sequences generated by a primitive polynomial of degree n overZ/（M） are pairwise distinct modulo2. The number of primitive polynomials satisfying thesufficient condition is highly related to two distribution properties of primitive sequences overZ/（M）, which have been studied in the second part of this paper. Moreover, expermental dataimply that the great majority of primitive polynomials of order n over Z/（M） can be included by the sufficient condition.8. As for an odd integer M that is composite and square-free, under the assumption thatevery element in Z/（M） occurs in any given primitive sequence generated by f （x） over Z/（M）, itis shown that primitive sequences generated by f （x） over Z/（M） are pairwise distinct modulo H,where H is an integer divisible by4or by an odd prime number coprime with M.The last part of this paper focus on the software implemention of primitive sequences overZ/（2^e-1）, and some effective technologies are introduced to improve its efficiency.