Cryptogr. Commun. https://doi.org/10.1007/s12095-018-0300-y
A lower bound on the 2-adic complexity of the modified Jacobi sequence Yuhua Sun1,2,3
· Qiang Wang2 · Tongjiang Yan1,4
Received: 3 November 2017 / Accepted: 26 March 2018 © Springer Science+Business Media, LLC, part of Springer Nature 2018
Abstract Let p, q be distinct primes satisfying gcd(p − 1, q − 1) = d and let Di , i = 0, 1, · · · , d − 1, be Whiteman’s generalized cyclotomic classes with Z∗pq = ∪d−1 i=0 Di . In this paper, we give the values of Gauss periods based on the generalized cyclotomic sets d
−1
d
−1
2 2 D0∗ = ∪i=0 D2i and D1∗ = ∪i=0 D2i+1 . As an application, we determine a lower bound on the 2-adic complexity of the modified Jacobi sequence. Our result shows that the 2-adic complexity of the modified Jacobi sequence is at least pq − p − q − 1 with period N = pq. This indicates that the 2-adic complexity of the modified Jacobi sequence is large enough
The work is supported by Shandong Provincial Natural Science Foundation of China (No. ZR2017MA001, No. ZR2016FL01, No. ZR2014FQ005), the Open Research Fund from Shandong provincial Key Laboratory of Computer Network, Grant No. SDKLCN-2017-03, NSERC of Canada (No. RGPIN-2017-06410), Qingdao application research on special independent innovation plan project (No. 16-5-1-5-jch), Key Laboratory of Applied Mathematics of Fujian Province University (Putian University) (No.SX201702), and the Fundamental Research Funds for the Central Universities (No. 17CX02030A). Yuhua Sun
sunyuhua
[email protected] Qiang Wang
[email protected] Tongjiang Yan
[email protected] 1
College of Sciences, China University of Petroleum, Qingdao, Shandong, 266555, China
2
School of Mathematics and Statistics, Carleton University, Ottawa, ON, K1S 5B6, Canada
3
Qilu University of Technology (Shandong Academy of Sciences), Shandong Computer Science Center (National Supercomputer Center in Jinan, Shandong Provincial Key Laboratory of Computer Networks, Jinan, China
4
Key Laboratory of Applied Mathematics, Fujian Province University (Putian University), Fujian Putian, 351100, China
Cryptogr. Commun.
to resist the attack of the rational approximation algorithm (RAA) for feedback with carry shift registers (FCSRs). Keywords Gauss period · Generalized cyclotomic class · Modified Jacobi sequence · 2-adic complexity Mathematics Subject Classification (2010) 11B50 · 94A55 · 94A60
1 Introduction Pseudo-random sequences with good statistical property are widely used as basic blocks for constructing stream ciphers. After the Berlekamp-Massey algorithm (BMA) for LFSRs [16] and the rational approximation algorithm for FCSRs [17] were presented, the linear complexity and 2-adic complexity of the key stream sequence have been regarded as critical security criteria and both are required to be no less than one half of the period. Sequences from cyclotomic and generalized cyclotomic classes are important sequences for constructing codebooks [11, 14], frequency hopping sequences [27], optical orthogonal codes [2, 6, 7], and cyclic codes [8, 9]. Most cyclotomic sequences and generalized cyclotomic sequences have been proved to be with large linear complexity [1, 10, 15, 26]. However, there are only a handful research papers that focus on 2-adic complexities of these sequences. In fact, although the concept of the 2-adic complexity has been introduced for more than two decades, there are only a few kinds of sequences whose 2-adic complexities have been completely determined. For example, in 1997, Klapper has pointed out that an m-sequence with prime period has maximal 2-adic complexity [17]. In 2010, Tian and Qi showed that the 2-adic complexity of all the binary m-sequences is maximal [20]. Afterwards, Xiong et al. [22] presented a new method using circulant matrices to compute the 2-adic complexities of binary sequences. They showed that all the known sequences with ideal 2-level autocorrelation have maximum 2-adic complexity. Moreover, they also proved that the 2-adic complexities of Legendre sequences and Ding-Helleseth-Lam sequences with optimal autocorrelation are also maximal. Then, using the same method as that in [22], Xiong et al. [23] pointed out that two other classes of sequences based on interleaved structure have also maximal 2-adic complexity. One of these two classes of sequences was constructed by Tang and Ding [18], which has optimal autocorrelation, the other was constructed by Zhou et al. [29], which is optimal with respect to the Tang-Fan-Matsufuji bound [19]. The modified Jacobi sequence is one of sequence families constructed by Whiteman generalized cyclotomic classes [3, 4]. Green, Green, and Choi [12, 13] have proved that these sequences have large linear complexity and low autocorrelation in many cases. To the best of our knowledge, among Jacobi sequence families, there is no other result about the 2-adic complexities of these sequences other than twin-prime sequences and another class of sequences constructed from Whiteman generalized cyclotomic classes of order 2. The former sequences have ideal autocorrelation and they were proved to have maximal 2-adic complexity by Xiong et al [22], and the latter class has been proved to have maximal 2-adic complexity by Zeng et al. [28]. In this paper, we study the 2-adic complexity of the modified Jacobi sequences. We determine the Gauss periods of Whiteman generalized cyclotomic classes and then give a general lower bound on the 2-adic complexity, i.e., we prove that the 2-adic complexity of
Cryptogr. Commun.
all these sequences is lower bounded by pq − p − q − 1 with period N = pq. As a special case, we can also confirm that the twin-prime sequence has maximal 2-adic complexity. The rest of this paper is organized as follows. Some necessary definitions, notation, and previous results are introduced in Section 2. Gauss periods based on two Whiteman generalized cyclic sets are given in Section 3. A lower bound on the 2-adic complexity of the modified Jacobi sequence is given in Section 4. Finally we summarize our results and give some remarks in Section 5.
2 Preliminaries Let N be a positive integer, {si }N−1 i=0 a binary sequence of period N , and S(x) = Z[x]. If we write
N−1
si x i ∈
i=0
N−1
s i 2i S(2) m i=0 = N = , 0 ≤ m ≤ n, gcd(m, n) = 1, 2N − 1 2 −1 n
(1)
then the 2-adic complexity 2 (s) of the sequence {si }N−1 i=0 is defined as the integer log2 n, i.e., 2N − 1 , (2) 2 (s) = log2 gcd(2N − 1, S(2)) where x is the greatest integer that is less than or equal to x. Let p = df + 1 and q = df + 1 (p < q) be two odd primes with gcd(p − 1, q − 1) = d, where d, f, f are positive integers. Define N = pq, L = (p − 1)(q − 1)/d. The Chinese Remainder Theorem guarantees that there exists a common primitive root g of both p and q. Then the order of g modulo N is L. Let x be an integer satisfying x ≡ g (mod p), x ≡ 1 (mod q). The existence and uniqueness of x (mod N ) are also guaranteed by the Chinese Remainder Theorem. In [21], Whiteman presented the definition of the following generalized cyclotomic classes Di = {g t x i : t = 0, 1, · · · , L − 1}, i = 0, 1, · · · , d − 1
(3)
of order d. Moreover, he proved Z∗N = ∪d−1 i=0 Di , Di ∩ Dj = ∅ for i = j, where ∅ denotes the empty set. In particular, x d ≡ g u (mod N ) for some 0 ≤ u ≤ L − 1. The corresponding generalized cyclotomic numbers of order d are defined by (i, j )d = |(Di + 1) ∩ Dj |, for all i, j = 0, 1, · · · , d − 1. In other words, (i, j )d is the number of solutions s, t of the congruence gs x i + 1 ≡ gt x j
(mod N ),
Cryptogr. Commun.
where the values of s and t are each selected from the integers 0, 1, . . . , L −1. The following properties of the generalized cyclotomic numbers have also been given by Whiteman in [21]: (i, j )d = (d − i, j − i)d , j + d2 , i + d2 d , if ff is even, (i, j )d = if ff is odd, (j, i)d , d−1 (p − 2)(q − 2) − 1 + δi , (i, j )d = d
(4) (5) (6)
j =0
where δi =
1, if ff is even and i = d2 , or if ff is odd and i = 0, 0, otherwise.
If we denote P = {p, 2p, · · · , (q − 1)p}, Q = {q, 2q, · · · , (p − 1)q}, R = {0}, d
−1
d
−1
2 C0 = ∪i=0 D2i ∪ Q ∪ R,
2 C1 = ∪i=0 D2i+1 ∪ P ,
D0∗ = ∪i=0 D2i ,
D1∗ = ∪i=0 D2i+1 ,
d 2 −1
d 2 −1
then we have ZN = C0 ∪ C1 , Z∗N = D0∗ ∪ D1∗ and it is easy to see that D0∗ is a subgroup of Z∗N . The modified Jacobi sequence {si }N−1 i=0 is defined by 0, if i (mod N ) ∈ C0 , (7) si = 1, if i (mod N ) ∈ C1 . t+2j (mod p) and If i ∈ D2j , then i = g t x 2j for some 0 ≤ t ≤ L − 1. Then i ≡ g i i ≡ g t (mod q). In this case, pi q = 1 where (·) is the Legendre symbol. Similarly,
i if i ∈ D2j +1 , then pi q = −1. Therefore it is not difficult to verify that the modified Jacobi sequence is also equivalent to the following sequence ⎧ if i (mod N ) ∈ P , ⎪ ⎨ 1, i i
1− p q si = , if i ∈ Z∗N , ⎪ 2 ⎩ 0, otherwise.
In this paper, we discuss its 2-adic complexity using properties of generalized cyclotomic classes. Note that D0∗ is a subgroup of Z∗N . In this paper, we first determine the Gauss periods based on generalized cyclotomic classes D0∗ and D1∗ . Then, using these Gauss periods, a lower bound on the 2-adic complexity of the modified Jacobi sequence will be given. To this end, we first list the following properties of the above sets (The proofs of these properties can also be found in many literatures, for example, [24]). Lemma 1 For any a ∈ ZN and B ⊆ ZN , we denote aB = {ab | b ∈ B}. Then we have the following properties. (1) (2)
For each fixed a ∈ Di , we have aDj = D(i+j ) (mod d) , aP = P and aQ = Q, where i, j = 0, 1, · · · , d − 1. For each fixed a ∈ P , if b runs through each element of Di , i = 0, 1, · · · , d − 1, then ab runs each element of P exactly p−1 d times. Symmetrically, for each fixed a ∈ Q, if b runs through each element of Di , i = 0, 1, · · · , d − 1, then ab runs each element of Q exactly q−1 d times.
Cryptogr. Commun.
(3) (4)
For each fixed a ∈ P , we have aP = P , aQ = R. Symmetrically, for each fixed a ∈ Q, we have aQ = Q, aP = R. ∗ For each fixed a ∈ Di∗ , we have aDj∗ = D(i+j ) (mod 2) , aP = P and aQ = Q, where i, j = 0, 1. √
Let ωN = e2π −1/N be a N th complex primitive root of unity. Then the additive character χ of ZN is given by x χ (x) = ωN , x ∈ ZN ,
(8)
and Gauss periods of order d are defined by ηi = χ (x), i = 0, 1, · · · , d − 1. x∈Di
It is well-known that
χ (x) = −1,
(9)
χ (x) = −1,
(10)
x∈P
x∈Q
and
d−1
ηi = 1.
(11)
i=0
In the sequel, we also need the following two useful results that are essentially proved by Whiteman [21]. Lemma 2 The element −1 ∈ Z∗N satisfies d g δ x 2 (mod N ), if ff is even, −1 ≡ L g 2 (mod N ), if ff is odd, where δ is some fixed integer such that 0 ≤ δ ≤ L − 1. The following result for the case of i = j follows similarly as Lemma 2 in [21] and the result for the case of i = j comes from Lemma 4 in [21]. Lemma 3 For each u ∈ P ∪ Q, |Di ∩ (Dj + u)| =
⎧ ⎪ ⎨ ⎪ ⎩
(p−1)(q−1) , if i = j, d2 (p−1)(q−1−d) , if i = j and d2 (p−1−d)(q−1) , if i = j and d2
u ∈ P, u ∈ Q,
3 Gaussian periods of Whiteman generalized cyclotomic classes Define Ω0 =
x∈D0∗
d
χ (x) =
2 −1
i=0
η2i andΩ1 =
x∈D1∗
In this section, we determine the values of Ω0 and Ω1 .
d
χ (x) =
2 −1
i=0
η2i+1 .
Cryptogr. Commun.
Theorem 1 Let p = df +1, q = df +1 be distinct primes satisfying gcd(p−1, q −1) = d and let Di∗ be the generalized cyclotomic set defined in Section 2 and Ωi be the Gauss period based on Di∗ , where i = 0, 1. Then we have ⎧ √ 1± pq ⎪ ⎨ 2 , if ff is odd, or if ff is even and d ≡ 0 (mod 4), Ω0 = χ (x) = (12) √ ⎪ ⎩ 1± −pq x∈D0∗ , if ff is even and d ≡ 2 (mod 4), 2 (13) Ω1 = 1 − Ω 0 . Proof From the definition of the generalized cyclotomic classes, for any τ ∈ Dk , it can be easily verified that τ −1 ∈ D(d−k) (mod d) . Then, by Lemma 1, for any 0 ≤ i, j, k ≤ d − 1, we have | (Di + τ ) ∩ Dj | = | (τ −1 Di + 1) ∩ τ −1 Dj | = ((i + d − k) (mod d), (j + d − k) (mod d))d . For simplicity, we often use (i − k, j − k)d to denote ((i + d − k) (mod d), (j + d − k) (mod d))d . If ff is odd, then, by Lemma 2, we have −1 ∈ D0 . Therefore, using Lemma 3, we get ⎞2 ⎛ d d d d 2 −1 2 −1 2 −1 2 −1 ⎟ ⎜ 2 2 η2i ⎠ = η2i + η2i η2j (Ω0 ) = ⎝ i=0 d
=
2 −1
⎝
⎞ y−x ωN ⎠ +
x∈D2i y∈D2i
i=0
i=0 j =i,j =0
i=0
⎛
d−1
d
i=0 j =i,j =0
d 2 −1
=
i=0
(2i − k, 2i − k)d ηk +
k=0
d
2 −1 2 −1
⎛ ⎝
⎞ y−x ωN ⎠
x∈D2i y∈D2j
(p − 1)(q − 1) (p − 1)(q − 1 − d) − d d2
(p − 1 − d)(q − 1) − d2 d d d−1 2 −1 2 −1 (p − 1)(q − 1) (p − 1)(q − 1) + , (2i − k, 2j − k)d ηk − − d2 d2 i=0 j =i,j =0
k=0
where (p−1)(q−1) in the above d y ∈ D2i . Therefore, we have
expression counts the number of occurrence such that x =
⎛ ⎞ d d d−1 2 −1 2 −1 p−1 q −1 ⎜ ⎟ + (Ω0 )2 = (2i − k, 2j − k)d ⎠ ηk + ⎝ 2 2 k=0
⎛
i=0 j =0
⎞ d d d−1 2 −1 2 −1 p−1 q −1 ⎜ ⎟ + = (d − (2i − k), 2(j − i))d ⎠ ηk + ⎝ 2 2 k=0
i=0 j =0
k=0
j =0 j =0
⎛ ⎞ d d d−1 2 −1 2 −1 p−1 q −1 ⎜ ⎟ = d − (2(j − j ) − k), 2j d ⎠ ηk + + , ⎝ 2 2
(14)
Cryptogr. Commun.
where (14) comes from (4). Similarly, we can get ⎞2 d d d d 2 −1 2 −1 2 −1 2 −1 ⎟ ⎜ 2 2 η2i+1 ⎠ = η2i+1 + η2i+1 η2j +1 (Ω1 ) = ⎝ ⎛
i=0
i=0 j =i,j =0
i=0
⎛
⎞ d d d−1 2 −1 2 −1 p−1 q −1 ⎜ ⎟ + . d − (2(j − j ) + 1 − k), 2j d ⎠ ηk + = ⎝ 2 2 k=0
j =0 j =0
Then, ⎛ ⎛ d d d−1 2 −1 2 −1 ⎜ ⎜ 2 2 d − (2(j − j ) − k), 2j d (Ω0 ) + (Ω1 ) = ⎝ ⎝ k=0
j =0
j =0
+ d − (2(j − j ) + 1 − k), 2j
d
ηk
+(p − 1) + (q − 1) ⎛ ⎛ ⎞⎞ d −1 d−1 d−1 2 ⎜ ⎝ (j, 2j )d ⎠⎟ = ⎝ ⎠ ηk + (p − 1) + (q − 1) j =0
k=0
j =0
⎛ ⎞ d−1 ⎝ (j, 2j )d ⎠ + (p − 1) + (q − 1) = d 2 −1
j =0
=
d−1
(15)
j =0
⎛ ⎞ d d−1 2 −1 ⎝ (j, 2j )d ⎠ + (p − 1) + (q − 1) (j, 0)d +
j =0
j =1
j =0
⎛ ⎞ d−1 d−1 ⎝ (2j , j )d ⎠ + (p − 1) + (q − 1) (0, j )d + = d 2 −1
j =0
j =1
(16)
j =0
(p − 2)(q − 2) − 1 d × + (p − 1) + (q − 1) 2 d pq − 1 , = 1+ 2
= 1+
(17)
where (15) is obtained from (11) and (16) is obtained from (5) and (17) holds because of (6). Moreover, from (11), we know that Ω0 + Ω1 = 1 and (Ω0 )2 + (Ω1 )2 = (Ω0 + Ω1 )2 − 2Ω0 Ω1 = 1 − 2Ω0 Ω1 Then we obtain Ω0 Ω1 =
1−pq 4 ,
which implies Ω0 =
√ 1± pq 2
and Ω1 =
√ 1∓ pq . 2
Cryptogr. Commun.
Suppose that ff is even, by Lemma 2, we have −1 ∈ D d . Let d ≡ 2 (mod 4), i.e., 2
d 2
is odd. Then, for any 0 ≤ i, j ≤ d2 − 1 with i = j , we know that 2i + d2 ≡ 2j (mod d) and 2i + 1 + d2 ≡ 2j + 1 (mod d). Therefore, ⎛ d d 2 −1 2 −1 ⎜ (Ω0 )2 = ⎝ i=0 j =0
⎞
y−x ⎟ ωN ⎠
x∈D2i+ d y∈D2j 2
d−1
(p − 1)(q − 1) = ηk − 2 × d2 d i=0 j =0 k=0 ⎛ ⎞ d d d−1 2 −1 2 −1 d (p − 1)(q − 1) d ⎟ ⎜ = − (2i − k), 2(j − i) + ⎝ ⎠ ηk − 2 2 d 2 d d 2 −1 2 −1
k=0
=
d−1 k=0
=
d−1 k=0
⎛
d 2i + − k, 2j − k 2
i=0 j =0
⎞
d d 2 −1 2 −1
(p − 1)(q − 1) ⎜ ⎟ (2(j − i), k − 2i)d ⎠ ηk − ⎝ 2 ⎛
i=0 j =0
⎞
d d 2 −1 2 −1
⎟ (p − 1)(q − 1) ⎜ , 2j , k − 2(j − j ) d ⎠ ηk − ⎝ 2 j =0 j =0
where we use (4) and (5) to simplify the above expressions. Similarly, we can get ⎛ ⎞ d d d−1 2 −1 2 −1 (p − 1)(q − 1) ⎜ ⎟ . 2j , k − 2(j − j ) − 1 d ⎠ ηk − (Ω1 )2 = ⎝ 2 k=0
j =0 j =0
Then we get ⎞⎞ ⎛ ⎛ d d d−1 2 −1 2 −1 ⎟⎟ ⎜ ⎜ 2j , k−2(j −j ) d + 2j , k−2(j −j )−1 d ⎠⎠ ηk (Ω0 )2 + (Ω1 )2 = ⎝ ⎝ k=0
j =0
j =0
− (p − 1)(q − 1) ⎛ ⎛ ⎞⎞ d d−1 d−1 2 −1 ⎜ ⎝ (2j , j )d ⎠⎟ = ⎝ ⎠ ηk − (p − 1)(q − 1) k=0 d 2 −1
=
j =0
j =0
j =0
⎛
⎞ d−1 ⎝ (2j , j )d ⎠ − (p − 1)(q − 1)
(p − 2)(q − 2) − 1 d × − (p − 1)(q − 1) 2 d pq + 1 , = 1− 2
=
(18)
j =0
(19)
Cryptogr. Commun.
where (18) is obtained from (11) and (19) is obtained from (6). Using similar arguments, √ √ 1± −pq 1∓ −pq we have Ω0 Ω1 = 1+pq , which implies Ω = and Ω = . For the case of 0 1 4 2 2 even ff and d ≡ 0 (mod 4), the result can be obtained similarly.
4 A lower bound on the 2-adic complexity of Jacobi sequence Let {si }N−1 i=0 be a binary sequence with period N and we recall that S(x) =
N−1
si x i ∈ Z[x].
i=0 si−j (mod N) and
we view A Let A = (ai,j )N×N be the circulant matrix defined by ai,j = as a matrix in the field C of complex numbers. The following results are obtained in [5] and [22] respectively. Lemma 4 (1) det(A) = root of unity. (2) If det(A) = 0, then
N−1 t=0
t ), where ω = e S(ωN N
√ 2π −1 N
is a complex primitive N th
gcd S(2), 2N − 1 | gcd det(A), 2N − 1 .
(20)
In this section, using Gauss periods which have been determined in Section 3, we will give a lower bound on the 2-adic complexity of the modified Jacobi sequence. Lemma 5 Let {si }N−1 i=0 be the modified Jacobi sequence with period N = pq. Then we have ⎧ (p+1)(q−1) , if a ∈ R, ⎪ ⎪ ⎪ −Ω 2, ⎪ if a ∈ D0∗ , ⎨ 0 a if a ∈ D1∗ , (21) S(ωN ) = −Ω1 , ⎪ p+1 ⎪ ⎪− 2 , if a ∈ P , ⎪ ⎩ q−1 if a ∈ Q. 2 , Proof By the definition of S(x), we obtain a ) = S(ωN
a k (ωN ) =
k∈C1
=
k∈aD1∗
k ωN
+
k∈D1∗
a k (ωN ) +
a k (ωN )
k∈P
k ωN .
k∈aP
a ) = (p−1)(q−1) +(q −1) = (p+1)(q−1) . Secondly, Firstly, if a = 0, then it is easy to see S(ωN 2 2 ∗ if a ∈ D0 , by Lemma 1 and (9), then we have a k k k k S(ωN ) = ωN + ωN = ωN + ωN k∈aD1∗
k∈aP
k∈D1∗
k∈P
= Ω1 − 1 = −Ω0 (for Ω0 + Ω1 = 1 by Eq.(11)). Similarly, if a ∈
D1∗ ,
we have
a ) = S(ωN
k∈aD1∗
k ωN +
k∈aP
= Ω0 − 1 = −Ω1 .
k ωN =
k∈D0∗
k ωN +
k∈P
k ωN
Cryptogr. Commun.
If a ∈ P , again by Lemma 1, we have p−1 k a k k k ) = ωN + ωN = ωN + ωN S(ωN 2 ∗ k∈aP
k∈aD1
= −
k∈P
k∈P
p+1 p−1 −1=− . 2 2
Similarly, if a ∈ Q we have q −1 k a k k S(ωN ) = ωN + ωN = ωN + (q − 1) 2 ∗ k∈aP
k∈aD1
= −
k∈Q
q −1 q −1 + (q − 1) = . 2 2
The result follows. Lemma 6 Let p and q be two distinct odd prime numbers and N = pq. Then we N −1 N −1 ) = gcd(2p − 1, q) and gcd 2q − 1, 22q −1 have gcd(2p − 1, 22p −1 = gcd(2q − 1, p).
N −1 Particularly, if p < q, then we have gcd 2q − 1, 22q −1 = gcd(2q − 1, p) = 1. Proof Note that 2N − 1 = 2pq − 1 = (2p − 1)(2p(q−1) + 2p(q−2) + · · · + 2p + 1) = (2q − 1)(2q(p−1) + 2q(p−2) + · · · + 2q + 1). −1 −1 ≡ q (mod 2p − 1) and 22q −1 ≡ p (mod 2q − 1) respectively, which Then we obtain 22p −1
N −1 N −1 imply gcd 2p − 1, 22p −1 = gcd(2p − 1, q) and gcd 2q − 1, 22q −1 = gcd(2q − 1, p) respectively. Particularly, for p < q, if gcd(2q − 1, p) > 1, i.e., p | 2q − 1, then the multiplicative order of 2 modulo p, denoted as Ordp (2), is a divisor of q. Because q is a prime number, we must have Ordp (2) = q. By Fermat’s little theorem, we know that p | 2p−1 −1. Therefore, we have q ≤ p −1, which contradicts to the hypothesis that p < q. The desired result follows. pq
pq
Theorem 2 Let p = df + 1 and q = df + 1 be two odd primes satisfying gcd(p − 1, q − 1) = d and p < q. Suppose {si }N−1 i=0 is the modified Jacobi sequence of order d with period N = pq. Then the 2-adic complexity φ2 (s) of {si }N−1 i=0 is bounded by φ2 (s) ≥ pq − p − q − 1. In particular, if q = p + 2, then the 2-adic complexity of
(22)
{si }N−1 i=0
is maximal.
Proof By Lemmas 4 and 5, we can get det(A) =
N−1
a S(ωN )
a=0
=
a S(ωN )
a∈R
= 2
p+1 2
a∈D0∗
q
a S(ωN )
q −1 2
a∈D1∗
a S(ωN )
p
(Ω0 Ω1 )
a S(ωN )
a∈P (p−1)(q−1) 2
a∈Q
.
a S(ωN )
Cryptogr. Commun.
From Theorem 1, we know that Ω0 Ω1 = 1−pq if ff is odd or if ff is even and d ≡ 0 4 1+pq (mod 4), and Ω0 Ω1 = 4 if ff is even and d ≡ 2 (mod 4). Then we have ⎧
q
p
(p−1)(q−1) 2 ⎪ p+1 q−1 pq−1 ⎪ 2 , if ff is odd, or if ff is ⎪ ⎪ 2 2 4 ⎪ ⎨ even and d ≡ 0 (mod 4) det(A) =
q
p
(p−1)(q−1) ⎪ 2 q−1 pq+1 ⎪ ⎪ 2 p+1 , if ff is even and ⎪ 2 2 4 ⎪ ⎩ d ≡ 2 (mod 4).
(23)
Now, let r be a prime factor of 2N − 1 and Ordr (2) be the multiplicative order of 2 modulo r. Then we get Ordr (2) | N . Note that N = pq. Therefore, Ordr (2) = pq, p or q. Next, we will prove gcd(det(A), 2N − 1) ≤ (2p − 1)(2q − 1). To this end, we need to discuss the following three cases. Case 1. Ordr (2) = pq. By Fermat’s little Theorem, we know that r | 2r−1 − 1, which implies Ordr (2) ≤ r − 1. Since Ordr (2) = pq, then we have pq ≤ r − 1, i.e., q−1 pq±1 r ≥ pq+1. Obviously, we have p+1 < pq+1. 2 < pq+1, 2 < pq+1, and 4 Hence gcd(det(A), r) = 1. In this case, r can not be a factor of det(A). Therefore, r can not be a common factor of det(A) and 2N − 1 in the case of Ordr (2) = pq. Case 2. Ordr (2) = p. It is obvious that r | 2p − 1. Using similar
arguments to that in Case p+1 pq∓1 1, we can get r ≥ p + 1, which implies gcd 2 , r = 1. If r | q−1 2 or r | 4 pq±1 4
correspond to the two cases in (23)), then we have gcd(r, q) = 1.
N −1 = gcd(2p − 1, q). Thus Furthermore, by Lemma 6, we know gcd 2p − 1, 22p −1 N
−1 we have gcd r, 22p −1 = 1. This implies that r can not be a common factor of (here
−1 in the case of Ordr (2) = p. det(A) and 22p −1 q Case 3. Ordr (2) = q. It is
obvious that r | 2 − 1. From NLemma
6 we know that 2N −1 −1 q gcd 2 − 1, 2q −1 = 1, which implies that gcd r, 22q −1 = 1. Similarly, we N
can show that r can not be a common factor of det(A) and Ordr (2) = q.
2N −1 2q −1
in the case of
N p Therefore, combining 1-3, the above Cases
we always have gcd(det(A), 2 − 1) ≤ (2 − 2N −1 q 1)(2 − 1) and gcd det(A), (2p −1)(2q −1) = 1. From Lemma 4, we have
gcd S(2), 2N − 1 ≤ gcd det(A), 2N − 1 ≤ (2p − 1)(2q − 1). Finally, by (2), we get 2N − 1 2pq − 1 ≥ log2 p ≥ pq − p − q − 1. φ2 (s) = log2 gcd(2N − 1, S(2)) (2 − 1)(2q − 1) In particular, if q = p + 2, then we know that ff is even, which implies that det(A) =
p(p+2)+1 . From the above argument, we know that 2 p+1 2 gcd
p + 1 p(p+2) ,2 − 1 | (2p − 1)(2p+2 − 1). 2
Cryptogr. Commun.
However, the smallest possible prime factors of 2p − 1 and 2p+2 − 1 are 2p + 1 and 2p + 5 respectively, we must have p + 1 p(p+2) ,2 gcd − 1 = 1. 2 The desire result follows. Example 1 Let p = 5 and q = 17. Take g = 3 and then x = 18. We note that D0 = {1, 3, 9, 27, 81, 73, 49, 62, 16, 48, 59, 7, 21, 63, 19, 57}, D1 = {18, 54, 77, 61, 13, 39, 31, 11, 33, 14, 42, 41, 38, 29, 2, 6}, D2 = {69, 37, 26, 78, 64, 22, 66, 28, 84, 82, 76, 58, 4, 12, 36, 23}, D3 = {52, 71, 43, 44, 47, 56, 83, 79, 67, 31, 8, 24, 72, 46, 53, 74}, P = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80}. The support set of the modified Jacobi sequence of period 5 × 17 = 85 is C1 = D1 ∪ D3 ∪ P . Here ff = 4 is even and d = gcd(p, q) = gcd(4, 16) = 4 ≡ 0 (mod 4). In this case, Det(A) = 2 × 317 × 85 × 2132 . Moreover, the 2-adic complexity of this sequence is maximum. We have verified these results by a Mathematica program.
5 Summary and further remarks In this paper, we derived Gauss periods of a class of generalized cyclotomic sets from Whiteman generalized cyclotomic classes. As an application, a lower bound on the 2adic complexity of the modified Jacobi sequence was determined. Our result shows that the 2-adic complexity of the modified Jacobi sequence with period N = pq is at least pq − p − q − 1, which is obviously large enough to resist against the RAA for FCSR. It is necessary to point out that sequences derived from Jacobi symbols, such as Jacobi sequence, the modified Jacobi sequence and variations of modified Jacobi sequences [25], are closely related. Indeed, both modified sequences are just slight modifications of Jacobi sequences only on those terms si with gcd(i, N ) > 1. Therefore, the calculation of Gauss periods and the method of determining the 2-adic complexity in this paper can also be adapted to calculate the 2-adic complexity of Jacobi sequences and similar modifications of Jacobi sequences. Acknowledgements Parts of this work were done during a very pleasant visit of the first author to the School of Mathematics and Statistics at Carleton University. She wishes to thank the hosts for their hospitality. We also thank anonymous referees for their helpful suggestions.
References 1. Bai, E., Liu, X., Xiao, G.: Linear complexity of new generalized cyclotomic sequences of order two of length pq. IEEE Trans. Inform. Theory 51, 1849–1853 (2005) 2. Cai, H., Liang, H., Tang, X.: Constructions of optimal 2-D optical orthogonal codes via generalized cyclotomic classes. IEEE Trans. Inform. Theory 61, 688–695 (2015) 3. Chen, Z., Du, X., Xiao, G.: Sequences related to Legendre/Jacobi sequences. Inf. Sci. 177(21), 4820– 4831 (2007) 4. Cusick, T.W., Ding, C., Renvall, A.: Stream ciphers and number theory. Elsevier, Amsterdam (2015) 5. Davis, P.J.: Circulant matrices. Chelsea, New York (1994)
Cryptogr. Commun. 6. Ding, C., Xing, C.: Several classes of (2m − 1, w, 2) optical orthogonal codes. Discret. Appl. Math. 128, 103–120 (2003) 7. Ding, C., Xing, C.: Cyclotomic optical orthogonal codes of composite lengths. IEEE Trans. Inform. Theory 52, 263–268 (2004) 8. Ding, C.: Cyclotomic constructions of cyclic codes with length being the product of two primes. IEEE Trans. Inform. Theory 58, 2231–2236 (2012) 9. Ding, C.: Cyclic codes from the two-prime sequences. IEEE Trans. Inform. Theory 58, 3881–3891 (2012) 10. Ding, C., Helleseth, T.: On the linear complexity of Legendre sequences. IEEE Trans. Inform. Theory 44, 1693–1698 (1998) 11. Fan, C., Ge, G.: A unified approach to Whiteman’s and Ding-Helleseth’s generalized cyclotomy over residue class rings. IEEE Trans. Inf. Theory 60, 1326–1336 (2014) 12. Green, D.H., Green, P.R.: Modified Jacobi sequences. IEEE Proceedings-Computers and Digital Techniques 147(4), 241–251 (2000) 13. Green, D.H., Choi, J.: Linear complexity of modified Jacobi sequences. IEE Proceedings-Computers and Digital Techniques 149(3), 97–101 (2002) 14. Hu, L., Yue, Q.: Gauss periods and codebooks from generalized cyclotomic sets of order four. Des. Codes Crypt. 69, 233–246 (2013) 15. Li, X., Ma, W., Yan, T., Zhao, X.: Linear complexity of a new generalized cyclotomic sequence of order two of length pq. IEICE Trans. 96-A, 1001–1005 (2013) 16. Massey, J.L.: Shift-register synthesis and BCH decoding. IEEE Trans. Inform. Theory 15, 122–127 (1969) 17. Klapper, A., Goresky, M.: Feedback shift registers, 2-adic span, and combiners with memory. J. Cryptol. 10, 111–147 (1997) 18. Tang, X., Ding, C.: New classes of balanced quaternary and almost balanced binary sequences with optimal autocorrelation Value. IEEE Trans. Inform. Theory 56, 6398–6405 (2010) 19. Tang, X., Fan, P., Matsufuji, S.: Lower bounds on the maximum correlation of sequences with low or zero correlation zone. Electron. Lett. 36, 551–552 (2000) 20. Tian, T., Qi, W.: 2-Adic complexity of binary m-sequences. IEEE Trans. Inform. Theory 56, 450–454 (2010) 21. Whiteman, A.L.: A family of difference sets. Ill. J. Math. 6, 107–121 (1962) 22. Xiong, H., Qu, L., Li, C.: A new method to compute the 2-adic complexity of binary sequences. IEEE Trans. Inform. Theory 60, 2399–2406 (2014) 23. Xiong, H., Qu, L., Li, C.: 2-Adic complexity of binary sequences with interleaved structure. Finite Fields Appl. 33, 14–28 (2015) 24. Yan, T.: Study on constructions and properties of pseudo-random sequence. Ph. D Thesis (2007) 25. Xiong, T., Hall, J.I.: Modifications of modified Jacobi sequences. IEEE Trans. Inform. Theory 57, 493– 504 (2011) 26. Yan, T., Du, X., Xiao, G., Huang, X.: Linear complexity of binary Whiteman generalized cyclotomic sequences of order 2k . Inf. Sci. 179, 1019–1023 (2009) 27. Zeng, X., Cai, H., Tang, X., Yang, Y.: Optimal frequency sequences of odd length. IEEE Trans. Inform. Theory 59, 3237–3248 (2013) 28. Xiao, Z., Zeng, X., Sun, Z.: 2-Adic complexity of two classes of generalized cyclotomic binary sequences. Int. J. Found. Comput. Sci. 27, 879–893 (2016) 29. Zhou, Z., Tang, X., Gong, G.: A new classes of sequences with zero or low correlation zone based on interleaving technique. IEEE Trans. Inform. Theory 54, 4267–4273 (2008)
