On the pseudorandom properties of d-ary generalized two-prime Sidelnikov sequences

Abstract

Let p and q be two distinct odd primes and let d=(p-1,q-1). In this paper, we construct d-ary generalized two-prime Sidelnikov sequences and study the autocorrelation values and linear complexity.

Keywords

Two-prime sequence / Sidelnikov sequence / character sum / autocorrelation value / linear complexity

1 Introduction

Sequences with good pseudorandom properties play an important role in communication and cryptography, and many of them with these properties sequences are constructed based on multiplicative features in finite fields [18, 19]. For example, the well-known Legendre sequence is based on the quadratic feature of finite field For example, the famous Legendre sequence is constructed based on the quadratic identity of the finite field storage (p is prime) and has been shown to have high linear complexity and good pseudorandomness [3, 5].

Another well-known sequence is the Sidelnikov sequence which has been shown to have good periodic autocorrelation values [8, 9]. Based on these two constructions, more good pseudo-random sequences such as double prime sequences have been proposed and shown to have good autocorrelation values [2]. Secondly, for Legendre-Sidelnikov sequence which is based on the Legendre sequence with period p and the Sidelnikov sequence with period q-1, Su and Winterhof [16] gives the periodic autocorrelation values of the Legendre–Sidelnikov sequence and the correlation values of upper bounds for the acyclic autocorrelation function. While literature [15] and [17] studied the linear complexity of the sequence, respectively, giving the upper and lower bounds on the linear complexity under different conditions. Correlational studies are also available in [13, 14, 20].

Brandstiitter et al. [1] defined the dual prime Sidelnikov sequence by combining the properties of the cut circle sequence with those of the Sidelnikov sequence.

Specifically, let p and q be two distinct odd prime numbers and g be a common primitive root of modulo p and modulo q. Let d=(p-1,q-1), t=(p-1)(q-1)/d, , Q_0=Q\cup \left\{0\right\} and p=\{p,2p,\dots ,(q-1)p\}. Then store on the biserial Sidelnikov sequence (s_n) with period t is defined as

