Pseudo-random sequences were widely used in communication and cryptographic systems. For the application of stream cipher, the keystream sequences had unpredictability and randomness [1]. One of the important indexes for measuring these properties is linear complexity of sequence, which is defined to be the length of the shortest linear feedback shift register that can generate the given sequence. Generally speaking, a sequence with large linear complexity (at least a half of its period) is considered to be favorable for cryptography to resist the well-known Berlekamp-Massey algorithm.

For an integer $ N\geq 2 $, let $ \mathbb{Z}_N = \{0, 1, \cdots, N-1\} $ denote the ring of integers modulo $ N $ and $ \mathbb{Z}^*_N $ denote the set of all invertible elements of $ \mathbb{Z}_N $. Let $ \{D_0, D_1, \cdots, D_{d-1}\} $ be a partition of $ \mathbb{Z}^*_N $. If $ D_0 $ is a multiplicative subgroup of $ \mathbb{Z}^*_N $ and there exist elements $ g_i\in \mathbb{Z}^*_N $ such that $ D_i = g_iD_0 $ for all $ i\in \{1, 2, \cdots, d-1\} $, then for prime (composite) $ N $, these $ D_i $ are called classical (generalized) cyclotomic classes of order $ d $ with respect to $ N $.

Using classical cyclotomy or generalized cyclotomy to construct sequences is an effective method to obtain sequences with large linear complexity. The linear complexity and autocorrelation property of generalized cyclotomic sequences with various period were extensively studied in the literature (see [2-7]). In this paper, we focus on the generalized cyclotomic binary sequences of period $ pq $.

The generalized cyclotomic binary sequences of period $ pq $ are by far constructed on the basis of Whiteman's generalized cyclotomic classes or Ding-Helleseth generalized cyclotomic classes which are proposed in [8] and [9], respectively. Most of these sequences have large linear complexity. A brief review of these sequences are provided in Section 2. In this paper, a class of new generalized cyclotomic binary sequences of period $ pq $ based on Whiteman's generalized cyclotomy of order 4 and classic cyclotomy of order 2 is proposed. By using the classic method for calculating the linear complexity described in [10], we determine the exact value of the linear complexity of such sequences. Our results show that the proposed sequences have large linear complexity.

In this section, we first recall the two types of generalized cyclotomy with respect to $ pq $ and the known generalized cyclotomic sequences of period $ pq $, and then define a class of new generalized cyclotomic sequences of period $ pq $.

Let $ N = pq $, where $ p $ and $ q $ are distinct odd primes with gcd $ (p-1, \, q-1) = d $. Define $ e = \frac{(p-1)(q-1)}{d} $. Let $ g $ be a fixed primitive root of both $ p $ and $ q $. Then $ \text{ord}_N(g) = \text{lcm}\, (p-1, q-1) = e $. Let $ x $ be an integer satisfying $ x \equiv g\, ({\rm mod}\, p), x \equiv 1\, ({\rm mod}\, q). $ Whiteman proved in [8] that

$ Z_N^{*} = \left\{ {g^s x^i :s = 0, 1, \cdots , e-1;\, i = 0, 1, \cdots, d-1} \right\}. $

Whiteman's generalized cyclotomic classes of order $ d $ with respect to $ pq $ are defined by [8]

$ \begin{equation} { } D_i = \left\{{g^s x^i\, (\bmod\, pq)\, :\, s = 0, 1, \cdots, e-1}\right\}, i = 0, 1, \cdots, d-1. \end{equation} $

(2.1)

Ding-Helleseth generalized cyclotomic classes of order $ d $ with respect to $ pq $ are defined by [9]

$ D'_i = \left\{g^{ds+i} x^j\, (\bmod\, pq)\, :\, s = 0, 1, \cdots, \frac{e}{d}-1; j = 0, 1, \cdots, d-1\right\}, i = 0, 1, \cdots, d-1. $

On the basis of these two generalized cyclotomies of even order $ d $, many generalized cyclotomic sequences of period $ pq $ were constructed.

