Keywords

1 Introduction

With the explosion of multimedia data, more and more data owners would outsource their personal multimedia data on the cloud [17, 18]. Secure message transmission plays an main role in the information-based society. Pseudo-random sequences used for stream ciphers are required to have the properties of unpredictability. Linear complexity is one of the main components that indicates this feature. The linear complexity of a sequence is defined as the length of the shortest linear feedback shift register that can generate the sequence [14]. Due to the Berlekamp-Massey algorithm, it is reasonable to suggest that the linear complexity of a good sequence should be at least a half of the period. In the recent years, the sequence derived from the Euler quotients modulo an odd prime power, which is an extension of the Fermat quotients, are a hot spot and much of the sequences possess sound linear complexity, see [1,2,3,4,5,6,7,8,9, 11, 12, 15, 20] and the references therein. While for the study of the sequences derived from the Euler quotients modulo an even number are very rare. For the binary threshold sequence, the linear complexity is derived from Carmichael quotients with even numbers modulus in [16]. In [19], Zhang et al. promoted a class of binary sequences derived from Euler quotients with period \(2p^2\) and p is an odd prime and determined the linear complexity and trace function representation of the sequences.

For an odd prime p and integer \(u\ge 0\) with \(\gcd (u,2p)=1\), the Euler quotient \(q_{2p}(u)\) modulo 2p can be defined as unique integer with

$$\begin{aligned} q_{2p}(u)\equiv \frac{u^{p-1}-1}{2p} \pmod {2p},\quad 0\le q_{2p}(u) \le 2p-1, \end{aligned}$$

and \(q_{2p}(u)=0\) for \(u\in R = \mathbb {Z}_{2p^2} \setminus \mathbb {Z}^*_{2p^2}\), where \(\mathbb {Z}_{2p^2}\) denote by the ring of the all the integers modulo \(2p^2\) and \(\mathbb {Z}^*_{2p^2}\) of the multiplicative group of all the unit in \(\mathbb {Z}_{2p^2}\) respectively.

The binary threshold sequence \((e_u)\) defined in [19] as

