Research On The Modulo 2 Distinctness Of Families Of Primitive Sequences Over Z/(2~e-1)

2008, X.Y. Zhu etc. proposed a new class of sequences called primitive sequences over Z/(2~e - 1). It is found that these sequences have good periodicity and complicated nonlinear structure. What’s more, every 2-adic coordinate sequence preserves all the information of the original sequence. These properties make them very suitable to being a bulding block for a stream cipher. In particular, primitive sequences over Z/(231 - 1) have been used in the ZUC algorithm, a new stream cipher accepted by 3GPP SA3 as a new inclusion in the LTE standards. However, on the other hand, present work on the primitive sequences over Z/(2~e - 1) are incomplete and there still exsist several important problems needed to be further explored, such as the distinctness of the modulo 2 reductions of primitive sequences over Z/(2~e - 1) and the modulo 2 distinctness of the families of primitive sequences over Z/(2~e - 1), which limit the application of these sequences. This thesis dedicates to the research on the modulo 2 distinctness of the families of primitive sequence over Z/(2~e - 1), ensuring that the primitive sequences generated by different primitive polynomials are pairwise distinct modulo 2. The main results are as follows:1. Let f(x) and g(x) be two different primitive polynomials of degree n over Z/(2~e - 1). If for any a ? G￠( f(x), 2~e - 1) and b ? G￠( g(x), 2~e - 1), a 1 b(mod 2), then we say G￠( f(x), 2~e - 1) and G￠( g(x), 2~e - 1) are distinct modulo 2. When e ? {4, 8, 16, 32}, by the special propery of 2~e - 1, we proved that if a and b have different distribution of 0 then a 1 b(mod 2). Furthermore, a sufficient condition is given for ensuring that the primitive sequences over Z/(2~e - 1) have different distribution of 0. For e ? {4, 8, 16, 32}, it is shown that if( f(x) mod 3, g(x) mod 3) is 0-independent over Z/(3) and 2 ￡ n ￡ 10,000, then the primitive sequences generated by f(x) and g(x) have different distribution of 0.2. Let M be a square- free odd integer. In the research of entropy-preservation of the modulo 2 reductions of primitive sequences over Z/(M), Q.X. Zheng etc. proposed the even conjecture, which is there exsists an even number in the primitive sequences of order 1 over Z/(M). Though, the even conjecture is shown useful to the research on the distinctness of modulo 2 reduction of primitive sequences and the modulo 2 distinctness of families of primitive sequences, it has not been completely proven. In this thesis, by the method of decimation and the Carner’s Chinese Reminder Theorem, we proved that the even conjecture is valid over Z/(pq), where p, q are two different odd prime numbers.3. Based on the result of 2, a sufficient condition is given for ensuring that the families of primitive sequences over Z/(pq) are distinct modulo 2. It is shown that if f(x) or g(x) is a typical primitive polynomial over Z/(pq) and( f(x) mod p, g(x) mod p) is 0-independent over Z/(p), and if the inequality qn - 1 > qn/2×gcd((pn - 1)/(p - 1), qn - 1) holds, then the primitive sequences generated by f(x) and g(x) are distinct modulo 2. When 3 ￡ p < q ￡ 10,000, 2 ￡ n ￡ 19, experimental data shows that there are more than 99.99% of tri- tuples( p, q, n) satisfies the inequlity. Furthermore, based on the even conjecture over Z/(M), the results of modulo 2 distinctness property over Z/(pq) are generalized to Z/(M).