Let $ P = p\mathbb{Z}_q^* = \left\{p, 2p, \cdots, (q-1)p\right\}, Q = q\mathbb{Z}_p^* = \left\{q, 2q, \cdots, (p-1)q\right\}, R = \left\{0 \right\}. $ It is easily verified that $ \mathbb{Z}_N = \mathbb{Z}_N^*\cup P\cup Q\cup R $. Using Whiteman's generalized cyclotomy of order 2 with respect to $ pq $, Ding first constructed a class of generalized cyclotomic binary sequences which admits $ D_1\cup P $ as the characteristic set, i.e., the sequences $ (s_0, s_1, s_2, \cdots) $ are given by $ s_i = 1 $ if $ i\, (\bmod pq)\in D_1\cup P $ and $ s_i = 0 $ otherwise. The linear complexity and autocorrelation property of these sequences were investigated in [10] and [11]. This kind of sequences was extended to the cases of $ d = 4 $ and $ d = 2^k $ in [12] and [13], respectively, where the linear complexity of the binary sequences with the characteristic sets $ \bigcup \limits_{i = \frac{d}{2}}^{d-1}D_i\cup P $ was calculated. Based on Ding-Helleseth generalized cyclotomy, the binary sequences with the characteristic sets $ \bigcup \limits_{i = \frac{d}{2}}^{d-1}D'_i\cup P $ for $ d = 2 $ were proposed in [14] and the linear complexity and autocorrelation values of these sequences were determined.

It is easily seen that the difference between the numbers of ones and zeros is $ q-p-1 $ in all the above sequences, i.e., they are not balanced unless $ q = p+2 $ (note that in the case where the difference is equal to $ \pm 1 $ the sequences are called almost balanced). In [9] Ding and Helleseth introduced a new method to construct almost balanced sequences, that is, using the classic cyclotomy to divide the sets $ P $ and $ Q $. Let $ d_1 $ be a divisor of $ d $, and $ p-1 = d_1f_1 $, $ q-1 = d_1f_2 $. For $ i = 0, 1, \cdots, d_1-1 $, define

$ \begin{eqnarray} D_i^{(p)} = \{g^{d_1s+i}\, (\bmod\, p)\, :\, s = 0, 1, \cdots, f_1-1\}, {}\\ D_i^{(q)} = \{g^{d_1s+i}\, (\bmod\, q)\, :\, s = 0, 1, \cdots, f_2-1\}. \end{eqnarray} $

(2.2)

