Abstract
Based on the Euler quotient modulo 2p (p is an odd prime), we extend the binary sequence with period \(2p^2\) to r-ary sequence where r is an odd prime divisor of \((p-1)\). We determine exact values of the linear complexity of the new sequences under the assumption \(r^{p-1}\not \equiv 1 \pmod {p^2}\), which are larger than half of the period. For cryptographic purpose, the linear complexities of the sequences in this paper are of desired values.
Supported by National Natural Science Foundation of China (61763044).
Access provided by Autonomous University of Puebla. Download conference paper PDF
Similar content being viewed by others
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
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
Motivated by the previous work in [15, 19], we extend the binary threshold sequence to r-ary sequence as the following
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
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\)
which is satisfied by \((s_u)\) and where \(c_0\ne 0\), \(c_1,\dots ,c_{L-1}\in \mathbb {F}_q \). The polynomial
is called the minimal polynomial of \((s_u)\). The generating polynomial of \((s_u)\) is defined by
It is easy to show that
hence
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
By [19], note that \(q_{2p}(u)\) is always even since it can be rewritten as
and two numbers \(u^{\frac{p-1}{2}}\pm 1\) are even. Thus we define
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
for all \(0\le k<p-1\), then we have
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
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
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
where \(D_l \pmod p=\{ a \pmod p : a \in D_l\}\)
Lemma 2
Let n be a positive integer. Then
From now we define
From the definition of \((f_u)\) we obtain that the generating polynomial of \((f_u)\) is
Lemma 3
Let \(\beta \in \mathbb {\overline{F}}_r\) be a primitive \(2p^2\)-th root of unity. Then we have
-
(1)
\(D_l(\beta ^v)=D_{l+l'}(\beta )\),
-
(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)
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)
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
(1) of the Lemma is proved by the fact that
(2) If \(k\equiv 0 \pmod {p}\), then \(k=0\) or p. It can be easy to see that
if \(k=0\), and
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
then by Lemma 1 and (1) of this lemma, we have
\(\square \)
Lemma 5
If \( r^{p-1} \not \equiv 1\pmod {p^2}\), then
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
Meanwhile the minimal polynomial of \(\beta ^a\) over \(\mathbb {F}_r\) is given by
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
then by Lemma 3(2) we have
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
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
and
respectively.
Proof
We prove this theorem by the following two facts.
-
(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)
\(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
and if \(u=kp\) for \(k\in \mathbb {Z}_{2p}^* \cup 2\mathbb {Z}_{p}^*\), we have
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.
References
Chen, Z.: Linear complexity of some binary sequences derived from Fermat quotients. China Commun. 9(2), 105–110 (2012)
Chen, Z.: Trace representation and linear complexity of binary sequences derived from Fermat quotients. Sci. China Inf. Sci. 57(11), 1–10 (2014)
Chen, Z., Du, X.: On the linear complexity of binary threshold sequences derived from Fermat quotients. Des. Codes Cryptogr. 67(3), 317–323 (2013)
Chen, Z., Du, X., Marzouk, R.: Trace representation of pseudorandom binary sequences derived from Euler quotients. Appl. Algebr. Eng. Commun. Comput. 26(6), 555–570 (2015)
Dai, Z., Gong, G., Song, H.: A trace representation of binary Jacobi sequences. Discrete Math. 309(6), 1517–1527 (2009)
Dai, Z., Gong, G., Song, H., Ye, D.: Trace representation and linear complexity of binary \(e\)-th power residue sequences of period \(p\). IEEE Trans. Inf. Theory 57(3), 1530–1547 (2011)
Dai, Z., Gong, G., Song, H., Ye, D.: Trace representation and linear complexity of binary e-th residue sequences. In: International Workshop on Coding and Cryptography-WCC, pp. 121–133 (2003)
Du, X., Klapper, A., Chen, Z.: Linear complexity of pseudorandom sequences generated by Fermat quotients and their generalizations. Inf. Process. Lett. 112, 233–237 (2012)
Du, X., Chen, Z., Hu, L.: Linear complexity of binary sequences derived from Euler quotients with prime-power modulus. Inf. Process. Lett. 112(14–15), 604–609 (2012)
Du, X.: An extension of binary threshold sequences from Fermat quotients. Adv. Math. Commun. 10(4), 745–754 (2016)
Golomb, S., Gong, G.: Signal Design for Good Correlation. Cambridge University Press, Cambridge (2015)
Jungnickel, D.: Finite Fields, Structure and Arithmetics. Biblographiches Institute, Mannheim (1993)
Lidl, R., Niederreiter, H.: Finite Fields. Cambridge University Press, Cambridge (1997)
Massey, J.L.: Shift register synthesis and BCH decoding. IEEE Trans. Inf. Theory 15(1), 122–127 (1969)
Wu, C., Wei, W.: An extension of binary threshold sequences from Fermat quotients. Adv. Math. Commun. 10(4), 743–752 (2016)
Wu, C., Chen, Z., Du, X.: Binary threshold sequences derived from Carmichael quotients with even numbers modulus. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E95-A(7), 1197–1199 (2012)
Xiong, L., Shi, Y.: On the privacy-preserving outsourcing scheme of reversible data hiding over encrypted image data in cloud computing. CMC: Comput. Mater. Contin. 55(3), 523–539 (2018)
Xu, W., Xiang, S., Sachnev, V.: A cryptograph domain image retrieval method based on Paillier homomorphic block encryption. CMC: Comput. Mater. Contin. 055(2), 285–295 (2018)
Zhang, J., Zhao, C.: Linear complexity and trace representation of sequences with period \(2p^2\). In: IEEE International Symposium on Information Theory, pp. 2206–2210 (2018)
Zhao, L., Du, X., Wu, C.: Trace representation of the sequences derived from polynomial quotient. In: Sun, X., Pan, Z., Bertino, E. (eds.) ICCCS 2018. LNCS, vol. 11066, pp. 26–37. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-00015-8_3
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
Mohammed, R., Du, X., Li, L. (2019). Linear Complexity of r-ary Sequences Derived from Euler Quotients Modulo 2p. In: Sun, X., Pan, Z., Bertino, E. (eds) Artificial Intelligence and Security. ICAIS 2019. Lecture Notes in Computer Science(), vol 11634. Springer, Cham. https://doi.org/10.1007/978-3-030-24271-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-030-24271-8_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-24270-1
Online ISBN: 978-3-030-24271-8
eBook Packages: Computer ScienceComputer Science (R0)