(1.1)s_n=\{\begin{array}{l}0,(g^n+1)\text{mod}pq\in Q_0,\\ 1,(g^n+1)\text{mod}pq\in P,\\ {\displaystyle \frac{1-(\frac{g^n+1}{p})(\frac{g^n+1}{q})}{2}},(g^n+1,pq)=1,\end{array}

where (\frac{\cdot }{p}) and (\frac{\cdot }{q}) denote the Legendre symbols of mod p and mod q, respectively. Literature [1] gives the autocorrelation function for the sequence (0.1).

Literature [21] improves the upper bound estimate of the autocorrelation value of this sequence for d = 2. Literature [7] introduces an improved binary biserial Sidelnikov sequence:

(1.2)s_n=\{\begin{array}{l}1,g^n+1\equiv 0(\text{mod}pq),\\ {\displaystyle \frac{1-(\frac{g^n+1}{q})}{2}},(g^n+1)\text{mod}pq\in P,\\ {\displaystyle \frac{1-(\frac{g^n+1}{p})}{2}},(g^n+1)\text{mod}pq\in Q,\\ {\displaystyle \frac{1-(\frac{g^n+1}{p})(\frac{g^n+1}{q})}{2}},(g^n+1,pq)=1,\end{array}

and proves that the sequence is equilibrium in addition to calculating its autocorrelation value. Related works can also be found in [4, 6, 11].

In this paper, we will construct a d\text{-element} bi-prime Sidelnikov sequence based on multiplicative features and study its autocorrelation value with linear complexity set integer d⩾2, prime p\equiv 1 (\mathrm{m}\mathrm{o}\mathrm{d}d), w is a d\text{-dimensional} unit root, and g is the original root of mod p defined by

{\chi }_p(g)=w,{\chi }_p(0)=0.

And for n\in {\mathbb{F}}_p^{\ast }, let n\equiv g^j mod (d), 0⩽j⩽p-2,

{\chi }_p(n)={\chi }_p(g^j)=w^j.

From the above, we can obtain a d\text{-order} multiplicative identity {\chi }_p for mod p.

Let the odd prime p\equiv 1 (\mathrm{m}\mathrm{o}\mathrm{d}d). Similarly, we can obtain a d\text{-order} multiplicative identity {\chi }_p(g^j)=w^j and {\chi }_p(0)=0. The methodological identity {\chi }_q satisfying {\chi }_p(g^j)=w^j, {\chi }_p(0)=0 and t=\frac{(p-1)(q-1)}{d} defines a d\text{-element} generalized dual prime of period t Sidelnikov sequence as follows:

(1.3)s_n=\{\begin{array}{ll}1,& g^n+1\equiv 0(\mathrm{mod}pq),\\ {\log }_{\omega }{\chi }_q(g^n+1),& (g^n+1)\mathrm{mod}pq\in P,\\ {\log }_{\omega }{\chi }_p(g^n+1),& (g^n+1)\mathrm{mod}pq\in Q,\\ {\log }_{\omega }({\chi }_p(g^n+1){\chi }_q(g^n+1)),& (g^n+1,pq)=1,\end{array}

where {\log }_{\omega }(\cdot )is the discrete logarithm on {\mathcal{Z}}_d with w as the base.

In this paper, the autocorrelation value and linear complexity of this sequence are investigated in Section 2 and Section 3, respectively, using the properties of the characteristic sum. The findings show that the sequence has a small autocorrelation value and a high linear complexity, and thus has potential applications in coding and cryptography.

2 Autocorrelation value

For a d\text{-element} sequence (s_n) with period N(s_n)(0⩽n⩽N-1), the periodic autocorrelation function is defined as

\text{AC}(s_n,l)=\sum _{n=0}^{N-1}{\omega }^{s_n-s_{n+l}},

where 1⩽l⩽N-1,\omega is the d\mathrm{t}\mathrm{h} unit root. If (s_n) is a pseudo-random sequence, then |\text{AC}(s_n,l)| is an infinite small plant about N.

This section will study the autocorrelation value of the d\text{-measure} sequence defined in (1.3). When l\equiv 0(\mathrm{mod}p-1)\text{or}l\equiv 0(\mathrm{mod}q-1), the exact value of \text{AC}(s_n,l) can be obtained.

Theorem 2.1　 Let (s_n) be defined as in (1.3). When l\equiv 0(\mathrm{mod}p-1), if p\equiv q\equiv 3\text{(mod}4), then

(2.1)\begin{array}{rl}\text{AC}(s_n,l)=& \left(\frac{p-1}{d}-1+\omega \right){\chi }_q^{-1}(-g^l+1)+\left(\frac{p-1}{d}-1+{\omega }^{-1}\right){\chi }_q(-g^{-l}+1)\\ & +\frac{p-1}{d}(-{\chi }_q^{-1}(g^l)-1).\end{array}

When p\not\equiv q\text{(mod 4),} then

(2.2)\text{AC}(s_n,l)=\frac{p-1}{d}({\chi }_q^{-1}(-g^l+1)+{\chi }_q(-g^{-l}+1)-{\chi }_q^{-1}(g^l)-1).

When l\equiv 0(\mathrm{mod}q-1), if p\equiv q\equiv 3\text{(mod}4), then

(2.3)\begin{array}{rl}\text{AC}(s_n,l)=& \left(\frac{q-1}{d}-1+\omega \right){\chi }_p^{-1}(-g^l+1)+\left(\frac{q-1}{d}-1+{\omega }^{-1}\right){\chi }_p(-g^{-l}+1)\\ & +\frac{q-1}{d}(-{\chi }_p^{-1}(g^l)-1).\end{array}

When p\not\equiv q\text{(mod 4),} then

(2.4)\text{AC}(s_n,l)=\frac{q-1}{d}({\chi }_p^{-1}(-g^l+1)+{\chi }_p(-g^{-l}+1)-{\chi }_p^{-1}(g^l)-1).

Proof　Due to the symmetry of p and q, we prove only the case of l\equiv 0(\mathrm{mod}q-1), i.e., (2.1) and (2.2).

It is easy to prove that g^n+1\equiv 0(\mathrm{mod}pq) if and only if p\equiv q\equiv 3(\mathrm{mod}4), and when g^n+1\equiv 0(\mathrm{mod}pq), there must be g^{n+l}+1\in P. Futher more, when g^n+1\in P, there is g^{n+l}+1\in P\cup \{0\}. By (1.3), we have

(2.5){\omega }^{s_n-s_{n+l}}=\{\begin{array}{ll}\omega {\chi }_q^{-1}(-g^l+1),& g^n+1\equiv 0\text{(mod}pq),g^{n+l}+1\in P,\\ {\omega }^{-1}{\chi }_q(-g^{-l}+1),& g^n+1\in P,g^{n+l}+1\equiv 0\text{(mod}pq),\\ {\chi }_q(g^n+1){\chi }_q^{-1}(g^{n+l}+1),& g^n+1\in P,g^{n+l}+1\in P,\\ {\chi }_q^{-1}(-g^l+1),& g^n+1\in Q,g^{n+l}+1\in {\mathbb{Z}}_{pq}^{\ast },\\ {\chi }_q(-g^{-l}+1),& g^n+1\in {\mathbb{Z}}_{pq}^{\ast },g^{n+l}+1\in Q,\\ {\chi }_q(g^n+1){\chi }_q^{-1}(g^{n+l}+1),& g^n+1\in {\mathbb{Z}}_{pq}^{\ast },g^{n+l}+1\in {\mathbb{Z}}_{pq}^{\ast }.\end{array}

The following two scenarios are used to calculate \text{AC}(s_n,l).

Case l　Assume that p\equiv q\equiv 3(\mathrm{mod}4). From (2.5), we have

\begin{array}{rl}\text{AC}(s_n,l)& =\sum _{n=0}^{t-1}{\omega }^{s_n-s_{n+l}}\\ & =\omega {\chi }_q^{-1}(-g^l+1)+{\omega }^{-1}{\chi }_q(-g^{-l}+1)\\ & +\sum _{\begin{array}{c}n=0\\ g^n+1\in Q\\ g^{n+l}+1\in {\mathbb{Z}}_{pq}^{\ast }\end{array}}^{\begin{array}{c}t-1\end{array}}{\chi }_q^{-1}(-g^l+1)+\sum _{\begin{array}{c}n=0\\ g^n+1\in {\mathbb{Z}}_{pq}^{\ast }\\ g^{n+l}+1\in Q\end{array}}^{\begin{array}{c}t-1\end{array}}{\chi }_q(-g^{-l}+1)\\ & +\sum _{\begin{array}{c}n=0\\ g^n+1\in P\\ g^{n+l}+1\in P\end{array}}^{\begin{array}{c}t-1\end{array}}{\chi }_q(g^n+1){\chi }_q^{-1}(g^{n+l}+1)+\sum _{\begin{array}{c}n=0\\ g^n+1\in {\mathbb{Z}}_{pq}^{\ast }\\ g^{n+l}+1\in {\mathbb{Z}}_{pq}^{\ast }\end{array}}^{\begin{array}{c}t-1\end{array}}{\chi }_q(g^n+1){\chi }_q^{-1}(g^{n+l}+1)\\ & =\omega {\chi }_q^{-1}(-g^l+1)+{\omega }^{-1}{\chi }_q(-g^{-l}+1)\\ & +\sum _{\begin{array}{c}n=0\\ g^n+1\in Q\end{array}}^{t-1}{\chi }_q^{-1}(-g^l+1)+\sum _{\begin{array}{c}n=0\\ g^{n+l}+1\in Q\end{array}}^{t-1}{\chi }_q(-g^{-l}+1)\\ & +\sum _{\begin{array}{c}n=0\\ g^n+1\in P\end{array}}^{t-1}{\chi }_q(g^n+1){\chi }_q^{-1}(g^{n+l}+1)+\sum _{\begin{array}{c}n=0\\ g^n+1\in {\mathbb{Z}}_{pq}^{\ast }\end{array}}^{t-1}{\chi }_q(g^n+1){\chi }_q^{-1}(g^{n+l}+1)\\ & =\omega {\chi }_q^{-1}(-g^l+1)+{\omega }^{-1}{\chi }_q(-g^{-l}+1)\end{array}

(2.6)\begin{array}{rl}& +\frac{p-1-d}{d}{\chi }_q^{-1}(-g^l+1)+\frac{p-1-d}{d}{\chi }_q(-g^{-l}+1)\\ & +\sum _{n=0}^{t-1}{\chi }_q(g^n+1){\chi }_q^{-1}(g^{n+l}+1).\end{array}

From the properties of the identity and the residual system, we have

(2.7)\begin{array}{rl}& \sum _{n=0}^{t-1}{\chi }_q(g^n+1){\chi }_q^{-1}(g^{n+l}+1)\\ & =\sum _{n_1=0}^{\frac{p-1}{d}-1}\sum _{n_2=0}^{q-2}{\chi }_q(g^{n_1(q-1)+n_2\frac{p-1}{d}}+1){\chi }_q^{-1}(g^{n_1(q-1)+n_2\frac{p-1}{d}+l}+1)\\ & =\frac{p-1}{d}\sum _{n_2=0}^{q-2}{\chi }_q(g^{n_2}+1){\chi }_q^{-1}(g^{n_2+l}+1)=\frac{p-1}{d}\sum _{n_3=1}^{q-1}{\chi }_q(n_3+1){\chi }_q^{-1}(g^l{n}_3+1)\\ & =\frac{p-1}{d}\sum _{n_4=2}^{q-1}{\chi }_q(n_4){\chi }_q^{-1}(g^l{n}_4+1-g^l)=\frac{p-1}{d}(\sum _{n_4=1}^{q-1}{\chi }_q^{-1}(g^l+(1-g^l)n_4^{-1})-1)\\ & =\frac{p-1}{d}(\sum _{n_4=1}^{q-1}{\chi }_q^{-1}(g^l+n_4)-1)=\frac{p-1}{d}(-{\chi }_q^{-1}(g^l)-1).\end{array}

Thus, combining (2.6) with (2.7), we have

(2.8)\begin{array}{rl}\text{AC}(s_n,l)=& \left(\frac{p-1}{d}-1+\omega \right){\chi }_q^{-1}(-g^l+1)+\left(\frac{p-1}{d}-1+{\omega }^{-1}\right){\chi }_q(-g^{-l}+1)\\ & +\frac{p-1}{d}(-{\chi }_q^{-1}(g^l)-1).\end{array}

Case 2　Assume that p\not\equiv q\text{(mod}4). From (2.5) and (2.7), we have

\begin{array}{rl}\text{AC}(s_n,l)& =\sum _{n=0}^{t-1}{\omega }^{s_n-s_{n+l}}\\ & =\sum _{\begin{array}{c}n=0\\ g^n+1\in Q\\ g^{n+l}+1\in {\mathbb{Z}}_{pq}^{\ast }\end{array}}^{\begin{array}{c}t-1\end{array}}{\chi }_q^{-1}(-g^l+1)+\sum _{\begin{array}{c}n=0\\ g^n+1\in {\mathbb{Z}}_{pq}^{\ast }\\ g^{n+l}+1\in Q\end{array}}^{\begin{array}{c}t-1\end{array}}{\chi }_q(-g^{-l}+1)\\ & +\sum _{\begin{array}{c}n=0\\ g^n+1\in P\\ g^{n+l}+1\in P\end{array}}^{\begin{array}{c}t-1\end{array}}{\chi }_q(g^n+1){\chi }_q^{-1}(g^{n+l}+1)+\sum _{\begin{array}{c}n=0\\ g^n+1\in {\mathbb{Z}}_{pq}^{\ast }\\ g^{n+l}+1\in {\mathbb{Z}}_{pq}^{\ast }\end{array}}^{\begin{array}{c}t-1\end{array}}{\chi }_q(g^n+1){\chi }_q^{-1}(g^{n+l}+1)\\ & =\sum _{\stackrel{n=0}{g^n+1\in Q}}^{t-1}{\chi }_q^{-1}(-g^l+1)+\sum _{\stackrel{n=0}{g^{n+l}+1\in Q}}^{t-1}{\chi }_q(-g^{-l}+1)\end{array}

(2.9)\begin{array}{rl}& +\sum _{\stackrel{n=0}{g^n+1\in P}}^{t-1}{\chi }_q(g^n+1){\chi }_q^{-1}(g^{n+l}+1)+\sum _{\stackrel{n=0}{g^n+1\in {\mathbb{Z}}_{pq}^{\ast }}}^{t-1}{\chi }_q(g^n+1){\chi }_q^{-1}(g^{n+l}+1)\\ & =\frac{p-1}{d}{\chi }_q^{-1}(-g^l+1)+\frac{p-1}{d}{\chi }_q(-g^{-l}+1)+\sum _{n=0}^{t-1}{\chi }_q(g^n+1){\chi }_q^{-1}(g^{n+l}+1)\\ & =\frac{p-1}{d}({\chi }_q^{-1}(-g^l+1)+{\chi }_q(-g^{-l}+1)-{\chi }_q^{-1}(g^l)-1).\end{array}

Theorem 2.1 is proved.□

The |\text{AC}(s_n,l)| can be given when l\not\equiv 0(\mathrm{mod}p-1)\text{and}l\not\equiv 0(\mathrm{mod}q-1), and we need the following upper bound estimate for the sum of characteristics.

Lemma 2.1 [10, Lemma 2]　 Let p be a prime number and \chi be a non-principal characteristic of dth-order modulo p. Let f(x)\in {\mathbb{F}}_p[x], and cannot be tabulated as {\mathbb{F}}_p on any polynomial of constant multiples of the dth curtain. Then for any a\in \mathbb{Z}, there is

|\sum _{n\in {\mathbb{F}}_p}\chi (f(n))e(\frac{an}{p})|⩽s{p}^{\frac{1}{2}},

where e(y)={\text{e}}^{2\pi \text{i}y}, s is the number of different roots of the polynomial f on {\overline{\mathbb{F}}}_p.

Theorem 2.2　 Let (s_n) be as defined in (1.3). When l\not\equiv 0(\mathrm{mod}p-1) with l\not\equiv 0(\mathrm{mod}q-1),

(2.10)\text{AC}(s_n,l)\ll p^{\frac{1}{2}}{q}^{\frac{1}{2}}+p+q.

Proof　From (1.3), we have

(2.11)\begin{array}{rl}\text{AC}(s_n,l)& =\sum _{n=0}^{t-1}{\omega }^{s_n-s_{n+l}}\\ & =\sum _{n=0}^{t-1}{\chi }_p(g^n+1){\chi }_p^{-1}(g^{n+l}+1){\chi }_q(g^n+1){\chi }_q^{-1}(g^{n+l}+1)+O(p+q)\\ & =\sum _{n_1=0}^{p-2}\sum _{n_2=0}^{\frac{q-1}{d}-1}{\chi }_p(g^{n_1\frac{q-1}{d}+n_2(p-1)}+1){\chi }_p^{-1}(g^{n_1\frac{q-1}{d}+n_2(p-1)+l}+1)\\ & \times {\chi }_q(g^{n_1\frac{q-1}{d}+n_2(p-1)}+1){\chi }_q^{-1}(g^{n_1\frac{q-1}{d}+n_2(p-1)+l}+1)+O(p+q)\\ & =\sum _{n_1=0}^{p-2}\sum _{n_2=0}^{\frac{q-1}{d}-1}{\chi }_p(g^{n_1\frac{q-1}{d}}+1){\chi }_p^{-1}(g^{n_1\frac{q-1}{d}+l}+1)\\ & \times {\chi }_q(g^{n_1\frac{q-1}{d}+n_2(p-1)}+1){\chi }_q^{-1}(g^{n_1\frac{q-1}{d}+n_2(p-1)+l}+1)+O(p+q).\end{array}

When n_2 is taken from 0 to \frac{q-1}{d}-1, g^{n_2(p-1)} is taken over the d\mathrm{t}\mathrm{h} residue of modulo q. Thus,

(2.12)\begin{array}{rl}\text{AC}(s_n,l)& =\sum _{n_1=0}^{p-2}{\chi }_p(g^{n_1\frac{q-1}{d}}+1){\chi }_p^{-1}(g^{n_1\frac{q-1}{d}+l}+1)\\ & \times \sum _{n_2=1}^{q-1}{\chi }_q(g^{n_1\frac{q-1}{d}}{n}_2+1){\chi }_q^{-1}(g^{n_1\frac{q-1}{d}}{n}_2+1)\cdot \frac{1}{d}\sum _{k=0}^{d-1}{\chi }_q^k(n_2)+O(p+q)\\ & =\frac{1}{d}\sum _{k=0}^{d-1}\sum _{n_1=0}^{p-2}{\chi }_p(g^{n_1\frac{q-1}{d}}+1){\chi }_p^{-1}(g^{n_1\frac{q-1}{d}}+1){\chi }_q^{-k}(g^{n_1\frac{q-1}{d}})\\ & \times \sum _{n_2=1}^{q-1}{\chi }_q(n_2+1){\chi }_q^{-1}(g^l{n}_2+1){\chi }_q^k(n_2)+O(p+q).\end{array}

Note that {\chi }_p(g)={\chi }_q(g)=\omega , therefore,

{\chi }_q^{-k}\left(g^{n_1\frac{q-1}{d}}\right)={\chi }_p^{-k}\left(g^{n_1\frac{q-1}{d}}\right).

Thus, we have

(2.13)\begin{array}{rl}\text{AC}(s_n,l)& =\frac{1}{d}\sum _{k=0}^{d-1}\sum _{n_1=0}^{p-2}{\chi }_p(g^{n_1\frac{q-1}{d}}+1){\chi }_p^{-1}(g^{n_1\frac{q-1}{d}}+1){\chi }_p^{-k}(g^{n_1\frac{q-1}{d}})\\ & \times \sum _{n_2=1}^{q-1}{\chi }_q(n_2+1){\chi }_q^{-1}(g^l{n}_2+1){\chi }_q^k(n_2)+O(p+q)\\ & =\frac{1}{d}\sum _{k=0}^{d-1}\sum _{n_1=1}^{p-1}{\chi }_p(n_1+1){\chi }_p^{-1}(g^l{n}_1+1){\chi }_p^{-k}(n_1)\\ & \times \sum _{n_2=1}^{q-1}{\chi }_q(n_2+1){\chi }_q^{-1}(g^l{n}_2+1){\chi }_q^k(n_2)+O(p+q)\\ & =\frac{1}{d}\sum _{k=0}^{d-1}\sum _{n_1=1}^{p-1}{\chi }_p((n_1+1)(g^l{n}_1+1{)}^{d-1}{n}_1^{d-k})\\ & \times \sum _{n_2=1}^{q-1}{\chi }_q((n_2+1)(g^l{n}_2+1{)}^{d-1}{n}_2^k)+O(p+q).\end{array}

Again, from Lemma 2.1, we have

(2.14)\text{AC}(s_n,l)\ll p^{\frac{1}{2}}{q}^{\frac{1}{2}}+p+q.

Theorem 2.2 is proved.□

3 Linear complexity

The linear complexity L(s_n,N) of a sequence of d elements (s_n) on {\mathbb{Z}}_d is the linear relationship for every integer N⩾2, such that

s_{n+L}=c_{L-1}{s}_{n+L-1}+\cdots +c_0{s}_n,0⩽n⩽N-L-1.

The smallest positive integer L that holds for both the coding and cryptography fields requires that the linear complexity L(s_n,N) must not be too small.

In this section, we study the linear complexity of the d\text{-element} sequence defined in (1.3) and give a lower bound estimate, which can be obtained as the following theorem.

Theorem 3.1　 Let (s_n) be as defined in (1.3). Then for any 0⩽N⩽t,

(3.1)L(s_n,N)\gg min\left\{p,q,\sqrt{\frac{N}{p^{\frac{1}{2}}{q}^{\frac{1}{2}}\log (pq)}}\right\}.

Proof　Note that L=L(s_n,N). It is useful to set Note c_L=-1, and set

0=c_L{s}_{n+L}+c_{L-1}{s}_{n+L-1}+\cdots +c_0{s}_n,0⩽n⩽N-L-1.

Thus, from (1.3), we have

(3.2)\begin{array}{rl}N-L& =\sum _{n=0}^{N-L-1}{\omega }^{c_L{s}_{n+L}+c_{L-1}{s}_{n+L-1}+\cdots +c_0{s}_n}\\ & =\sum _{n=0}^{N-L-1}{\chi }_p((g^{n+L}+1{)}^{c_L}\cdots (g^n+1{)}^{c_0}){\chi }_q((g^{n+L}+1{)}^{c_L}\cdots (g^n+1{)}^{c_0})\\ & \begin{array}{l}=\sum _{n=0}^{t-1}{\chi }_p((g^{n+L}+1{)}^{c_L}\cdots (g^n+1{)}^{c_0}){\chi }_q((g^{n+L}+1{)}^{c_L}\cdots (g^n+1{)}^{c_0})\end{array}\\ & \times \frac{1}{t}\sum _{m=0}^{N-L-1}\sum _{u=0}^{t-1}e(\frac{u(n-m)}{t})\\ & =\frac{1}{t}\sum _{u=0}^{t-1}\sum _{m=0}^{N-L-1}e(-\frac{um}{t})\sum _{n=0}^{t-1}{\chi }_p((g^{n+L}+1{)}^{c_L}\cdots (g^n+1{)}^{c_0})\\ & \times {\chi }_q((g^{n+L}+1{)}^{c_L}\cdots (g^n+1{)}^{c_0})e\left(\frac{un}{t}\right)\\ & :=\frac{1}{t}\sum _{u=0}^{t-1}\sum _{m=0}^{N-L-1}e(-\frac{um}{t})\cdot \mathrm{\Gamma }.\end{array}

Let the integer {\delta }_1,{\delta }_2 satisfy {\delta }_1\cdot \frac{q-1}{d}\equiv 1(\mathrm{mod}p-1),{\delta }_2\cdot \frac{p-1}{d}\equiv 1(\mathrm{mod}q-1). By the nature of the residual system, we have

\begin{array}{rl}\text{T}& \begin{array}{l}=\sum _{n=0}^{t-1}{\chi }_p((g^{n+L}+1{)}^{c_L}\cdots (g^n+1{)}^{c_0}){\chi }_q((g^{n+L}+1{)}^{c_L}\cdots (g^n+1{)}^{c_0})e\left(\frac{un}{t}\right)\end{array}\\ & =\sum _{n_1=0}^{p-2}\sum _{n_2=0}^{\frac{q-1}{d}-1}{\chi }_p((g^{n_1\frac{q-1}{d}+n_2(p-1)+L}+1{)}^{c_L}\cdots (g^{n_1\frac{q-1}{d}+n_2(p-1)}+1{)}^{c_0})\\ & \times {\chi }_q((g^{n_1\frac{q-1}{d}+n_2(p-1)+L}+1{)}^{c_L}\cdots (g^{n_1\frac{q-1}{d}+n_2(p-1)}+1{)}^{c_0})e(\frac{u(n_1\frac{q-1}{d}+n_2(p-1))}{t})\\ & =\sum _{n_1=0}^{p-2}\sum _{n_2=0}^{\frac{q-1}{d}-1}{\chi }_p((g^{n_1\frac{q-1}{d}+L}+1{)}^{c_L}\cdots (g^{n_1\frac{q-1}{d}}+1{)}^{c_0})e(\frac{u{\delta }_1{n}_1\frac{q-1}{d}}{p-1})\\ & \times {\chi }_q((g^{n_1\frac{q-1}{d}+n_2(p-1)+L}+1{)}^{c_L}\cdots (g^{n_1\frac{q-1}{d}+n_2(p-1)}+1{)}^{c_0})e(\frac{u{\delta }_2{\text{ind}}_g{g}^{n_2(p-1)}}{q-1})\\ & =\sum _{n_1=0}^{p-2}{\chi }_p((g^{n_1\frac{q-1}{d}+L}+1{)}^{c_L}\cdots (g^{n_1\frac{q-1}{d}}+1{)}^{c_0})e(\frac{u{\delta }_1{n}_1\frac{q-1}{d}}{p-1})\\ & \times \sum _{n_2=1}^{q-1}{\chi }_q((g^{n_1\frac{q-1}{d}+L}{n}_2+1{)}^{c_L}\cdots (g^{n_1\frac{q-1}{d}}{n}_2+1{)}^{c_0})e(\frac{u{\delta }_2{\text{ind}}_g{n}_2}{q-1})\frac{1}{d}\sum _{k=0}^{d-1}{\chi }_q^k(n_2)\\ & =\frac{1}{d}\sum _{k=0}^{d-1}\sum _{n_1=0}^{p-2}{\chi }_p((g^{n_1\frac{q-1}{d}+L}+1{)}^{c_L}\cdots (g^{n_1\frac{q-1}{d}}+1{)}^{c_0})e(\frac{u{\delta }_1{n}_1\frac{q-1}{d}}{p-1})e(-\frac{u{\delta }_2{n}_1\frac{q-1}{d}}{q-1})\\ & \times {\chi }_q^{-k}(g^{n_1\frac{q-1}{d}})\sum _{n_2=1}^{q-1}{\chi }_q((g^L{n}_2+1{)}^{c_L}\cdots (n_2+1{)}^{c_0})e\left(\frac{u{\delta }_2{\text{ind}}_g{n}_2}{q-1}\right){\chi }_q^k(n_2).\end{array}

Notice that

{\chi }_q^{-k}(g^{n_1\frac{q-1}{d}})={\chi }_p^{-k}(g^{n_1\frac{q-1}{d}}),e(-\frac{u{\delta }_2{n}_1\frac{q-1}{d}}{q-1})=e(-\frac{u{\delta }_1{n}_1\frac{q-1}{d}}{p-1}).

Set

{\chi }_{q,\ast }(n)=\{\begin{array}{ll}e\left({\displaystyle \frac{{\text{ind}}_g}{q-1}}\right),& (n,q)=1,\\ 0,& (n,q)>1,\end{array}

and {\chi }_q={\chi }_{q,\ast }^{\mathrm{\Delta }},\mathrm{\Delta }=\frac{q-1}{d}m,(m,q-1)=1. By Lemma 2.1, we have

\begin{array}{rl}\text{T}& =\frac{1}{d}\sum _{k=0}^{d-1}\sum _{n_1=1}^{p-1}{\chi }_p((g^L{n}_1+1{)}^{c_L}\cdots (n_1+1{)}^{c_0}){\chi }_p^{-k}(n_1)\\ & \times \sum _{n_2=1}^{q-1}{\chi }_q((g^L{n}_2+1{)}^{c_L}\cdots (n_2+1{)}^{c_0}){\chi }_{q,\ast }^{u{\delta }_2}(n_2){\chi }_q^k(n_2)\\ & =\frac{1}{d}\sum _{k=0}^{d-1}\sum _{n_1=1}^{p-1}{\chi }_p((g^L{n}_1+1{)}^{c_L}\cdots (n_1+1{)}^{c_0}{n}_1^{d-k})\end{array}

(3.3)\begin{array}{rl}& \times \sum _{n_2=1}^{q-1}{\chi }_{q,\ast }((g^L{n}_2+1{)}^{c_L\mathrm{\Delta }}\cdots (n_2+1{)}^{c_0\mathrm{\Delta }}{n}_2^{u{\delta }_2}{n}_2^{k\mathrm{\Delta }})\\ & \ll L^2{p}^{\frac{1}{2}}{q}^{\frac{1}{2}}.\end{array}

By combining (3.2) and (3.3), N-L\ll \frac{1}{t}\sum _{u=0}^{t-1}\left|\sum _{m=0}^{N-L-1}e(-\frac{um}{t})\right|\cdot \mathrm{\Gamma }\ll L^2{p}^{\frac{1}{2}}{q}^{\frac{1}{2}}\log (pq). Thus, Theorem 3.1 is completely proved.□

References

[1] Brandstätter N, Pirsic G. Correlation of the two-prime Sidelnikov sequence. Des Codes Cryptogr 2011; 59(1/3): 59–68

[2] Brandstätter N, Winterhof A. Some notes on the two-prime generator of order 2. IEEE Trans Inform Theory 2005; 51(10): 3654–3657

[3] Ding C. Pattern distributions of Legendre sequences. IEEE Trans Inform Theory 1998; 44(4): 1693–1698

[4] Ding C, Helleseth T. On cyclotomic generator of order r. Inform Process Lett 1998; 66(1): 21–25

[5] Ding C, Helleseth W. On the linear complexity of Legendre sequences. IEEE Trans Inform Theory 1998; 44(3): 1276–1278

[6] Green D H, Green P R. Polyphase power-residue sequences. R Soc Lond Proc Ser A, Math Phys Eng Sci 2003; 459(2032): 817–827

[7] Ke P H, Ye Z F, Zhou Z C, Shen J. Autocorrelation of the modified binary two-prime Sidelnikov sequence. Internat J Found Comput Sci 2017; 28(4): 391–409

[8] Kim Y, Kim D, Song H. New M-ary sequence families with low correlation from the array structure of Sidelnikov sequences. IEEE Trans Inform Theory 2015; 61(1): 655–670

[9] Kim Y, Song M, Kim D. . Properties and crosscorrelation of decimated Sidelnikov sequences. IEICE Transactions on Fundamentals of Electronics Communications & Computer Sciences 2014; E97.A(12): 2562–2566

[10] Mauduit C, Sárközy A. On finite pseudorandom binary sequences I. Measure of pseudorandomness, the Legendre symbol. Acta Arith 1997; 82(4): 365–377

[11] Mauduit C, Sárközy A. On finite pseudorandom sequences of k symbols. Indag Math (N S) 2002; 13(1): 89–101

[12] SchmidtW M. Equations over Finite Fields, An Elementary Approach. Lecture Notes in Mathematics, Vol 536. Berlin: Springer-Verlag, 1976

[13] Sidel'nikov V M. Some k-valued pseudo-random sequences and nearly equidistant codes. Problems Inform Transmission 1969; 5(1): 12–16

[14] SuM. On the d-ary generalized Legendre-Sidelnikov sequence. In: Sequences and Their Applications SETA 2012. Lecture Notes in Comput Sci, Vol 7280. Heidelberg: Springer-Verlag, 2012, 233–244

[15] Su M. On the linear complexity of Legendre-Sidelnikov sequences. Des Codes Cryptogr 2015; 74(3): 703–717

[16] Su M, Winterhof A. Autocorrelation of Legendre-Sidelnikov sequences. IEEE Trans Inform Theory 2010; 56(4): 1714–1718

[17] Su M. Correlation measure of order k and linear complexity profile of Legendre-Sidelnikov sequence. IEICE Transactions on Fundamentals of Electronics Communications & Computer Sciences 2012; E95.A(11): 1851–1854

[18] TopuzogluAWinterhofA. Pseudorandom sequences. In: Topics in Geometry, Coding Theory and Cryptography. Algebr Appl, Vol 6. Dordrecht: Springer-Verlag, 2007, 135–166

[19] WinterhofA. Linear complexity and related complexity measures. In: Selected Topics in Information and Coding Theory. Ser Coding Theory Cryptol, Vol 7. Hackensack, NJ: World Sci Publ, 2010, 3–40

[20] Yan T J, Liu H D, Sun Y H. Autocorrelation of modified Legendre-Sidelnikov sequence. IEICE Transactions on Fundamentals of Electronics Communications & Computer Sciences 2015; E98.A(2): 771–775

[21] Yue Z, Gao J T, Xie J. Autocorrelation of the two-prime sidelnikov sequence. Journal of Electronics & Information Technology 2013; 35(11): 2602–2607

RIGHTS & PERMISSIONS

Higher Education Press 2023