Then $ D_i^{(p)} $ and $ D_i^{(q)} $ with $ i\in \{0, 1, \cdots, d_1-1\} $ are the classic cyclotomic classes of order $ d_1 $ with respect to $ p $ and $ q $, respectively. Let $ P_i = pD_i^{(q)} $, $ Q_i = qD_i^{(p)} $. Then $ P = \bigcup \limits_{i = 0}^{d_1-1}P_i $, $ Q = \bigcup \limits_{i = 0}^{d_1-1}Q_i $. The binary sequences based on Ding-Helleseth generalized cyclotomy and classic cyclotomy corresponding to $ d = d_1 = 2 $, $ 4 $ and $ 6 $ were considered in [15-17], respectively, where the linear complexity of the binary sequences with the characteristic set $ \bigcup \limits_{i = \frac{d}{2}}^{d-1}(D'_i\cup P_i\cup Q_i) $ was determined. The general case of $ d = d_1 = 2k $ was discussed in [18] and a lower bound on the linear complexity of the sequences was given. Almost balanced binary sequences based on Whiteman's generalized cyclotomy with the characteristic set $ D_1\cup P_1\cup Q_1 $ for $ d = d_1 = 2 $ were investigated in [19-21], where the lower bound of the linear complexity of the sequences was given in [19] and the exact values of the linear complexity and autocorrelation of these sequences were calculated respectively in [20, 21]. In [22], the linear complexity of the sequences with the characteristic set $ D_2\cup D_3\cup P_2 \cup P_3\cup Q_2\cup Q_3 $ was determined.

In the following, we define a family of generalized cyclotomic binary sequences of period $ N = pq $, where $ p $ and $ q $ are distinct odd primes with gcd $ (p-1, \, q-1) = 4 $. Let $ D_i $ with $ i\in \{0, 1, 2, 3\} $ be Whiteman's generalized cyclotomic classes of order $ 4 $ defined in (2.1), $ D_i^{(p)} $ and $ D_i^{(q)} $ with $ i\in \{0, 1\} $ be the classical cyclotomic classes of order 2 defined in (2.2). Let $ P_i = pD_i^{(q)} $, $ Q_i = q D_i^{(p)} $, $ R = \left\{0 \right\} $. Then

$ \mathbb{Z}_N = \mathbb{Z}_N^*\cup P\cup Q\cup R = \bigcup \limits_{i = 0}^{3}D_i\bigcup \limits_{i = 0}^{1}P_i\bigcup \limits_{i = 0}^{1}Q_i\cup R. $

Define two sets

$ C_0 = D_{a+2} \cup D_{a+3} \cup P_0 \cup Q_0 \cup R \;\text{and} \; C_1 = D_a \cup D_{a+1} \cup P_1 \cup Q_1, $

where $ a $ is an arbitrary integer with $ 0\leq a\leq 3 $, and the subscripts $ i $ in $ D_i $ are assumed to be taken modulo $ 4 $. For simplicity, the modulo operation is omitted in this paper. It is easy to see that $ \{C_0, C_1\} $ forms a partition of $ \mathbb{Z}_N $ and $ |C_0|-|C_1| = 1 $. Now we define a family of almost balanced binary sequences of period $ pq $ which admits $ C_1 $ as the characteristic set, i.e., the sequences $ \textbf{s}^\infty = (s_0, s_1, s_2, \cdots) $ are given by

$ \begin{equation} s_i = \left\{ {\begin{array}{*{20}c} {0}, \hfill & {i\, ({\rm mod}\, pq) \in C_0, } \hfill \\ {1}, \hfill & {i\, ({\rm mod}\, pq) \in C_1.} \hfill \\ \end{array}} \right. \end{equation} $

(2.3)

Let $ \textbf{s}^\infty = (s_0, s_1, s_2, \cdots) $ be a periodic infinite sequence over a field $ \mathbb{F} $. The linear complexity of $ \textbf{s}^\infty $ is defined to be the least positive integer $ L $ such that there are constants $ c_0 = 1 $, $ c_1, \cdots, c_L \in \mathbb{F} $ satisfying $ -s_i = c_1 s_{i-1} + c_2 s_{i-2}+\cdots+ c_L s_{i-L}\,\; \text{for all}\; i\geq L. $ The polynomial $ c(x) = c_0 + c_1x +\cdots c_L{x^L} $ is called the minimal polynomial of $ \textbf{s}^\infty $. Let $ N $ be the period of $ \textbf{s}^\infty $. It is well known that

$ c(x) = \frac{x^N-1}{\gcd(x^N-1, s(x))}, $

where $ s(x) = s_0 + s_1x+\cdots +s_{N-1}x^{N-1} $ is the generating polynomial of the sequence $ \textbf{s}^\infty $. The linear complexity of $ \{s_i\} $ is given by

$ \begin{equation} L(\textbf{s}^\infty) = N-\deg(\gcd(x^N-1, s(x))). \end{equation} $

(3.1)

In this section, we use (3.1) to determine the linear complexity of the new generalized cyclotomic binary sequences of period $ pq $ defined by (2.3).

For $ a $ with $ 0\leq a\leq 3 $, denote

$ \begin{equation} { } s_a(x) = \sum\limits_{i\in C_1} x^i = (\sum\limits_{i\in P_1}+ \sum\limits_{i\in Q_1}+\sum\limits_{i\in D_{a}}+\sum\limits_{i\in D_{a+1}})x^i\in GF(2)[x]. \end{equation} $

(3.2)

Then the generating polynomial of a sequence defined by (2.3) for a given integer $ a $ is $ s_a(x) $. Let $ m $ be the order of 2 modulo $ N $. Then there exists a primitive $ N $th root of unity $ \alpha $ over the splitting field $ GF(2^m) $ of $ x^N -1 $. Thus the linear complexity of the sequence is given by

$ \begin{equation} L(\textbf{s}^\infty) = N-|\{j\, :\, s_a(\alpha^j) = 0\}|. \end{equation} $

(3.3)

That is to say, the problem of determining the linear complexity of the sequence defined by (2.3) is reduced to that of counting the number of roots in the set $ \{\alpha^j\, :\, j = 0, 1, \cdots, pq-1\} $ of the generating polynomial given in (3.2).

To determine the linear complexity of the sequences defined by (2.3), we need the following lemmas.

Lemma 2.1 (see [23]) Let the symbols be the same as before. Then

(ⅰ) if $ a\in D_i $, then $ aD_j = D_{(i+j)({\rm mod}\, 4)} $, where $ i, j \in \{0, 1, 2, 3\}; $

(ⅱ) for any odd prime $ p $, if $ t\, ({\rm mod}\, p)\in D^{(p)}_i $, then $ tD^{(p)}_j = D^{(p)}_{(i+j)\, ({\rm mod}\, 2)} $, where $ i, j\in \{0, 1\} $.

Lemma 2.2 (see [15]) Let the symbols be the same as before. Then

(ⅰ) $ \sum\limits_{i \in P }\alpha^i = \sum\limits_{i = 1}^{q-1}\alpha^{pi} = 1 $; (ⅱ) $ \sum\limits_{i \in Q }\alpha^i = \sum\limits_{i = 1}^{p-1}\alpha^{qi} = 1 $; (ⅲ) $ \sum\limits_{i \in Z^*_{pq} }\alpha^i = 1 $.

Lemma 2.3 (see [12]) Let the symbols be the same as before. Then

$ \sum\limits_{i \in D_j }\alpha ^{ti} = \left\{ {\begin{array}{*{20}c} {\frac{p-1}{4}\, ({\rm mod}\, 2), \;\text {if}\; t \in P, } \\ {\frac{q-1}{4}\, ({\rm mod}\, 2), \;\text {if}\; t \in Q.} \end{array}} \right. $

Lemma 2.4 Let the symbols be the same as before. Then

(ⅰ) if $ t\, ({\rm mod}\, p)\in D^{(p)}_0 $, then $ \sum\limits_{i\in Q_1}\alpha^{ti} = \sum\limits_{i\in Q_1}\alpha^{i} $;

(ⅱ) if $ t\, ({\rm mod}\, p)\in D^{(p)}_1, $ then $ \sum\limits_{i \in Q_1 }\alpha ^{ti} = 1+\sum\limits_{i \in Q_1 }\alpha ^{i} $;

(ⅲ) if $ t\, ({\rm mod}\, q)\in D^{(q)}_0, $ then $ \sum\limits_{i \in P_1 }\alpha ^{ti} = \sum\limits_{i \in P_1 }\alpha ^{i} $;

(ⅳ) if $ t\, ({\rm mod}\, q)\in D^{(q)}_1, $ then $ \sum\limits_{i \in P_1 }\alpha ^{ti} = 1+\sum\limits_{i \in P_1 }\alpha ^{i} $.

Proof (ⅰ) If $ t\, ({\rm mod}\, p)\in D^{(p)}_0 $, then by Lemma 2.1 (ⅱ), we have $ tQ_1 = tqD^{(p)}_1 = qD^{(p)}_1 = Q_1 $, thus

$ \sum\limits_{i \in Q_1 }\alpha ^{ti} = \sum\limits_{i \in Q_1 }\alpha^{i}. $

(ⅱ) If $ t\, ({\rm mod}\, p)\in D^{(p)}_1 $, then $ tQ_1 = tqD^{(p)}_1 = qD^{(p)}_0 = Q_0 $, it follows from Lemma 2.2 (ⅱ) that

$ \sum\limits_{i \in Q_1 }\alpha ^{ti} = \sum\limits_{i \in Q_0 }\alpha^{i} = 1+\sum\limits_{i \in Q_1 }\alpha^{i}. $

The assertions in (ⅲ) and (ⅳ) can be similarly proved, so we omit them here.

Lemma 2.5 Let the symbols be the same as before. For $ t\in Z_{pq}^* $, let $ t\, ({\rm mod}\, p)\in D_i^{(p)} $ and $ t\, ({\rm mod}\, q)\in D_j^{(q)} $, where $ i, j\in \{0, 1\} $. Then $ t\in D_0\cup D_2 $ if and only if $ i = j $, and $ t \in D_1\cup D_3 $ if and only if $ i\neq j $.

Proof Let $ t\in D_k $ with $ k\in \{0, 1, 2, 3\} $. Then there exists a uniquely determined integer $ u_0 $ with $ 0\leq u_0\leq e-1 $ such that $ t\equiv g^{u_0}x^k\, ({\rm mod}\, pq) $. Since $ x \equiv g\, ({\rm mod}\, p) $ and $ x \equiv 1\, ({\rm mod}\, q) $, we have $ t\equiv g^{u_0+k}\equiv g^{(u_0+k)\, ({\rm mod}\, p-1)}\, ({\rm mod}\, p) $ and $ t\equiv g^{u_0}\equiv g^{u_0\, ({\rm mod}\, q-1)}\, ({\rm mod}\, q) $. It is easily verified that $ k $ is even if and only if $ u_0+k $ and $ u_0 $ have the same parity, or equivalently, if and only if $ (u_0+k)\, ({\rm mod}\, p-1) $ and $ u_0\, ({\rm mod}\, q-1) $ have the same parity since $ p-1 $ and $ q-1 $ are both even. Therefore, $ t\, ({\rm mod}\, p) $ and $ t\, ({\rm mod}\, q) $ are either quadratic residues of both $ p $ and $ q $ or quadratic nonresidues of both $ p $ and $ q $, and the desired result for even $ k $ follows immediately from the definition of the classical cyclotomic classes of order 2. The case of odd $ k $ can be proved in the similar way.

Lemma 2.6 Let the symbols be the same as before. Then

$ s_a(\alpha^t) = \left\{ {\begin{array}{*{20}c} {s_a(\alpha)}, \hfill & {t \in D_0}, \hfill \\ {1+s_{a+1}(\alpha), } \hfill & {t \in D_1}, \hfill \\ {1+s_a(\alpha), } \hfill & {t\in D_2}, \hfill \\ {s_{a+1}(\alpha), } \hfill & {t \in D_3}. \hfill \\ \end{array}} \right. $

Proof For $ t\in D_0\cup D_2 $, it follows from Lemma 2.5 that $ t\, ({\rm mod} p) \in D_0^{(p)} $ and $ t\, ({\rm mod} q) \in D_0^{(q)} $ or $ t\, ({\rm mod} p) \in D_1^{(p)} $ and $ t\, ({\rm mod} q) \in D_1^{(q)} $. Then by Lemma 2.4, we always have

$ (\sum\limits_{i \in P_1 }+ \sum\limits_{i \in Q_1 })\alpha^{ti} = (\sum\limits_{i \in P_1 }+ \sum\limits_{i \in Q_1 })\alpha^i. $

For $ t\in D_1\cup D_3 $, it follows from Lemma 2.5 that $ t\, ({\rm mod}\, p) \in D_0^{(p)} $ and $ t\, ({\rm mod}\, q) \in D_1^{(q)} $ or $ t\, ({\rm mod}\, p) \in D_1^{(p)} $ and $ t\, ({\rm mod}\, q) \in D_0^{(q)} $. Then by Lemma 2.4, we always have

$ (\sum\limits_{i \in P_1 }+ \sum\limits_{i \in Q_1 })\alpha^{ti} = 1+(\sum\limits_{i \in P_1 }+ \sum\limits_{i \in Q_1 })\alpha^i. $

Moreover, by Lemma 2.1 we have $ tD_a = D_{a+k}, tD_{a+1} = D_{a+k+1} $ for $ t\in D_{k} $ with $ k\in \{0, 1, 2, 3\} $, so that

$ \, (\sum\limits_{i \in D_a }+ \sum\limits_{i \in D_{a+1}})\, \alpha^{ti} = (\sum\limits_{i \in D_{a+k}}+ \sum\limits_{i \in D_{a+k+1}})\, \alpha^{i}. $

Thus, when $ t\in D_0 $,

$ s_a(\alpha^t) = (\sum\limits_{i \in P_1 }+ \sum\limits_{i \in Q_1 }+ \sum\limits_{i \in D_a }+ \sum\limits_{i \in D_{a+1}})\alpha^{i} = s_a(\alpha); $

when $ t\in D_1 $,

$ s_a(\alpha^t ) = 1+(\sum\limits_{i \in P_1 }+ \sum\limits_{i \in Q_1 }+ \sum\limits_{i \in D_{a+1}}+ \sum\limits_{i \in D_{a+2}})\alpha^{i} = 1+s_{a+1}(\alpha); $

When $ t\in D_2 $, by Lemma 2.2 (ⅲ), we have

$ (\sum\limits_{i \in D_a } + \sum\limits_{i \in D_{a+1}} + \sum\limits_{i \in D_{a+2}} + \sum\limits_{i \in D_{a+3}})\alpha^{i} = \sum\limits_{i \in \mathbb{Z}^*_{pq}}\alpha^i = 1. $

It follows then that

$ s_a(\alpha^t ) = (\sum\limits_{i \in P_1 }+ \sum\limits_{i \in Q_1 }+ \sum\limits_{i \in D_{a+2}}+ \sum\limits_{i \in D_{a+3}})\alpha^{i} = 1+(\sum\limits_{i \in P_1 }+ \sum\limits_{i \in Q_1 }+ \sum\limits_{i \in D_{a}}+ \sum\limits_{i \in D_{a+1}})\alpha^{i} = 1+s_{a}(\alpha). $

By the same arguments, for the case $ t\in D_3 $, we have

$ \begin{eqnarray*} s_a(\alpha^t )& = &1+(\sum\limits_{i \in P_1 }+ \sum\limits_{i \in Q_1 })\alpha^{i}+ (\sum\limits_{i \in D_{a+3}}+ \sum\limits_{i \in D_{a}})\alpha^{i}\\ & = &1+(\sum\limits_{i \in P_1 }+ \sum\limits_{i \in Q_1 })\alpha^{i}+1+(\sum\limits_{i \in D_{a+1}}+ \sum\limits_{i \in D_{a+2}})\alpha^{i}\\ & = &s_{a+1}(\alpha). \end{eqnarray*} $

The proof is completed.

Lemma 2.7 Let the symbols be the same as before. Then

$ s_a(\alpha^t) = \left\{ {\begin{array}{*{20}c} \sum\limits_{i \in P_1 }\alpha ^{ti}, \hfill & {t \in P}, \hfill \\ \sum\limits_{i \in Q_1 }\alpha ^{ti}, \hfill & {t \in Q}. \hfill \\ \end{array}} \right. $

Proof When $ t \in P $, for any $ i \in Q_1 $, $ ti\, ({\rm mod}\, pq) = 0 $, so that

$ \sum\limits_{i \in Q_1 }\alpha^{ti} = |Q_1| = \frac{p-1}{2}\, ({\rm mod}\, 2). $

Then by Lemma 2.3, we get

$ s_a(\alpha^t ) = (\sum\limits_{i \in P_1 }+ \sum\limits_{i \in Q_1 }+ \sum\limits_{i \in D_a}+ \sum\limits_{i \in D_{a+1} })\alpha^{ti}\\ = \sum\limits_{i \in P_1}\alpha^{ti}+(\frac{p-1}{4}+\frac{p-1}{4}+\frac{p-1}{2})\, ({\rm mod}\, 2) = \sum\limits_{i \in P_1 }\alpha ^{ti}. $

When $ t \in Q $, for any $ i \in P_1, $ $ ti\, ({\rm mod}\, pq) = 0 $, it follows that

$ \sum\limits_{i \in P_1 }\alpha^{ti} = |P_1| = \frac{q-1}{2}\, ({\rm mod}\, 2). $

Again by Lemma 2.3, we obtain

$ s_a(\alpha^t ) = (\sum\limits_{i \in P_1 }+ \sum\limits_{i \in Q_1 }+ \sum\limits_{i \in D_2 }+ \sum\limits_{i \in D_3 })\alpha^{ti} = \sum\limits_{i \in Q_1 }\alpha ^{ti}+(\frac{q-1}{4}+\frac{q-1}{4}+\frac{q-1}{2})\, ({\rm mod}\, 2) = \sum\limits_{i \in Q_1 }\alpha ^{ti}. $

Lemma 2.8 For any $ a\in \{0, 1, 2, 3\} $, $ s_a(\alpha) \in \{0, 1\} $ if and only if $ 2\in D_0 $.

Proof If $ 2\in D_0 $, then by Lemma 2.6, $ s_a(\alpha^2) = s_a(\alpha) $ for any $ a\in \{0, 1, 2, 3\} $. Since the characteristic of the field $ GF(2^m) $ is $ 2 $, it follows that $ s_a(\alpha^2) = [s_a(\alpha)]^2 $. Thus we get $ [s_a(\alpha)]^2 = [s_a(\alpha)] $, and so $ s_a(\alpha)\in \{0, 1\} $.

To prove the necessity, we suppose, by way of contradiction, that $ 2\not\in D_0 $.

If $ 2\in D_1 $, then it follows from Lemma 2.6 that $ s_a(\alpha^2) = 1+s_{a+1}(\alpha) $. On the other hand, since $ s_a(\alpha)\in \{0, 1\} $, $ s_a(\alpha) = [s_a(\alpha)]^2 = s_a(\alpha^2) $. Thus $ s_a(\alpha) = 1+s_{a+1}(\alpha) $, which implies $ s_{a+1}(\alpha)\in \{0, 1\} $. By the same argument, $ s_{a+1}(\alpha) = [s_{a+1}(\alpha)]^2 = s_{a+1}(\alpha^2) = 1+s_{a+2}(\alpha), $ and so $ s_{a}(\alpha) = s_{a+2}(\alpha) $. But from (3.2) and Lemma 2.2 (ⅲ), it follows that

$ s_a(\alpha)+s_{a+2}(\alpha) = \sum\limits_{j = a}^{a+3}\sum\limits_{i\in D_j}\alpha^{i} = \sum\limits_{i\in Z_{pq}^*}\alpha^{i} = 1, $

and so we arrive at a contradiction.

If $ 2\in D_2 $, then by Lemma 2.6, $ s_a(\alpha) = [s_a(\alpha)]^2 = s_a(\alpha^2) = 1+s_a(\alpha) $, an obvious contradiction.

Similarly, if $ 2\in D_3 $, then $ s_a(\alpha) = [s_a(\alpha)]^2 = s_a(\alpha^2) = s_{a+1}(\alpha) $ and $ s_{a+1}(\alpha) = [s_{a+1}(\alpha)]^2 = s_{a+1}(\alpha^2) = s_{a+2}(\alpha). $ It follows that $ s_a(\alpha) = s_{a+2}(\alpha) $, a contradiction.

Lemma 2.9 (see [15]) Let the symbols be the same as before. Then

(ⅰ) For any $ t\in P $, $ \sum\limits_{i \in P_1 }\alpha ^{ti}\in \{0, 1\} $ if and only if $ q \equiv \pm 1\, ({\rm mod}\, 8) $.

(ⅱ) For any $ t\in Q, \sum\limits_{i \in Q_1 }\alpha ^{ti}\in \{0, 1\} $ if and only if $ p \equiv \pm 1\, ({\rm mod}\, 8) $.

Lemma 2.10(see [24]) $ 2\in D^{(p)}_0 $ if and only if $ p\equiv\pm 1\, ({\rm mod}\, 8) $.

Now the results on the linear complexity of the sequences defined by (2.3) are summarized in the following three theorems.

Theorem 2.11 Let $ p \equiv 1\, ({\rm mod}\, 8) $ and $ q \equiv-3\, ({\rm mod}\, 8). $ Then $ L(s^\infty) = \frac{2pq-p-1}{2} $.

Proof By eq.(3.3), it suffices to count the number of roots in $ \{\alpha^j\, :\, j = 0, 1, \cdots, pq-1\} $ of $ s_a(x) $. For $ t\in R = \{0\} $, it is easily verified that

$ s_a(\alpha^t) = \frac{pq-1}{2}({\rm mod}\, 2) = 0. $

Since $ p \equiv 1\, ({\rm mod}\, 8) $ and $ q \equiv -3\, ({\rm mod}\, 8) $, it follows from Lemma 2.10 that $ 2 \in D_0^{(p)} $ and $ 2 \in D^{(q)}_1 $, and so $ 2 \in D_1\cup D_3 $ by Lemma 2.5. Thus $ s_a(\alpha^t)\neq 0 $ for any $ t\in \mathbb{Z}_{pq}^* $ by Lemma 2.6 and Lemma 2.8. In addition, for any $ t\in P $ we have $ s_a(\alpha^t)\neq 0 $ by Lemma 2.7 and Lemma 2.9 (ⅰ), but for any $ t\in Q $ we have $ s_a(\alpha^t) = \sum\limits_{i \in Q_1 }\alpha ^{ti}\in \{0, 1\} $ by Lemma 2.7 and Lemma 2.9 (ⅱ). We now distinguish the cases $ t\in Q_0 $ and $ t\in Q_1 $. It is obvious $ \sum\limits_{i\in Q_1 }\alpha^{ti} = \sum\limits_{i\in D_1^{(p)}}(\alpha^{q^2})^{i} $ when $ t \in Q_0 $ and $ \sum\limits_{i\in Q_1 }\alpha^{ti} = \sum\limits_{i\in D_0^{(p)}}(\alpha^{q^2})^{i} $ when $ t \in Q_1 $. Since

$ \sum\limits_{i \in D_1^{(p)}}(\alpha^{q^2})^{i} +\sum\limits_{i \in D_0^{(p)}}(\alpha^{q^2})^{i} = \sum\limits_{i = 1}^{p-1}(\alpha^{q^2})^{i} = 1, $

it follows that $ s_a(\alpha^t) = 0 $ either for all $ t\in Q_0 $ or for all $ t\in Q_1 $. In conclusion, the size of the set $ \{s_a(\alpha^t) = 0\, :\, t\in\mathbb{Z}_{pq}\} $ is $ \frac{p-1}{2}+1 $, then by (3.3) we get that $ L(s^\infty) = pq-\frac{p-1}{2}-1 = \frac{2pq-p-1}{2}. $

Theorem 2.12 Let $ p \equiv -3\, ({\rm mod}\, 8) $ and $ q \equiv 1\, ({\rm mod}\, 8) $. Then $ L(s^\infty) = \frac{2pq-q-1}{2} $.

Proof When $ p \equiv -3\, ({\rm mod}\, 8) $ and $ q \equiv 1\, ({\rm mod}\, 8) $, we have $ 2 \in D_1\cup D_3 $ by Lemma 2.5, and hence $ s_a(\alpha^t)\neq 0 $ for any $ t\in \mathbb{Z}_{pq}^* $ by Lemma 2.6 and Lemma 2.8. By the same arguments as in Theorem 2.11, $ s_a(\alpha^t)\neq 0 $ for any $ t\in Q $ and $ s_a(\alpha^t) = 0 $ for half of $ t\in P $. Therefore, by (3.3) we have $ L(s^\infty) = pq-\frac{q-1}{2}-1 = \frac{2pq-q-1}{2}. $

Theorem 2.13 Let $ p \equiv -3\, ({\rm mod}\, 8) $ and $ q \equiv -3\, ({\rm mod}\, 8) $. Then

$ L(\textbf{s}^\infty) = \left\{{\begin{array}{*{20}c} \frac{pq+p+q-3}{2}, \hfill & {2 \in D_0}, \hfill \\ pq-1, \hfill & {2 \notin D_0}. \hfill \\ \end{array}} \right. $

Proof Since $ p \equiv -3\, ({\rm mod}\, 8) $ and $ q \equiv -3\, ({\rm mod}\, 8) $, it follows from Lemmas 2.7 and 2.9 that $ s_a(\alpha^t)\neq 0 $ for any $ t\in P $ and $ t\in Q $.

If $ 2\in D_0 $, then $ s_a(\alpha^t) = 0 $ for half of $ t\in \mathbb{Z}_{pq}^* $ by Lemma 2.6. If $ 2\notin D_0 $, then $ s_a(\alpha^t)\neq 0 $ for any $ t\in \mathbb{Z}_{pq}^* $ by Lemma 2.6. So the desired result follows immediately from (3.3).

In this paper, new class of almost balanced binary sequences of period $ pq $ is constructed via Whiteman's generalized cyclotomy of order 4 and classic cyclotomy of order 2. The linear complexity of these sequences is determined. The results show that the proposed sequences have large linear complexity. In addition, since the parameter $ a $ in the characteristic set could be any integers in the range of $ 0 $ to $ 3 $, our construction can generate a number of binary sequences with large linear complexity.