Distribution Properties of Binary Sequences Derived from Primitive Sequences Modulo Square-free Odd Integers

摘要

Recently, a class of nonlinear sequences, modular reductions of primitive sequences over integer residue rings, was proposed and has attracted much attention. I1) were used in the ZUC algorithm. In this paper, we study the distribution pn particular, modulo 2 reductions of primitive sequences over Z/(2~(31)-roperties of modulo 2 reductions of primitive sequences over Z/(M), where M is a square-free odd integer. Let a be a primitive sequence of order n over Z/(M) with period T and [a]_(mod 2) the modulo 2 reduction of a. With the estimate of exponential sums over Z/(M), the proportion f_s of occurrences of s within a segment of [a]_(mod 2) of length μT is estimated, where s ∈ {0,1} and 0 ＜ μ ≤ 1. Based on this estimate, it is further shown that for given M and μ, f_s tends to (M+1-2s)/2M as n → ∞. This result implies that there exists a small imbalance between 0 and 1 in [a]_(mod 2), which should be taken into full consideration in the design of stream ciphers based on [a]_(mod 2).