The shift-based scaling and recursing algorithm for evaluating the action of the matrix $\varphi$-functions

1.   Introduction

The linear complexity and the $k$-error linear complexity are important cryptographic characteristics of stream cipher sequences. The linear complexity of an $N$-periodic sequence $s = \{s_u\}^\infty_{u = 0}$, denoted by $LC(s)$, is defined as the length of the shortest linear feedback shift register (LFSR) that generates it ^[1]. With the Berlekamp-Massey (B-M) algorithm ^[2], if $LC(s)\geq N/2$, then $s$ is regarded as a good sequence with respect to its linear complexity. For an integer $k\geq0$, the $k$-error linear complexity $LC_k(s)$ is the smallest linear complexity that can be obtained by changing at most $k$ terms of $s$ in the first period and periodically continued ^[3]. The cryptographic background of the $k$-error linear complexity is that some key streams with large linear complexity can be approximated by some sequences with much lower linear complexity ^[2]. For a sequence to be cryptographically strong, its linear complexity should be large enough, and its $k$-error linear complexity should be close to the linear complexity.

The relationship between the linear complexity and the DFT of the sequence was given by Blahut in ^[4]. Let $m$ be the order of 2 modulo an odd number $N$. For a primitive $N$-th root $\beta\in\mathbb{F}_{2^m}$ of unity, the DFT of $s$ is defined by

Then

where $W_H(A)$ is the hamming weight of the sequence $A$. The polynomial

is called the Mattson-Solomon polynomial (M-S polynomial) of $s$ ^[5]. It can be deduced from Eqs (1.2)and (1.3) that the linear complexity of $s$ is equal to the number of the nonzero terms of $G(X)$, namely

By the inverse DFT,

There are many studies about two-prime generators. In 1997–1998, Ding calculated the linear complexity and the autocorrelation values of binary Whiteman generalized cyclotomic sequences of order two ^[6,7]. In 2013, Li defined a new generalized cyclotomic sequence of order two of length $pq$, which is based on Whiteman generalized cyclotomic classes, and calculated its linear complexity ^[8]. In 2015, Wei determined the $k$-error linear complexity of Legendre sequences for $k = 1, 2$ ^[9]. In 2018, Hofer and Winterhof studied the 2-adic complexity of the two-prime generator of period $pq$ ^[10]. Alecu and Sălăgean transformed the optimisation problem of finding the $k$-error linear complexity of a sequence into an optimisation problem in the DFT domain, by using Blahut's theorem in the same year ^[11]. In 2019, in terms of the DFT, Chen and Wu discussed the $k$-error linear complexity for Legendre, Ding-Helleseth-Lam, and Hall's sextic residue sequences of odd prime period $p$ ^[12]. In 2020, Zhou and Liu presented a type of binary sequences based on a general two-prime generalized cyclotomy, and derived their minimal polynomial and linear complexity ^[13]. In 2021, the autocorrelation distribution and the 2-adic complexity of generalized cyclotomic binary sequences of order 2 with period $pq$ were determined by Jing ^[14].

This paper is organized as follows. Firstly, we present some preliminaries about Whiteman generalized cyclotomic classes and the linear complexity in Section 2. In Section 3, we give main results about the linear complexity of Whiteman generalized cyclotomic sequences of order two. In Section 4, we give the 1-error linear complexity of these sequences. At last, we conclude this paper in Section 5.

2.   Preliminaries

Let $p$ and $q$ be two distinct odd primes with $\mbox{gcd}(p-1, q-1) = 2$, and $N = pq$, $e = (p-1)(q-1)/2$. By the Chinese Remainder Theorem, there is a fixed common primitive root $g$ of both $p$ and $q$ such that $\mbox{ord}_N(g) = e$. Let $x$ be an integer satisfying

Then the set

for $i = 0, 1$ is called a Whiteman generalized cyclotomic class of order two ^[15].

As pointed out in ^[14], the unit group of the ring $Z_N$ is

Let $P = \{p, 2p, \cdots, (q-1)p\}$, $Q = \{q, 2q, \cdots, (p-1)q\}$ and $R = \{0\}$. Then $Z_N = Z_N^*\cup P\cup Q \cup R$. The sequence $s(a, b, c) = \{s_u\}^\infty_{u = 0}$ over $\mathbb{F}_2$ is defined by

where $(\frac{\cdot}{\cdot})$ denotes the Legendre symbol and $a, b, c\in \mathbb{F}_2$ ^[14].

Lemma 2.1. ^[7] $-1\in D_1$, if $|p-q|/2$ is odd; and $-1\in D_0$, if $|p-q|/2$ is even.

Lemma 2.2. ^[6]

Lemma 2.3. ^[6] (1) If $a\in P$, then $aP = P$ and $aQ = R$.

(2) If $a\in Q$, then $aP = R$ and $aQ = Q$.

(3) If $a\in D_i$, then $aP = P$, $aQ = Q$, and $aD_j = D_{(i+j)\bmod 2}$, where $i, j = 0, 1$.

It was shown in ^[6] that, for a primitive $N$-th root $\beta\in\mathbb{F}_{2^m}$ of unity, we have

and

Lemma 2.4. ^[6]

Actually, if $p\equiv -1(\bmod 8)$ or $p\equiv 3(\bmod 8)$, then $(p-1)/2 = 1$; if $p\equiv 1(\bmod 8)$ or $p\equiv -3(\bmod 8)$, then $(p-1)/2 = 0$. By symmetry, if $q\equiv -1(\bmod 8)$ or $q\equiv 3(\bmod 8)$, then $(q-1)/2 = 1$; if $q\equiv 1(\bmod 8)$ or $q\equiv -3(\bmod 8)$, then $(q-1)/2 = 0$.

