Abstract
Recently, a class of nonlinear sequences, modular reductions of primitive sequences over integer residue rings, was proposed and has attracted much attention. In particular, modulo 2 reductions of primitive sequences over \(\mathbf {Z}/(2^{31}-1)\) were used in the ZUC algorithm. In this paper, we study the distribution properties of modulo 2 reductions of primitive sequences over \(\mathbf {Z}/(M)\), where M is a square-free odd integer. Let \(\underline{a}\) be a primitive sequence of order n over \(\mathbf {Z}/(M)\) with period T and \(\left[ \underline{a}\right] _{\text {mod}\, 2}\) the modulo 2 reduction of \(\underline{a}\). With the estimate of exponential sums over \(\mathbf {Z}/(M)\), the proportion \(f_{s}\) of occurrences of s within a segment of \(\left[ \underline{a}\right] _{\text {mod}\, 2}\) of length \(\mu T\) is estimated, where \(s\in \left\{ 0,1\right\} \) and \(0<\mu \le 1\). Based on this estimate, it is further shown that for given M and \(\mu \), \(f_{s}\) tends to \(\frac{M+1-2s}{2M}\) as \(n\rightarrow \infty \). This result implies that there exists a small imbalance between 0 and 1 in \(\left[ \underline{a}\right] _{\text {mod}\, 2}\), which should be taken into full consideration in the design of stream ciphers based on \(\left[ \underline{a}\right] _{\text {mod}\, 2}\).
This work was supported by NSF of China (Nos. 61872383, 61402524, 61872359 and 61602510). The work of Qun-Xiong Zheng was also supported by Young Elite Scientists Sponsorship Program by CAST (2016QNRC001) and by National Postdoctoral Program for Innovative Talents (BX201600188) and by China Postdoctoral Science Foundation funded project (2017M611035).
Access provided by Autonomous University of Puebla. Download conference paper PDF
Similar content being viewed by others
Keywords
1 Introduction
For an integer \(m\ge 2\), let \(\mathbf {Z}/(m)\) denote the integer residue ring modulo m. The set \(\{0,1,\ldots ,m-1\}\) is always chosen as the complete set of representatives for the elements of the ring \(\mathbf {Z}/(m)\). Thus a sequence \(\underline{a}\) over \(\mathbf {Z}/(m)\) is usually seen as an integer sequence over \(\{0,1,\ldots ,m-1\}\). Moreover, for an integer a and a positive integer \(b\ge 2\), let us denote the least nonnegative residue of a modulo b by \(\left[ a\right] _{\text {mod}\, b}\), and similarly, for a sequence \(\underline{a}=(a(t))_{t\ge 0}\) over \(\mathbf {Z}/(m)\), denote \(\left[ \underline{a}\right] _{\text {mod}\, b}=\left( \left[ a(t)\right] _{\text {mod}\, b}\right) _{t\ge 0}\).
Let p be a prime number and e a positive integer. During the past two decades, the maximal period linear recurring sequences over \(\mathbf {Z} /(p^{e})\), called primitive sequences over \(\mathbf {Z}/(p^{e})\), have been paid much attention. An enormous amount of effort is directed toward the study of finding useful mappings to derive good pseudorandom sequences from primitive sequences over \(\mathbf {Z}/(p^{e})\), which are called compression mappings in literature, and proving that they are injective. Generally there are two kinds of compression mappings: one is based on e-variable functions over \(\mathbf {Z}/(p)\) [10, 15,16,17, 20, 21]; the other is based on the modular arithmetic [13, 22]. Besides, the pseudorandom properties of these compression sequences are also extensively studied, such as periodicity [7, 13], linear complexity [3, 6, 15] and distribution properties [2, 8, 12, 23].
Recently research interests on primitive sequences over \(\mathbf {Z}/(p^{e})\) are further extended to primitive sequences over \(\mathbf {Z}/(M)\) [4, 9, 24,25,26,27], where M is a square-free odd integer. One of important reasons for this is that the period of a primitive sequence \( \underline{a}\) of order n over \(\mathbf {Z}/(p^{e})\) is undesirable if \( e\ge 2\). Recall that the period \(per(\underline{a})\) of a primitive sequence \(\underline{a}\) of order n over \(\mathbf {Z}/(p^{e})\) is equal to \( p^{e-1}\cdot \left( p^{n}-1\right) \approx p^{e+n-1}\) [18]. It can be seen that for a fixed prime power \(p^{e}\) with \(e\ge 2\), the period \(per( \underline{a})\) increases slowly and far less than \(p^{e\cdot n}\) as n increases. Therefore, to meet the requirement of long period in practical applications, n should be chosen large enough, which will be high resource consumption in hardware and software implementation. For example, to generate a sequence with period not less than \(2^{64}\) over \(\mathbf {Z} /(2^{8})\), \(\mathbf {Z}/(2^{16})\) and \(\mathbf {Z}/(2^{32})\), the number of bit-registers required must be larger than 456, 784 and 1056, respectively. However for many choices of M, primitive sequences over \( \mathbf {Z}/(M)\) have no such periodic weakness. For cryptographic applications, the moduli of the form \(2^{e}-1\) have attracted much attention since the operation “\(\text {mod}\, 2^{e}-1\)” can be efficiently implemented both in hardware and software, and this offers new possibilities for advancement in the solution of applying linear recurring sequences over integer residue rings. For instance, primitive sequences over \(\mathbf {Z}/(2^{31}-1)\) are used to design the ZUC algorithm, a stream cipher that is the core of the standardised 3GPP confidentiality algorithm 128-EEA3 and the 3GPP integrity algorithm 128-EIA3, see [28].
By applying the operation \(\text {mod}\, 2\) to primitive sequences over \(\mathbf {Z} /(M)\), one can easily obtain a class of binary sequences, called modulo 2 reductions of primitive sequences over \(\mathbf {Z}/(M)\). It is thought that the operation \(\text {mod}\, 2\) destroys the original linear recurrence relation of primitive sequences over \(\mathbf {Z}/(M)\) and the obtained binary sequences should have many desirable cryptographic properties if the modulus M and the order n are carefully chosen. One of the most interesting properties is the so-called “modulo 2 distinctness”. Some progress has been made on the modulo 2 distinctness, see, for example, [9, 26]. From the viewpoint of cryptographic applications, it is naturally interested in the pseudorandom properties of modulo 2 reductions of primitive sequences over \(\mathbf {Z}/(M)\). However, so far few result was obtained. In [25], to study the modulo 2 distinctness of primitive sequences over \(\mathbf {Z}/(M)\), two distribution properties of primitive sequences over \(\mathbf {Z}/(M)\) are investigated. One is to determine whether there is an integer \(t\ge 0\) such that \(a(t)=s\) for a given element \(s\in \mathbf {Z}/(M)\) and a given primitive sequence \( \underline{a}\) of order n over \(\mathbf {Z}/(M)\). The other is to determine whether there is an integer \(t\ge 0\) such that a(t) is an even number for a given primitive sequence \(\underline{a}\) of order 1 over \(\mathbf {Z}/(M)\). In [9], Hu and Wang studied whether there is an integer \(t\ge 0\) such that \(a(t)=a\) and \(b(t)=b\), for two given elements \(a,b\in \mathbf {Z} /(M)\) and two given primitive sequences \(\underline{a},\underline{b}\) generated by a same primitive polynomial over \(\mathbf {Z}/(M)\).
In this paper, we study the distribution properties of the binary sequence \( \left[ \underline{a}\right] _{\text {mod}\, 2}\), where \(\underline{a}\) is a primitive sequence of order n over \(\mathbf {Z}/(M)\) with period T. With the estimate of exponential sums over \(\mathbf {Z}/(M)\), the proportion \(f_{s} \) of occurrences of s within a segment of \(\left[ \underline{a}\right] _{\text {mod}\, 2}\) of length \(\mu T\) is estimated, where \(s\in \left\{ 0,1\right\} \) and \(0<\mu \le 1\). Based on this estimate, it is further shown that for given M and \(\mu \), \(f_{s}\) tends to \(\left( M+1-2s\right) /2M\) as \(n\rightarrow \infty \). Generally speaking, if n is not too small (for example, \(n\ge 3\) for \(M=2^{32}-1\)), then the value of \( f_{s}\) is very close to that of \(\left( M+1-2s\right) /2M\). This implies that there always exists a small imbalance (about 1/M) between 0 and 1 in \(\left[ \underline{a}\right] _{\text {mod}\, 2}\). In order to provide a good resistance against the distinguishing attacks, such imbalance should be taken into full consideration in the design of stream ciphers based on \( \left[ \underline{a}\right] _{\text {mod}\, 2}\). Fortunately, by introducing a moderate amount of exclusive or operations, the imbalance of 0, 1 will be reduced to a small enough extent.
The rest of this paper is organized as follows. Section 2 presents some necessary preliminaries. Section 3 gives the main results of this paper. Finally, conclusions are drawn in Sect. 4.
2 Preliminaries
2.1 Primitive Polynomials and Primitive Sequences over Integer Residue Rings
Let m be an integer greater than 1. If a sequence \(\underline{a}=(a(t))_{t\ge 0}\) over \(\mathbf {Z}/(m)\) satisfies
for all integers \(t\ge n\), where n is a positive integer and \( c_{0},c_{1},\ldots ,c_{n-1}\in \mathbf {Z}/(m)\) are constant coefficients, then \(\underline{a}\) is called a linear recurring sequence of order n over \(\mathbf {Z}/(m)\) generated by \(f(x)=x^{n}-c_{n-1}x^{n-1}-\cdots -c_{0}\) (or \(\underline{a}\) is a sequence of order n over \(\mathbf {Z}/(m)\) in short). For convenience, the set of sequences generated by f(x) over \( \mathbf {Z}/(m)\) is generally denoted by \(G\left( f\left( x\right) ,m\right) \). Particular interests for cryptography are the maximal period linear recurring sequences also called primitive sequences over \(\mathbf {Z}/(m)\), which are generated by primitive polynomials over \(\mathbf {Z}/(m)\). Next we introduce the definitions of primitive polynomials and primitive sequences over \(\mathbf {Z}/(m)\).
Let \(f\left( x\right) \) be a monic polynomial of degree n over \(\mathbf {Z} /(m)\). If \(\gcd (f\left( 0\right) ,m)=1\), then there exists a positive integer T such that \(x^{T}-1\) is divisible by f(x) in \(\mathbf {Z}/(m)[x]\). The minimum of such T is called the period of \(f\left( x\right) \) over \( \mathbf {Z}/(m)\) and denoted by \(per\left( f\left( x\right) ,m\right) \). For the case that m is a prime power, say \(m=p^{e}\), it is known that \( per\left( f\left( x\right) ,p^{e}\right) \le p^{e-1}(p^{n}-1)\), see [18]. If \(per\left( f\left( x\right) ,p^{e}\right) =p^{e-1}(p^{n}-1)\), then \(f\left( x\right) \) is called a primitive polynomial of degree n over \(\mathbf {Z}/(p^{e})\). A sequence \(\underline{a}\) over \(\mathbf {Z} /(p^{e})\) is called a primitive sequence of order n if \(\underline{a}\) is generated by a primitive polynomial of degree n over \(\mathbf {Z}/(p^{e})\) and \(\left[ \underline{a}\right] _{\text {mod}\, p}\) is not an all-zero sequence. A primitive sequence \(\underline{a}\) of order n over \(\mathbf {Z}/(p^{e})\) is (strictly) periodic and the period \(per(\underline{a})\) is equal to \(p^{e-1}(p^{n}-1)\), see [18]. For the case of a general integer m, assume \(m=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{r}^{e_{r}}\) is the canonical factorization of m. A monic polynomial \(f\left( x\right) \) of degree n over \(\mathbf {Z}/(m)\) is called a primitive polynomial if for every \(k\in \left\{ 1,2,\ldots ,r\right\} \), \(f\left( x\right) \) is a primitive polynomial of degree n over \(\mathbf {Z}/(p_{k}^{e_{k}})\). A sequence \(\underline{a}\) over \(\mathbf {Z}/(m)\) is called a primitive sequence of order n if \(\underline{a}\) is generated by a primitive polynomial of degree n over \(\mathbf {Z}/(m)\) and \(\left[ \underline{a}\right] _{\text {mod}\, p_{k}}\) is not an all-zero sequence for every \(k\in \left\{ 1,2,\ldots ,r\right\} \), that is, \(\left[ \underline{a}\right] _{\text {mod}\, p_{k}^{e_{k}}}\) is a primitive sequence of order n over \(\mathbf {Z}/(p_{k}^{e_{k}})\). It can be seen that the period of a primitive polynomial of degree n over \(\mathbf {Z}/(m)\) and that of a primitive sequence of order n over \(\mathbf {Z}/(m)\) are both equal to
For convenience, the set of primitive sequences generated by a primitive polynomial f(x) over \(\mathbf {Z}/(m)\) is generally denoted by \(G^{\prime }(f(x),m)\).
2.2 Exponential Sums over Integer Residue Rings
Let m be a positive integer greater than 1, and let \(e_{m}\left( \cdot \right) \) be the canonical additive character over \(\mathbf {Z}/(m)\) given by \(e_{m}(a)=e^{2\pi ia/m}\), where a is an integer. For an integer c, it is well-known that
The following Lemma 1 is cited from [5, Theorem 1].
Lemma 1
([5, Theorem 1]) Let \(D\ge 1\), \(m\ge 2\) and \(g=\gcd (m,D)\). Then we have
where \(\ln (m)\) is the natural logarithm of m.
The following Lemma 2 is an improvement of a well-known result of Korobov [14, Theorem 13].
Lemma 2
Let \(\underline{a}\) be a primitive sequence of order n over \(\mathbf {Z}/(m)\) with period T. Then for any integer h we have
In particular,
Moreover, we have
for any integer \(k\ge 0\) and \(0<L<T\).
Proof
Since the inequality (2) has been proved in [14, Theorem 13], we only prove the inequality (3). We start from the identity
which is valid since the sum over j is 1 for \(k\le t\le k+L-1\) and 0 for \(k+L\le t\le k+T-1\). Rearranging terms, we get
and so we obtain
Then by the inequality (2) we get
We note that
and so an application of Lemma 3 yields
where the last inequality follows from the fact that \(g=\gcd (L,T)<T/2\). Combining the inequalities (4) and (5), we get the desired result.
3 Main Results
Throughout the rest of this paper, we always assume that \(M>1\) is a given square-free odd integer and \(M=p_{1}p_{2}\cdots p_{r}\) is the canonical factorization of M. Let \(d>1\) be a divisor of M. Suppose \(d=p_{i_{1}}\cdots p_{i_{k}}\) with \(1\le i_{1}<\cdots <i_{k}\le r\). Let us denote by \(\lambda _{n}(d)\) the period of primitive sequences of order n over \(\mathbf {Z}/(d)\), that is,
The main results of this paper are stated in the following Theorems 1 and 2.
Theorem 1
Let \(\underline{a}\) be a primitive sequence of order n over \(\mathbf {Z}/(M)\) with period \(T=\lambda _{n}\left( M\right) \), and let \(\underline{b}=\left[ \underline{a}\right] _{\text {mod}\, 2}\). For \(s\in \left\{ 0,1\right\} \), denote by \(N\left( \underline{b}^{T},s\right) \) the number of t, \(0\le t\le T-1\), with \(b\left( t\right) =s\). Then we have
if M is an odd prime number; and
if M has at least two different prime divisors.
Theorem 2
Let \(\underline{a}\) be a primitive sequence of order n over \(\mathbf {Z}/(M)\) with period \(T=\lambda _{n}\left( M\right) \). Let \( \underline{b}=\left[ \underline{a}\right] _{\text {mod}\, 2}\) and \(\underline{b} ^{L}=\left( b\left( k\right) ,b\left( k+1\right) ,\ldots ,b\left( k+L-1\right) \right) \) a segment of \(\underline{b}\) with length \(L=\mu T\), where \(0\le k\le T-1\) and \(0<\mu <1\). For \(s\in \left\{ 0,1\right\} \), denote by \(N\left( \underline{b}^{L},s\right) \) the number of t, \(0\le t\le L-1\), with \(b\left( k+t\right) =s\). Then we have
where
The rest of this section is divided into three subsections. Subsects. 3.1 and 3.2 are mainly devoted to the proof of Theorem 1 and the proof of Theorem 2, respectively. Finally, as an example, an application of Theorems 1 and 2 to the modulo 2 reductions of primitive sequences over \(\mathbf {Z}/(2^{32}-1)\) is given in Subsect. 3.3.
3.1 The Proof of Theorem 1
We first collect two well-known results on trigonometric functions in Lemma 3. The first result can be found in [19] and the second result can be found in [11, p. 447].
Lemma 3
Let \(\tan x=\sin x/\cos x\), \(\sec x=1/\cos x\) and \(\csc x=1/\sin x\) be the tangent function, the secant function and the cosecant function, respectively. Then we have:
(1) \(\int \sec xdx=\ln \left| \sec x+\tan x\right| +C\), where C is the constant of integration;
(2) \(\csc (\pi /m)\le m/3\) if \(m\ge 6\).
Lemma 4
For an odd integer \(m>1\), we have
Proof
It can be directly verified that the lemma holds for \(m=3\) or 5. Therefore, we assume that \(m\ge 7\). Since it is clear that
we obtain
Note that the convexity of the function \(\sec x\) implies that
Thus by taking \(\theta =\frac{\pi }{m}\) we get
By combining (8) and (9), we obtain
By applying \(\csc (\pi /m)\le m/3\) to the right-hand side of (10) we get
This completes the proof.
Now we start to prove Theorem 1.
Proof
(Proof of Theorem 1). If M is an odd prime number, then (6) immediately follows from the theory of m-sequences over finite fields (see, for example, [11]). Next we will prove the equality (7). Note that
and so it suffices to show (7) holds for the case that \(s=0\), that is,
Since
we get
We note that
Applying (13) to (12) we obtain
Note that given a divisor \(d>1\) of M, \(\left[ h\underline{a}\right] _{\text {mod}\, d}\) is a primitive sequence over \(\mathbf {Z}/(d)\) with period \(\lambda _{n}\left( d\right) \) for every integer h coprime with d, and so it follows from Lemma 2 that
Combining (14) and (15) yields
and so (11) follows from (16) and Lemma 4.
Generally speaking, if n is sufficiently large, then the right-hand side of (6) is sufficiently small, and so the value of \(N\left( \underline{b}^{T},s\right) /T\) is very close to that of \(\left( M+1-2s\right) /2M\) (for more details, see Table 1). In fact, we can give a more theoretical result on the asymptotic property of \(N\left( \underline{b} ^{T},s\right) /T\) as \(n\rightarrow \infty \).
Corollary 1
Let \(\underline{a}\) be a primitive sequence of order n over \(\mathbf {Z}/(M)\) with period \(T=\lambda _{n}\left( M\right) \), and let \(\underline{b}=\left[ \underline{a}\right] _{\text {mod}\, 2}\). Then for \(s\in \left\{ 0,1\right\} \) we have
To prove Corollary 1, we first introduce a result of Bugeaud, Corvaja and Zannier [1].
Lemma 5
([1, Theorem 1]) If \(a<b\) are two integers greater than 1 which are multiplicatively independent (that is, the only integer solution \(\left( x,y\right) \) of the equation \(a^{x}b^{y}=1\) is \(\left( x,y\right) =\left( 0,0\right) )\), then for any given real number \(\varepsilon >0\), there exists an integer \(N_{\varepsilon }\) such that
Remark 1
Note that a and b are multiplicatively independent if \(\gcd \left( a,b\right) =1\).
Proof
(Proof of Corollary 1). Since Corollary 1 is obvious true for the case that M is an odd prime number, we assume that \(M=p_{1}p_{2}\cdots p_{r}\) is the canonical factorization of M with \(r\ge 2\) and \(3\le p_{1}<p_{2}<\cdots <p_{r}\). Note that the inequality
holds for any divisor d of M, and so by Theorem 1 we get
Therefore to prove Corollary 1, it suffices to show that
that is
Given a real number \(\varepsilon >0\). For any \(1\le u<v\le r\), it follows from Lemma 5 and Remark 1 that there exists an integer \(N_{\varepsilon }^{(u,v)}\) such that
Set
where \(\left\lceil a\right\rceil \) denotes the smallest integer greater than or equal to a. Then it is clear that
Let \(2\le k\le r\) and \(1\le i_{1}<\cdots <i_{k}\le r\). It follows from (18) that if \(n>N_{\varepsilon }\), then
Consequently, we have
Note that \(k\ge 2\) and \(p_{i_{j}}\ge p_{1}\) for \(1\le j\le k\), and so (19) yields
Hence it can be seen that
Then choosing \(\varepsilon <r^{-2}\), we get
Since r, M and \(p_{1}\) are all fixed integers with \(p_{1}\ge 3\), we get
and so (17) follows from (20).
3.2 The Proof of Theorem 2
Proof
(Proof of Theorem 2). Since
it suffices to show that
First, it is clear that
Then proceed as in the proof of Theorem 1, we can get
Note that given a divisor \(d>1\) of M, \(\left[ h\underline{a}\right] _{ \text {mod}\, d}\) is a primitive sequence over \(\mathbf {Z}/(d)\) with period \( \lambda _{n}\left( d\right) \) for every integer h coprime with d, and so by Lemma 2 we have
where \(\left\lfloor a\right\rfloor \) denotes the largest integer smaller than or equal to a. Combining (22) and (23) we get
and so (21) follows from (24) and Lemma 4.
Similar to Corollary 1, we can give the asymptotic property of \(\frac{N\left( \underline{b}^{L},s\right) }{L}\) as \(n\rightarrow \infty \).
Corollary 2
Let \(\underline{a}\) be a primitive sequence of order n over \(\mathbf {Z}/(M)\) with period \(T=\lambda _{n}\left( M\right) \). Let \( \underline{b}=\left[ \underline{a}\right] _{\text {mod}\, 2}\) and \(\underline{b} ^{L}=\left( b\left( k\right) ,b\left( k+1\right) ,\ldots ,b\left( k+L-1\right) \right) \) a segment of \(\underline{b}\) with length \(L=\mu T\), where \(0\le k\le T-1\) and \(0<\mu <1\). Then for \(s\in \left\{ 0,1\right\} \) we have
Proof
Since
and
hold for any divisor d of M with \(d>1\), it follows from Theorem 2 that
where
is a constant only depended on M and \(\mu \). Therefore to prove Corollary 2, it suffices to show that
that is
Proceed as in the proof of Corollary 1 (but substitute \( \prod _{j=1}^{k}p_{i_{j}}^{n/2}\) by \(n\prod _{j=1}^{k}p_{i_{j}}^{n/2}\)), finally we can get
Since r, M and \(p_{1}\) are all fixed integers with \(p_{1}\ge 3\), we get
and so (25) follows from (26).
3.3 An Example: Element Distribution of Modulo 2 Reductions of Primitive Sequences over \(\mathbf {Z}/(2^{32}-1)\)
Let \(\underline{a}\) be a primitive sequence of order n over \(\mathbf {Z} /(2^{32}-1)\) with period \(T=\lambda _{n}\left( 2^{32}-1\right) \). Let \( \underline{b}=\left[ \underline{a}\right] _{\text {mod}\, 2}\) and \(\underline{b} ^{L}=\left( b\left( k\right) ,b\left( k+1\right) ,\ldots ,b\left( k+L-1\right) \right) \) a segment of \(\underline{b}\) with length \(L=\mu T\), where \(0\le k<T\) and \(0<\mu \le 1\). Then it follows from Theorems 1 and 2 that
where
with
and
The values of \(\varLambda _{n}\left( \mu \right) \) are calculated and listed in Table 1 for \(1\le n\le 10\) and \(\mu \in \left\{ 1,1/2,1/4,1/8\right\} \). It can be seen from Table 1 that the estimate of (27) is nontrivial if \(\left( 1\right) \) \(\mu =1\) and \(n\ge 2\); or \(\left( 2\right) \) \(0<\mu <1\) and \(n\ge 3\). Moreover for any \(\mu \in \left\{ 1,1/2,1/4,1/8\right\} \), the value of \(\varLambda _{n}\left( \mu \right) \) is very close to 0 if \(n\ge 3\), which is consistent with the results of Corollarys 1 and 2.
4 Conclusions
In this paper, the distribution properties of modulo 2 reductions of primitive sequences modulo square-free odd integers are studied. Let M be a square-free odd integer, n a positive integer, and \(\underline{a}\) a primitive sequence of order n over \(\mathbf {Z}/(M)\) with period T. For \( s\in \left\{ 0,1\right\} \) and \(0<\mu \le 1\), denote by \(f_{s}\) the proportion of occurrences of s within a segment of the binary sequence \( \left[ \underline{a}\right] _{\text {mod}\, 2 }\), the modulo 2 reduction of \( \underline{a}\), of length \(\mu T\). Then it is shown that the difference of \( f_{s}\) from the average value \(\frac{M+1-2s}{2M}\) tends to 0 as \( n\rightarrow \infty \). Note that \(\frac{M+1}{2M}\) differs from \(\frac{M-1}{2M }\) by \(\frac{1}{M}\). This implies that there exists a small imbalance between 0 and 1 occurring in the binary sequence \(\left[ \underline{a} \right] _{\text {mod}\, 2}\), and the bias of \(f_{0}\) and \(f_{1}\) is about \(\frac{1}{M} \). To provide a good resistance against the distinguishing attacks, such imbalance should be taken into full consideration in the design of stream ciphers based on \(\left[ \underline{a}\right] _{\text {mod}\, 2}\). A simple method is to introduce the exclusive or operation. A bitwise exclusive or of several phase-shifts of \(\left[ \underline{a}\right] _{\text {mod}\, 2}\) will has smaller bias than \(\left[ \underline{a}\right] _{\text {mod}\, 2}\). Therefore, by introducing a moderate amount of exclusive or operations, the imbalance of 0, 1 will be reduced to a small enough extent. In the future we will be interested in other pseudorandom properties of \(\left[ \underline{a}\right] _{\text {mod}\, 2}\), such as the linear complexity of \(\left[ \underline{a}\right] _{\text {mod}\, 2}\).
References
Bugeaud, Y., Corvaja, P., Zannier, U.: An upper bound for the G.C.D. of \(a^{n}-1\) and \(b^{n}-1\). Math. Z. 243, 79–84 (2003)
Bylkov, D.N., Kamlovskii, O.V.: Occurrence indices of elements in linear recurrence sequences over primary residue rings. Probl. Inf. Transm. 44, 161–168 (2008)
Chan, A.H., Games, R.A.: On the linear span of binary sequences obtained from finite geometries. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 405–417. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_29
Chen, H.J., Qi, W.F.: On the distinctness of maximal length sequences over \(\mathbf{Z}/(pq)\) modulo 2. Finite Fields Appl. 15(1), 23–39 (2009)
Cochrane, T.: On a trigonometric inequality of Vinogradov. J. Number Theory 27(1), 9–16 (1987)
Dai, Z.D., Beth, T., Gollmann, D.: Lower bounds for the linear complexity of sequences over residue rings. In: Damgård, I.B. (ed.) EUROCRYPT 1990. LNCS, vol. 473, pp. 189–195. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-46877-3_16
Dai, Z.D.: Binary sequences derived from ML-sequences over rings I: periods and minimal polynomials. J. Cryptol. 5(3), 193–207 (1992)
Fan, S.Q., Han, W.B.: Random properties of the highest level sequences of primitive sequences over \(\mathbf{Z}/(2^{e})\). IEEE Trans. Inf. Theory 49(6), 1553–1557 (2003)
Hu, Z., Wang, L.: Injectivity of compressing maps on the set of primitive sequences modulo square-free odd integers. Cryptogr. Commun. 7(4), 347–361 (2015)
Huang, M.Q., Dai, Z.D.: Projective maps of linear recurring sequences with maximal \(p\)-adic periods. Fibonacci Q. 30(2), 139–143 (1992)
Lidl, R., Niederreiter, H.: Finite Fields. Encyclopedia of Mathematics and Its Applications, vol. 20. Cambridge University Press, Cambridge (1997)
Kamlovskii, O.V.: Frequency characteristics of linear recurrences over Galois rings. Matematicheskii Sbornik 200, 31–52 (2009)
Klapper, A., Goresky, M.: Feedback shift registers, 2-adic span, and combiners with memory. J. Crypt. 10(2), 111–147 (1997)
Korobov, N.M.: Exponential Sums and Their Applications. Kluwer, Dordrecht (1992)
Kuzmin, A.S., Nechaev, A.A.: Linear recurring sequences over Galois ring. Russ. Math. Surv. 48(1), 171–172 (1993)
Qi, W.F., Yang, J.H., Zhou, J.J.: ML-sequences over rings Z/(2e): I. Constructions of nondegenerative ML-sequences II. Injectivness of compression mappings of new classes. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 315–326. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-49649-1_25
Tian, T., Qi, W.F.: Injectivity of compressing maps on primitive sequences over \(\mathbf{Z}/(p^{e})\). IEEE Trans. Inf. Theory 53(8), 2966–2970 (2007)
Ward, M.: The arithmetical theory of linear recurring series. Trans. Am. Math. Soc. 35(3), 600–628 (1933)
Wikipedia, Trigonometric functions, Wikipedia website (2018). https://en.wikipedia.org/wiki/Trigonometric_functions#Calculus
Zhu, X.Y., Qi, W.F.: Compression mappings on primitive sequences over \(\mathbf{Z}/(p^{e})\). IEEE Trans. Inf. Theory 50(10), 2442–2448 (2004)
Zhu, X.Y., Qi, W.F.: Further result of compressing maps on primitive sequences modulo odd prime powers. IEEE Trans. Inf. Theory 53(8), 2985–2990 (2007)
Zhu, X.Y., Qi, W.F.: On the distinctness of modular reduction of maximal length modulo odd prime numbers. Math. Comput. 77(263), 1623–1637 (2008)
Zheng, Q.X., Qi, W.F.: Distribution properties of compressing sequences derived from primitive sequences over \(\mathbf{Z}/(p^{e})\). IEEE Trans. Inf. Theory 56(1), 555–563 (2010)
Zheng, Q.X., Qi, W.F.: A new result on the distinctness of primitive sequences over \(\mathbf{Z}/(pq)\) modulo \(2\). Finite Fields Appl. 17(3), 254–274 (2011)
Zheng, Q.X., Qi, W.F., Tian, T.: On the distinctness of binary sequences derived from primitive sequences modulo square-free odd integers. IEEE Trans. Inf. Theory 59(1), 680–690 (2013)
Zheng, Q.X., Qi, W.F.: Further results on the distinctness of binary sequences derived from primitive sequences modulo square-free odd integers. IEEE Trans. Inf. Theory 59(6), 4013–4019 (2013)
Zheng, Q.X., Qi, W.F., Tian, T.: On the distinctness of modular reduction of primitive sequences over \(\mathbf{Z}/(2^{32}-1)\). Des. Codes Crypt. 70(3), 359–368 (2014)
ETSI/SAGE Specification: Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3. Document 4: Design and Evaluation Report; Version: 2.0; Date: 9th Sep. 2011. Tech. rep., ETSI 2011. http://www.gsmworld.com/our-work/programmes-and-initiatives/fraud-and-security/gsm_security_algorithms.htm
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Zheng, QX., Lin, D., Qi, WF. (2019). Distribution Properties of Binary Sequences Derived from Primitive Sequences Modulo Square-free Odd Integers . In: Guo, F., Huang, X., Yung, M. (eds) Information Security and Cryptology. Inscrypt 2018. Lecture Notes in Computer Science(), vol 11449. Springer, Cham. https://doi.org/10.1007/978-3-030-14234-6_30
Download citation
DOI: https://doi.org/10.1007/978-3-030-14234-6_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-14233-9
Online ISBN: 978-3-030-14234-6
eBook Packages: Computer ScienceComputer Science (R0)