$$\begin{aligned} {} e_u= {\left\{ \begin{array}{ll} 0 ,&{} \text {if} \quad 0\le \frac{q_{2p}(u)}{2p}< \frac{1}{2} ,\\ 1 ,&{} \text {if} \quad \frac{1}{2} \le \frac{q_{2p}(u)}{2p}< 1, \end{array}\right. }\qquad u\ge 0. \end{aligned}$$
(1)

Motivated by the previous work in [15, 19], we extend the binary threshold sequence to r-ary sequence as the following

$$\begin{aligned} {} f_u= {\left\{ \begin{array}{ll} 0 ,&{} \text {if} \quad 0\le \frac{q_{2p}(u)}{2} \le s ,\\ 1 ,&{} \text {if} \quad s+1 \le \frac{q_{2p}(u)}{2} \le 2s,\\ \vdots &{} \vdots \\ r-1 ,&{} \text {if} \quad (r-1)s+1 \le \frac{q_{2p}(u)}{2} \le p-1 , \end{array}\right. } \end{aligned}$$
(2)

where r is a prime, \(r|(p-1) \) and \(s=(p-1)/r\). In fact, if \(r=2\), then \((f_u)\) is the binary threshold sequence defined in (1). We note that \((f_u)\) is \(2p^2\)-periodical since \(q_{2p}(u)\) is a \(2p^2\)-periodic sequence modulo 2p by the fact

$$\begin{aligned} q_{2p}(u+2kp)\equiv \ q_{2p}(u)+k(p-1)u^{-1}\pmod {2p},\; \gcd (u,2p)=1. \end{aligned}$$

The linear complexity is considered as a primary quality measure for periodic sequences and play an important role in applications of sequences in cryptography. The main aims of this article is to determine the linear complexity of \((f_u)\). We recall that the linear complexity \(L((s_u))\) of a T-periodic sequence \((s_u)\) with terms in finite field \(\mathbb {F}_q\) with q elements is the least order of L of a linear recurrence relation over \(\mathbb {F}_q\)

$$\begin{aligned} s_{u+L}+c_{L-1}s_{u+L-1}+\dots +c_1s_{u+1}+c_0s_{u}=0 \quad \text {for} \; u \ge 0 \end{aligned}$$

which is satisfied by \((s_u)\) and where \(c_0\ne 0\), \(c_1,\dots ,c_{L-1}\in \mathbb {F}_q \). The polynomial

$$\begin{aligned} M(x)=x^L+c_{L-1}x^{L-1}+\dots +c_0\in \mathbb {F}_q[x] \end{aligned}$$

is called the minimal polynomial of \((s_u)\). The generating polynomial of \((s_u)\) is defined by

$$\begin{aligned} S(x)=s_0+s_1x+s_2x^2+\dots +s_{T-1}x^{T-1}\in \mathbb {F}_q[x]. \end{aligned}$$

It is easy to show that

$$\begin{aligned} M(x)=(x^T-1)/\gcd (x^T-1, S(x)), \end{aligned}$$

hence

$$\begin{aligned} L((s_u))=T-\deg (\gcd (x^T-1,S(x))), \end{aligned}$$
(3)

which is the degree of minimal polynomial, see [13] for more details.

2 Preliminary

The main aims of this article are to determine the linear complexity of \((f_u)\) under the assumption \(r^{p-1}\not \equiv 1 \pmod {p^2}\). To achieve our goals we need to describe \((f_u)\) in an equivalent way. For any subset \(D \subset \mathbb {Z}_N\), define \(aD=\{ a \cdot b \pmod N : b\in N \}\) for any integer a.

If \(\mathrm {gcd}(u,2p)=1\), it is easy to verify that

$$\begin{aligned} q_{2p}(uv)\equiv q_{2p}(u)+q_{2p}(v)\ (\mathrm {mod}\ 2p),\ \mathrm {gcd}(uv,2p)=1. \end{aligned}$$
(4)

By [19], note that \(q_{2p}(u)\) is always even since it can be rewritten as

$$q_{2p}(u)\equiv \frac{(u^{\frac{p-1}{2}}-1)(u^{\frac{p-1}{2}}+1)}{2p}\ (\mathrm {mod}\ 2p),$$

and two numbers \(u^{\frac{p-1}{2}}\pm 1\) are even. Thus we define

$$\begin{aligned} D_l=\{u:q_{2p}(u)=2l \pmod {2p} \;\; \text {for} \;\; u\in \mathbb {Z}_{2p^2}^ *\} \end{aligned}$$

for \(l=0,1,\dots ,p-1\). We always assume that g be a fixed primitive root modulo \(2p^{2}\) such that \(q_{2p}(g)=2\), we declare such g exists. Otherwise, if \(q_{2p}(g)=2a\ne 2\). It is easy to prove that \(\gcd (a,p)=1\). By (4) we get \(q_{2p}(g^{a^{-1}})=2\), where \(a^{-1}\) is the inverse of a modulo p. Furtherly, we have

$$q_{2p}(g^{a^{-1}+kp})\equiv 2~(\mathrm {mod}~2p)$$

for all \(0\le k<p-1\), then we have

$$D_0=\{g^{kp} \pmod {2p^2} : 0\le k\le p-2 \}$$

is a subgroup of the multiplicative group \(\mathbb {Z}_{2p^2}^ *\) and for all \(0 \le l \le p-1\), there exists \(0 \le l_0 \le p-1\), such that

$$D_l=g^{l_0}D_0=\{g^{l_0}\cdot a\ (\mathrm {mod}\ 2p)\ :\ a\in D_0\}$$

and each \(D_l\) has the cardinality \(\#D_l=p-1\) and \(\mathbb {Z}_{2p^2}^*=\bigcup \limits ^{p-1}_{l=0}D_l\).

Now the sequence \((f_u)\) can be written equivalently as

$$\begin{aligned} {} f_u= {\left\{ \begin{array}{ll} 0 ,&{} \text {if} \quad u\in D_0\cup D_1\cup \dots \cup D_s\cup R,\\ 1 ,&{} \text {if} \quad u\in D_{s+1}\cup D_{s+2}\cup \dots \cup D_{2s},\\ \vdots &{} \vdots \\ r-1 ,&{} \text {if} \quad u\in D_{(r-1)s+1}\cup D_{(r-1)s+2}\cup \dots \cup D_{p-1}. \end{array}\right. } \end{aligned}$$
(5)

Below, we are devoted to determining the linear complexity of the sequences. The rest of paper is organized as follows. In Sect. 3, we present some Auxiliary lemmas. In Sect. 4, We prove the main results of the paper and give some examples. Finally we conclude the paper.

3 Auxiliary Lemmas

Let \(\mathbb {F}_r =\{0,1,\dots ,r-1\}\) be the finite field of order r and \(\mathbb {\overline{F}}_r\) be the algebraic closure of \(\mathbb {F}_r\). Below we always let \(\beta \in \mathbb {\overline{F}}_r\) be a primitive \(2p^2\)-th root of unity and the subscripts of D are calculated modulo p.

The following two lemmas are given in [19].

Lemma 1

For any \(0 \le l <p\), if \(a\pmod {2p^2} \in D_{l'}\), for some \(0 \le l'<p\) we have

$$ D_l \pmod p= \{1,2,\ldots , p-1 \} ~and~ aD_l= D_{l+l'},$$

where \(D_l \pmod p=\{ a \pmod p : a \in D_l\}\)

Lemma 2

Let n be a positive integer. Then

$$\begin{aligned} \{u\pmod {p^n} : u \in \mathbb {Z}_{2p^n}^*\}=\mathbb {Z}_{p^n}^*. \end{aligned}$$

From now we define

$$\begin{aligned} D_l(x)=\sum \limits _{u\in D_l}{x^u}\in \mathbb {F}_r [x], \;\; \text {for}\;\; 0\le l \le p-1. \end{aligned}$$

From the definition of \((f_u)\) we obtain that the generating polynomial of \((f_u)\) is

$$\begin{aligned} E(x)=\sum \limits _{u=0}^{2p^2-1}{f_ux^u}=\sum \limits _{j=1}^{r-1}{j}\sum \limits _{i=js+1}^{(j+1)s}{D_i(x)}\in \mathbb {F}_r [x]. \end{aligned}$$

Lemma 3

Let \(\beta \in \mathbb {\overline{F}}_r\) be a primitive \(2p^2\)-th root of unity. Then we have

  1. (1)

    \(D_l(\beta ^v)=D_{l+l'}(\beta )\),

  2. (2)

    \(D_l(\beta ^u)=D_l(\beta ^v)\) and \(E(\beta ^u)=E(\beta ^v)\),

where \(u , v\in D_l\) for some \(0 \le l \le p-1\).

Proof

From Lemma 1 and the definitions of \(D_l(x)\) and E(x), we can obtain the results.

Lemma 4

Let \(\beta \in \mathbb {\overline{F}}_r\) be a primitive \(2p^2\)-th root of unity.

  1. (1)

    For all \(v\in \mathbb {Z}_{2p^2}^*\cup 2\mathbb {Z}_{p^2}^*\), we have

    $$\begin{aligned} \sum \limits _{l=0}^{p-1}D_l(\beta ^v)=0. \end{aligned}$$
  2. (2)

    For \(0\le l< p\), we have

    $$\begin{aligned} D_l(\beta ^{kp})= {\left\{ \begin{array}{ll} 0 ,&{} \text {if} \quad k\equiv 0 \pmod {p},\\ -1 ,&{} \text {if} \quad k\equiv 0 \pmod {2}, (k,p)=1. \end{array}\right. } \end{aligned}$$

Proof

(1) From the definition of \(\beta \), we have

$$\begin{aligned} 0=\beta ^{2p^2}-1= & {} (\beta -1) \sum \limits _{j\in \mathbb {Z}_{2p^2}} \beta ^j= (\beta ^2-1)\sum \limits _{j\in 2\mathbb {Z}_{p^2}} \beta ^j \\= & {} (\beta ^p-1)\sum \limits _{j\in p\mathbb {Z}_{2p}} \beta ^j=(\beta ^{2p}-1) \sum \limits _{j\in 2p\mathbb {Z}_{p}} \beta ^j \\= & {} (\beta ^{p^2}-1)(\beta ^{p^2}+1) \end{aligned}$$

(1) of the Lemma is proved by the fact that

$$\begin{aligned} \mathbb {Z}_{2p^2}= & {} \mathbb {Z}_{2p^2}^* \cup 2 \mathbb {Z}_{p^2}^* \cup p \mathbb {Z}_{2p}\\= & {} \mathbb {Z}_{2p^2}^* \cup 2 \mathbb {Z}_{p^2}^* \cup 2p \mathbb {Z}_{p} \cup p\mathbb {Z}_{2p}^* \cup \{p^2\}. \end{aligned}$$

(2) If \(k\equiv 0 \pmod {p}\), then \(k=0\) or p. It can be easy to see that

$$D_l(\beta ^{kp})=D_l(\beta ^{0p})=D_l(1)=\sum _{u\in D_l}1^u=p-1\equiv 0 \pmod r $$

if \(k=0\), and

$$D_l(\beta ^{kp})=D_l(\beta ^{p^2})=D_l(-1)=\sum _{u\in D_l}(-1)^u=0$$

if \(k=p\) from the proof of (1).

If \(k\equiv 0 \pmod {2}\) with \((k,p)=1\), we have \(\beta ^2\) is a primitive \(p^2\)-th root of unity, so

$$\{k:\ k \;\mathrm {is\; an\; even,\; with}\;\; (k,p)=1\},$$

then by Lemma 1 and (1) of this lemma, we have

$$\begin{aligned} D_l(\beta ^{kp})= & {} \beta ^{2p}+\beta ^{4p}+\ldots +\beta ^{2(p-1)}\\= & {} \frac{\beta ^{2p}-\beta ^{2p^2}}{1-\beta ^{2p}}\\= & {} \frac{\beta ^{2p}-1}{1-\beta ^{2p}}\\= & {} -1\pmod {r}.\\ \end{aligned}$$

   \(\square \)

Lemma 5

If \( r^{p-1} \not \equiv 1\pmod {p^2}\), then

$$D_l(\beta ^u)\not = 0$$

for all \(0\le l\le p-1\) and all \(u\in \mathbb {Z}_{2p^2}^* \cup 2\mathbb {Z}_{p^2}^*\).

Proof

Denote by \(d:=ord_{2p^2}(r)\) the multiplicative order of r modulo \(2p^2\). Thus, \(d\mid p(p-1)\) and \(d\ge p\) and \(r^i\not \equiv r^j\pmod {2p^2} \) for \(0\le i<j\le p-1\). Suppose that \(r\in D_{l_0\pmod {p}}\), using Lemma 1 we have \(r^i \pmod {2p^2} \in D_{l_0}\) for all \(0\le i\le p-1\) and

$$D_0\cup rD_0(=D_{l_0})\cup \dots \cup r^{p-1}D_0=D_0\cup D_1\cup \dots \cup D_{p-1}=\mathbb {Z}_{2p^2}^*.$$

Meanwhile the minimal polynomial of \(\beta ^a\) over \(\mathbb {F}_r\) is given by

$$M(x)=\prod \limits _{k=0}^{d-1}(x-\beta ^{ar^k}).$$

Consequently, if there are some \(0\le l'\le p-1\) and some \(a\in D_k\) such that \(D_{l'}(\beta ^a)=0\), then \(D_{l'}(\beta ^{ar^t})=0\) for \(0 \le t \le d-1\).

Note that

$$ D_k\cup rD_k\cup \dots \cup r^{p-1}D_k=\mathbb {Z}_{2p^2}^* $$

then by Lemma 3(2) we have

$$D_{l'}(\beta ^u)=0 \; \text {for all}\; u \in \mathbb {Z}_{2p^2}^*.$$

Furthermore, Lemma 3(1) leads to that \(D_{l'}(\beta ^a)=D_{l'+1}(\beta ^{a'})\) for some \({a'}\in D_{k-1}\), we also have \(D_{l'+1}(\beta ^u)=0\) for all \(u \in \mathbb {Z}_{2p^2}^*\). Seeking this process continually, we will get that

$$\begin{aligned} D_l(\beta ^u)=0 \; \text {for all} \; 0\le l \le p-1 \; \text {and}\; u\in \mathbb {Z}_{2p^2}^*. \end{aligned}$$

By Lemma 2 and notice the fact that \(\beta ^{p^2}=-1\), we have that for any \(l=0,1,\dots ,p-1\), the polynomial \(D_l(x) \pmod {x^{p^2}+1}\) has at least \(p(p-1)\) many roots.

However, in the set \(\{u: 0\le u \le p^2-1, \gcd (u,p)=1\}\) there are only \(p-1\) many elements, which appear in \(D_l(x) \pmod {x^{p^2}+1}\) as exponents for all \(0\le l \le p-1\), larger than \(p^2-p\). (Notice that \(x^{p^2-p}\) never appears.) So by the pigeonhole principle, there exists at least one \(0 \le l' \le p-1 \), such that \(\deg (D_{l'}(x) \pmod {x^{p^2}+1} ) < p^2-p.\) This is a contradiction to the fact that the polynomial \(D_{l'}(x)\) has at least \(p^2-p\) many different roots. Therefore, for all \(u \in \mathbb {Z}_{2p^2}^*\), we always have \(D_l(\beta ^u)\not =0.\)

For the case of \(u\in 2\mathbb {Z}_{p^2},\) by Lemmas 1 and 2, with the fact that \(d=ord_{p^2}(r)\) and \((\beta ^2)^{p^2}=1\), following the above approach, we can get desired result. Thus we have finish the proof of the lemma.   \(\square \)

4 Linear Complexity

In this section, we determine the linear complexity of r-ary sequence \((f_u)\) defined in (2) under the assumption \(r^{p-1} \not \equiv 1 \pmod {p^2}\).

Theorem 1

Let \((f_u)\) be the \(2p^2\)-periodic r-ary sequence defined as in (2). If \(r^{p-1} \not \equiv 1 \pmod {p^2} \), then the linear complexity \(L((f_u))\) and the minimal polynomial M(x) of \((f_u)\) are given by

$$\begin{aligned} L((f_u))=2p^2-2p \end{aligned}$$

and

$$\begin{aligned} M(x)=(x^{2p^2}-1)/(x^{2p}-1) \end{aligned}$$

respectively.

Proof

We prove this theorem by the following two facts.

  1. (1)

    \(E(\beta ^u)\not =0\) if \(u \in \mathbb {Z}_{2p^2}^* \cup 2\mathbb {Z}_{p^2}^*.\)

    Suppose that there is some \(a\in D_k\) for some \(0 \le k \le p-1\) such that \(E(\beta ^a)=0\), similar to the proof of Lemma 5, we have \(E(\beta ^u)=0\) holds for all \(u \in \mathbb {Z}_{2p^2}^*.\) Then we get \(E(\beta ^{a'})=E(\beta )=0\) where \(a'\in D_l\). It follows from Lemma 3 and after simple calculation that

    $$ E(\beta ^{a'})=\sum \limits _{j=0}^{r-1}(j-1)\sum \limits _{i=jl+1}^{(j+1)l}D_i(\beta )-D_0(\beta )+D_l(\beta ).$$

    Then by Lemma 4, we have

    $$0=-D_l(\beta )=E(\beta )-E(\beta ^{a'})=\sum \limits _{j=0}^{p-1}D_j(\beta )-D_l(\beta ).$$

    This contradiction with Lemma 5. Then for all \(u \in \mathbb {Z}_{2p^2}^*\), we always have \(E(\beta ^u)\not =0.\)

    For all \(u \in 2\mathbb {Z}_{p^2}^*\), the results follows directly from Lemma 3.4 in [10].

  2. (2)

    \(E(\beta ^u)=0\) if \(u=kp, k\in \mathbb {Z}_{2p}.\) Note that each \(D_l\) has \(p-1\) many elements for \(0\le l < p\) and \(D_l\pmod {p}=\{1,2,\dots ,p-1\}\). Then we have two cases.

    If \(k=0,p, \) by Lemma 4 we have

$$ E(\beta ^{kp})=E(\pm 1)=\sum \limits _{j=1}^{r-1}j\sum \limits _{i=jl+1}^{(j+1)l}D_i(\pm 1) \equiv 0,$$

and if \(u=kp\) for \(k\in \mathbb {Z}_{2p}^* \cup 2\mathbb {Z}_{p}^*\), we have

$$\begin{aligned} E(\beta ^u)= & {} \sum \limits _{j=1}^{r-1}j\sum \limits _{i=jl+1}^{(j+1)l}D_i(\beta ^{kp})\\= & {} \sum \limits _{j=1}^{r-1}j\sum \limits _{i=jl+1}^{(j+1)l}(\beta ^{pk}+\beta ^{2pk}+\dots +\beta ^{(p-1)pk}) \\= & {} (\beta ^{pk}+\beta ^{2pk}+\dots +\beta ^{(p-1)pk}) \sum \limits _{j=1}^{r-1}j\sum \limits _{i=jl+1}^{(j+1)l}1\\= & {} l (\beta ^{pk}+\beta ^{2pk}+\dots +\beta ^{(p-1)pk}) \sum \limits _{j=1}^{r-1}j \\\equiv & {} 0 \pmod {r}. \end{aligned}$$

Putting every thing together, we have \(E(\beta ^u)=0\) if and only if \(u\in \{kp: k\in \mathbb {Z}_{2p} \}\), that is, the number of common roots of E(x) and \(x^{2p^2}-1\) is 2p, so the linear complexity of \((f_u)\) is \(2p^2-2p\) by (3). Meanwhile, it is easy to see that the minimial polynomial M(x) of \((f_u)\) satisfies \(M(x)=(x^{2p^2}-1)/(x^{2p}-1).\)    \(\square \)

Now we provide some examples of \(2p^2\)-periodic r-ary sequences \((f_u)\) to show the applicability of Theorem 1:

p

r

\(L((f_u))\)

\(L((f_u))\) satisfying

7

3

84

\(2p^2-2p\)

11

5

220

\(2p^2-2p\)

13

3

312

\(2p^2-2p\)

19

3

684

\(2p^2-2p\)

23

11

1012

\(2p^2-2p\)

29

7

1624

\(2p^2-2p\)

31

3 or 5

1860

\(2p^2-2p\)

43

3 or 7

3612

\(2p^2-2p\)

5 Conclusion

For cryptographic purpose, one should construct pseudorandom sequences with high linear complexity according to the Berlekamp-Massey algorithm [14], which tells us that the complete sequences can be deduced from a knowledge of just 2L (here L is the linear complexity) consecutive terms from the sequences. So it is desired that the linear complexity should be at least half of the period.

In this article, under the assumption \(r^{p-1}\not \equiv 1 \pmod {p^2}\), we give the linear complexity of r-ary sequence derived from Euler quotients modulo 2p with p an odd prime. The results show that the linear complexity is equal to \(2p^2-2p\), which is larger enough to resist the attack from the Berlekamp-Massey algorithm. For the case of \(r^{p-1} \equiv 1 \pmod {p^2}\), we leave an open problem since such primes pair are rare.