Lemma 2.5. Define

Then for $\beta$, we have $D_0(\beta) = 0$ and $D_1(\beta) = 1$ if $2\in D_0$; $D_0(\beta) = \omega$ and $D_1(\beta) = 1+\omega$ if $2\in D_1$, where $\omega\in\mathbb{F}_4\setminus\mathbb{F}_2$.

Proof. (1) If $2\in D_0$, by Lemma 2.3 we have

(2) If $2\in D_1$, by Lemma 2.3 we have

Hence $D_i(\beta)\in\mathbb{F}_4\setminus\mathbb{F}_2$.

And by Eq (2.1), we have $D_0(\beta)\neq D_1(\beta)$ and $D_0(\beta)+D_1(\beta) = 1$. Assume that $D_0(\beta) = 0$, $D_1(\beta) = 1$ for $2\in D_0$, and $D_0(\beta) = \omega$, $D_1(\beta) = 1+\omega$ for $2\in D_1$, where $\omega\in\mathbb{F}_4\setminus\mathbb{F}_2$.

3.   The linear complexity of $s(a, b, c)$

Let $LC(s(a, b, c))$ be the linear complexity of $s(a, b, c)$, and the other symbols be the same as before.

Theorem 3.1. Let $p\equiv v(\bmod 8)$ and $q\equiv w(\bmod 8)$, where $v, w = \pm1, \pm3$. Then the linear complexity of $s(a, b, c)$ respect to different values of $p$ and $q$ is as shown as Table 1.

Proof. We provide the process of calculating $LC(s(0, 0, 0))$ when $v = -1$ and $w = -3$, and can prove other cases in a similar way.

By Lemmas 2.1–2.3 and Eq (1.1), we have $-1\in D_1$, $2\in D_1$, then

and $\rho_0 = 0$. By Eq (1.3), we have

Let $t = iu$. Then by Lemmas 2.3–2.5, we have

By Eq (1.4) we can get the linear complexity of $s(0, 0, 0)$ as

Actually, the linear complexity of $s(1, 0, 0)$ was studied by Ding in ^[6] with its minimal polynomial.

4.   The 1-error linear complexity of $s(a, b, c)$

Let $LC_k(s(a, b, c))$ be the $k$-error linear complexity of $s(a, b, c)$, $\tilde{s} = \{\tilde{s}_u\}^\infty_{u = 0}$ be the new sequence obtained by changing at most $k$ terms of $s$, that $\tilde{s} = s+e$, where $e = \{e_u\}^\infty_{u = 0}$ is an error sequence of period $N$. Ding has provided in ^[2] that, the $k$-error linear complexity of a sequence can be expressed as

It is clearly that $LC_0(s) = LC(s)$ and

where $l = W_H(s)$.

Let $G(X)$, $G_k(X)$ and $\tilde{G}(X)$ be the M-S polynomials of $s$, $e$ and $\tilde{s}$ respectively. Note that

where $\rho_i$, $\eta_i$ and $\xi_i$ are the DFTs of $s$, $e$ and $\tilde{s}$ respectively. By Eqs (1.5), (4.1) and (4.2), we have $\tilde{G}(X) = G(X)+G_k(X)$, then

Assume that $e_{u_0} = 1$ for $0\leq u_0\leq N-1$ and $e_u = 0$ for $u\neq u_0$ in the first period of $e$. Then the DFT of $e$ is

Specially, if $u_0 = 0$, then $\eta_i = 1$ for all $0\leq i\leq N-1$; otherwise, $\eta_0 = 1$ and the order of $\eta_i$ is $N$ for $1\leq i\leq N-1$.

Theorem 4.1. Let $p\equiv v(\bmod 8)$ and $q\equiv w(\bmod 8)$, where $v, w = \pm1, \pm3$, and the other symbols be the same as before. Then the 1-error linear complexity of $s(a, b, c)$ is as shown as Table 2.

Proof. We consider the case $v = -1, w = -3$ for $LC_1(s(0, 0, 0))$. By Lemmas 2.1–2.5 and Eq (1.1), we have $-1\in D_1$, $2\in D_1$ and

Then by Eq (4.2), we can get

According to Lemma 2.3, we can get the following results.

(1) If $u_0 = 0$, then

(2) If $u_0\in Q$, then

(3) If $u_0\in D_0$ or $u_0\in D_1$ or $u_0\in P$, then

Compare the results of Cases (1)–(3) with $LC(s(0, 0, 0)) = pq-p$. If $p > q$, then $pq-p < pq-q+1 < pq$; if $p < q$, then $pq-q+1 < pq-p < pq$. Hence

Similarly we can prove the other cases for $LC_1(s(a, b, c))$.

All results of $LC(s(a, b, c))$ and $LC_1(s(a, b, c))$ in Sections 3 and 4 have been tested by MAGMA program.

5.   Conclusions

The purpose of this paper is to determine the linear complexity and the 1-error linear complexity of $s(a, b, c)$. In most of the cases, $s(a, b, c)$ possesses high linear complexity, namely $LC(s(a, b, c)) > N/2$, consequently has decent stability against 1-bit error. Notice that the linear complexity of some of the sequences above is close to $N/2$. Then the sequences can be selected to construct cyclic codes by their minimal generating polynomials with the method introduced by Ding ^[16].

Acknowledgments

This work was supported by Fundamental Research Funds for the Central Universities (No. 20CX05012A), the Major Scientific and Technological Projects of CNPC under Grant (No. ZD2019-183-008), the National Natural Science Foundation of China (Nos. 61902429, 11775306) and Shandong Provincial Natural Science Foundation of China (ZR2019MF070).

Conflict of interest

The authors declare that they have no conflicts of interest.