The linear complexity of generalized cyclotomic binary sequences of period $p^n$

Abstract

This paper examines the linear complexity of a family of generalized cyclotomic binary sequences of period $p^n$ recently proposed by Xiao et al. (Des Codes Cryptogr, 2017, https://doi.org/10.1007/s10623-017-0408-7), where a conjecture about the linear complexity in the special case that $f=2^r$ for a positive integer r was made. We prove the conjecture and also extend the result to more general even integers f.

1 Introduction

Pseudo-random sequences used for stream ciphers are required to have the property of unpredictability. Linear complexity is one of the main components that indicate 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 [11]. 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.

Cyclotomy is an old topic of elementary number theory and is related to difference sets, sequences, coding theory and cryptography [4]. In the past decades generalized cyclotomy has been extensively studied [4, 5, 10, 19, 25]. Whiteman [19] introduced a generalized cyclotomy with respect to pq, which was extended with respect to odd integers in [5]. Whiteman’s generalized cyclotomy is not consistent with classical cyclotomy. A new generalized cyclotomy that includes classical cyclotomy as a special case was later introduced by Ding and Helleseth [4]. A unified approach that determines both of the Whiteman and Ding-Helleseth generalized cyclotomy was proposed by Fan and Ge [10]. Recently another construction was presented in [25], where the order of the generalized cyclotomic classes depends on the choice of parameters.

Classical and generalized cyclotomies have been used in the construction of cyclic codes [3, 15] and sequences [2, 4, 7] with desirable properties. In recent years there has been some research on generalized cyclotomic binary and non-binary sequences of period $p^n$ [1, 7, 8, 16, 20, 23] (see also references therein). Based on the generalized cyclotomic classes in [25], Xiao et al. presented a new family of cyclotomic binary sequences of period $p^n$ and determined the linear complexity of the sequences in the case that $n=2$ and $f=2^r$ for a positive integer r [22]. As the exponent n increases, the experimental result indicates that the linear complexity of this family of sequences is very close to $p^n$. Based on this observation, the authors of [22] made a conjecture about the linear complexity for any positive integer n and even integer $f=2^r$. In this paper, we revisit the conjecture and prove it based on a detailed investigation of some polynomials over certain extension fields of $\mathbb { F}_2$. With the help of this new technique, we also extend the conjectured result from the special case $f=2^r$ to more general even integers f.

The remainder of this paper is organized as follows. In Sect. 2 we introduce some basics and recall the generalized cyclotomic sequences and the conjecture in [22]. Section 3 is dedicated to the study of the linear complexity of this family of cyclotomic sequences. Section 4 concludes the work in this paper.

2 Preliminaries

Throughout this paper, we will denote by $\mathbb {Z}_N$ the ring of integers modulo N for a positive integer N, and by $\mathbb {Z}_N^{*}$ the multiplicative group of $\mathbb {Z}_N$, namely, $\mathbb {Z}_N^{*} = \{ x \in \mathbb {Z}_N\,|\, \gcd (x, N) = 1\}$.

In the following we will recall some basics of the linear complexity of a periodic sequence and introduce the generalized cyclotomic sequences proposed in [22].

2.1 Linear complexity

Let $s^\infty =(s_0,s_1,s_2,\dots )$ be a binary sequence of period N and $S(x) = s_0 + s_1x +\cdots + s_{N-1}x^{N-1}$. It is well known (see, for instance, [2, p. 171]) that the minimal polynomial of $s^{\infty }$ is given by

$$\begin{aligned} (x^N-1)\big / \gcd \big (x^N-1, S(x)\big ) \end{aligned}$$

and the linear complexity of $s^\infty$ is given by

$$\begin{aligned} L=N-\deg \Big (\gcd \big (x^{N}-1,S(x)\big )\Big ). \end{aligned}$$

This formula allows one to determine the linear complexity of $s^{\infty }$ by examining the roots of S(x) in an extension of $\mathbb { F}_2$ (the finite field of two elements). More specifically, the linear complexity of $s^\infty$ can be given by

$$\begin{aligned} L=N-\Big |\big \{i \in \mathbb {Z}_N \,|\, S(\beta ^i)=0 \big \}\Big |, \end{aligned}$$

(1)

where $\beta$ is a primitive Nth root of unity in an extension field of $\mathbb { F}_2$.

2.2 New generalized cyclotomic sequences

Let p be an odd prime and $p=ef+1$, where e, f are positive integers. Let g be a primitive root modulo $p^2$. It is well known [12] that g is also a primitive root modulo $p^j$ for each integer $j\ge 1$, namely, the order of g modulo $p^j$ is equal to $\varphi (p^j)=p^{j-1}(p-1)$, where $\varphi (\cdot )$ is the Euler’s totient function. Below we recall the generalized cyclotomic classes introduced in [25] and the cyclotomic sequences proposed in [22].

Let n be a positive integer. For $j=1, 2,\ldots , n$, denote $d_j=\varphi (p^j)/e=p^{j-1}f$ and define

$$\begin{aligned} D^{(p^j )}_0&= \left\{ g^{t\cdot d_ j}~(\bmod {p^j}) \,|\, 0\le t< e \right\} , \text { and } \nonumber \\ D^{(p^j )}_ i&= g^i D^{(p^j )}_0 = \left\{ g^i x~(\bmod {p^j}) : x \in D^{(p^j )}_0\right\} , \quad 1\le i <d_j. \end{aligned}$$

(2)

The cosets $D^{(p^j )}_ i$, $i=0, 1, \ldots , d_j-1$, are called generalized cyclotomic classes of order $d_ j$ with respect to $p^j$. It was shown in [25] that $\left\{ D^{(p^j )}_ 0, D^{(p^j )}_ 1,\dots ,D^{(p^j)}_ {d_j-1}\right\}$ forms a partition of $\mathbb {Z}^{*}_{p^j}$ for each integer $j \ge 1$ and for an integer $m\ge 1$,

$$\begin{aligned} \mathbb {Z}_{p^m}=\bigcup _{j=1}^{m} \bigcup _{i=0}^{d_j-1} p^{m-j}D^{(p^j )}_ i \cup \{0\}. \end{aligned}$$

Based on the above generalized cyclotomic classes, a family of almost balanced binary sequences was proposed in [22], where f is chosen to be $2^r$ for a positive integer r. Indeed, the construction of the sequence in [22] can be naturally extended to any even integer f as follows.

Let f be a positive even integer and b an integer with $0\le b < p^{n-1} f$. Define two sets

$$\begin{aligned} \mathscr {C}_0^{(p^n)}&=\bigcup _{j=1}^{n} \bigcup _{i=d_j/2}^{d_j-1} p^{n-j}D^{(p^j )}_ {(i+b)\pmod {d_j}}, \text {and }\nonumber \\ \mathscr {C}_1^{(p^n)}&=\bigcup _{j=1}^{n} \bigcup _{i=0}^{d_j/2-1} p^{n-j}D^{(p^j )}_ {(i+b)\pmod {d_j}}\cup \{0\}. \end{aligned}$$

(3)

It is obvious that $\mathbb {Z}_{p^n}=\mathscr {C}_0^{(p^n)} \cup \mathscr {C}_1^{(p^n)}$ and $|\mathscr {C}_1^{(p^n)}|=(p^n+1)/2$. A family of almost balanced binary sequences $s^\infty =(s_0,s_1,s_2,\dots )$ of period $p^n$ can thus be defined as

$$\begin{aligned} s_i ={\left\{ \begin{array}{ll} 0,&{}\text { if } i~(\bmod ~p^n) \in \mathscr {C}_0^{(p^n)}, \\ 1,&{}\text { if } i~(\bmod ~p^n) \in \mathscr {C}_1^{(p^n)}. \\ \end{array}\right. } \end{aligned}$$

(4)

In the case of $f=2^r$, the linear complexity of $s^\infty$ for $n=2$ was determined in [22], where a conjecture about the linear complexity of $s^\infty$ for any integer $n\ge 3$ was also made as follows.

Conjecture 1

[22] Let $s^\infty$ be a generalized cyclotomic binary sequence of period $p^n$ defined by (4). If $2^{(p-1)} \not \equiv 1~(\bmod ~p^2)$ and $f=2^r$, where r is a positive integer, then the linear complexity of $s^\infty$ is given by

$$\begin{aligned} L ={\left\{ \begin{array}{ll} p^n-\frac{p-1}{2}-\delta \left( \frac{p^n+1}{2}\right) ,&{}\text { if } 2 \in D^{(p)}_0, \\ p^n-\delta \left( \frac{p^n+1}{2}\right) ,&{}\text { if } 2 \not \in D^{(p)}_0, \\ \end{array}\right. } \end{aligned}$$

where $\delta (t) = 1$ if t is even and $\delta (t) = 0$ if t is odd.

In the next section we will revisit Conjecture 1 and develop a new technique to prove it. It turns out that the new technique also works for other even integers f and leads to more general result.

3 Linear complexity of generalized cyclotomic sequences

In this section, we will first give some subsidiary lemmas, and then investigate the linear complexity of $s^\infty$ defined in (4). The main result will be presented in Sect. 3.2.

3.1 Subsidiary lemmas

An odd prime p satisfying $2^{p-1}\equiv 1 \pmod {p^2}$ is known as a Wieferich prime. It is shown in [6] that there are only two Wieferich primes 1093 and 3511 up to $6.7\times 10^{15}$. In this paper we will only focus on non-Wieferich primes.

For a non-Wieferich prime p with $2^{p-1}\not \equiv 1 \pmod {p^2}$, some properties related to $2\pmod {p^j}$ for integers $j\ge 1$ are discussed below.

Lemma 1

Let p be a non-Wieferich prime and let $2 \equiv g^u~(\bmod ~p^2)$ for some integer u. Then $\gcd (u, p) = 1$.

Proof

Suppose $\gcd (u, p) \ne 1$, namely, p|u. Then $2^{p-1} \equiv g^{u(p-1)} \equiv 1~(\bmod ~p^2)$. This contradicts the condition that p is a non-Wieferich prime. $\square$

Lemma 2

Let p be a non-Wieferich prime and $\tau ={\text {ord}}_p(2)$ be the order of 2 modulo p. Then the order of 2 modulo $p^j$ for an integer $j\ge 1$ is $\tau p^{j-1}$.

Proof

The statement for $j=1$ is trivial and we only need to consider the case that $j\ge 2$. Since p is a non-Wieferich prime and $\tau$ is the order of 2 modulo p, there exists an integer t such that $2^{\tau }=1+pt$ with $\gcd (p,t)=1$.

Let $\sigma$ be the order of 2 modulo $p^j$, namely, $\sigma$ is the least positive integer satisfying $2^{\sigma } \equiv 1 \pmod {p^{j}}$. By the properties of binomial coefficients,

$$\begin{aligned} 2^{\tau p^{j-1}} = (1+pt)^{p^{j-1}} \equiv 1 \pmod {p^j}. \end{aligned}$$

This implies $\sigma \, |\, \tau p^{j-1}$. On the other hand, it is clear that $\tau$ divides $\sigma$. Denote $\sigma =\tau d p^l$, where $\gcd (p,d)=1$ and $l\ge 0$. Again by the properties of binomial coefficients we have

$$\begin{aligned} 2^{\sigma } =2^{\tau d p^l}= (1+pt)^{dp^l}\equiv 1+dtp^{l+1}\pmod {p^{l+2}}. \end{aligned}$$

Since $\gcd (dt, p)=1$, it follows that $2^{\sigma } \pmod {p^j} = 1$ if and only if $l+1 \ge j$. Hence $\tau p^{j-1}$ divides $\sigma =\tau d p^l$. From the above analysis the desired conclusion follows. $\square$

Let $\overline{\mathbb {F}}_2$ be the algebraic closure of $\mathbb {F}_2$ and $\alpha _n \in \overline{\mathbb {F}}_2$ be a primitive $p^n$th root of unity. Denote $\alpha _j=\alpha _n^{p^{n-j}},\, j=1,2\dots ,n-1$. Then $\alpha _j$ is a primitive $p^j$th root of unity in an extension field of $\mathbb {F}_2$. As usual, we denote by $\mathbb {F}_2(\alpha _j)$ a simple extension of $\mathbb {F}_2$ obtained by adjoining an algebraic element $\alpha _j$ [18]. The dimension of the vector space $\mathbb {F}_2(\alpha _j)$ over $\mathbb {F}_2$ is called the degree of $\mathbb {F}_2(\alpha _j)$ over $\mathbb {F}_2$, in symbols $[\mathbb {F}_2(\alpha _j): \mathbb {F}_2]$.

Lemma 3

For a non-Wieferich prime p, we have

$$\begin{aligned}{}[\mathbb {F}_2(\alpha _{j+1}): \mathbb {F}_2(\alpha _j)]=p,\quad j=1, 2, \ldots , n-1, \end{aligned}$$

where $\alpha _j=\alpha _n^{p^{n-j}}$ and $\alpha _n$ is a primitive $p^n$th root of unity.

Proof

It is well known [18] that if $\mathbb { F}$ is a finite extension of $\mathbb {F}_2$, then $|\mathbb { F}|=2^{[\mathbb { F} : \mathbb {F}_2]}$ and the order of any nonzero element $\mathbb { F}$ divides $|\mathbb { F}|-1$. Let $\tau$ be the order of 2 modulo p. It follows from Lemma 2 that $2^{\tau p^{j-1}} \equiv 1\pmod {p^{j}}$ and $2^{\tau p^{j-1}} \not \equiv 1\pmod {p^{j+1}}$ for any integer $j\ge 1$, which implies $\alpha _{j} \in \mathbb {F}_{2^{\tau p^{j-1}}}$ and $\alpha _{j+1} \not \in \mathbb {F}_{2^{\tau p^{j-1}}}$. That is to say, $[\mathbb {F}_2(\alpha _{j}) : \mathbb {F}_{2}]= \tau p^{j-1}$ for $j=1, 2, \ldots , n$. The desired result immediately follows. $\square$

The following lemma discusses some of the basic properties of the generalized cyclotomic classes defined in (2). Despite the simplicity, the proof is included here for completeness.

Lemma 4

For $D_i^{(p^j)}$ defined as in (2), we have

• (i) $aD^{(p^j)}_i = D^{(p^j)}_{ i+k \pmod {d_j}}$ for $a \in D^{(p^j)}_k$; and

• (ii) $D^{(p^j )}_ i\pmod {p^l} = D^{(p^l )}_{i \pmod {d_l}}$ for $1\le l \le j$.

Proof

• (i) By the definition in (2), any element a in $D^{(p^j)}_k$ can be written as $a = g^{k+t_0d_j}$ for some integer $t_0$ with $0\le t_0<e$. Thus,

  $$\begin{aligned} aD^{(p^j)}_i = \left\{ g^{k+t_0d_j}\cdot g^{i+td_j} \,|\, 0\le t<e \right\} = \left\{ g^{{i+k}\,(\text {mod}\,{d_j})} \cdot g^{t'd_j}\,|\, 0\le t'< e \right\} = D_{i+k\,(\text {mod}\,{d_j})}^{(p^j)}. \end{aligned}$$

• (ii) For any positive integer l with $l\le j$, since g is also a primitive root modulo $p^l$, one has

  $$\begin{aligned} g^{d_j}\,(\text {mod}\,{p^l})= g^{(p^{l-1}(p^{j-l}-1) + p^{l-1})f}\,\text {mod}{p^l}) = g^{d_l}\,(\text {mod}\,{p^l}), \end{aligned}$$

  whence

  $$\begin{aligned} g^{i + d_jt}\,(\text {mod}\,{p^l}) = g^{i\,(\text {mod}\,{d_l}) + t_i d_l + td_j} \,(\text {mod}\,{p^l}) = g^{i\,(\text {mod}\,{d_l}) + t' d_l} \,(\text {mod}\,{p^l}). \end{aligned}$$

  The desired result thus follows.

$\square$

The above auxiliary lemmas will be heavily used in our investigation of the linear complexity of $s^{\infty }$ in the next subsection.

3.2 Main result

This subsection will investigate the linear complexity of $s^{\infty }$ defined in (4) for some even integers f. The main result in this paper is given as follows.

Theorem 5

Let $p=ef+1$ be an odd prime with $2^{p-1}\not \equiv 1 \pmod {p^2}$ and f being an even positive integer. Let $s^\infty$ be the generalized cyclotomic binary sequence of period $p^n$ defined in (4). Let ${\text {ord}}_p(2)$ denote the order of 2 modulo p and $v=\gcd \big (\frac{p-1}{\mathrm{ord}_p(2)}, f\big )$. Then the linear complexity of $s^{\infty }$ is given by

$$\begin{aligned} \begin{array}{c} L = p^n - r\cdot \mathrm{ord}_p(2) -\delta \big (\frac{p^n+1}{2}\big ), \quad 0\le r \le \frac{p-1}{2\mathrm{ord}_p(2)}, \end{array} \end{aligned}$$

where $\delta (t) = 1$ if t is even and $\delta (t) = 0$ if t is odd. Furthermore,

• (i) for $p\equiv \pm 3 \pmod {8}$, the linear complexity $L=p^n-\delta \big (\frac{p^n+1}{2}\big )$; and

• (ii) for $p\equiv \pm 1 \pmod {8}$, the linear complexity

  $$\begin{aligned} L = {\left\{ \begin{array}{ll} p^n-\frac{p-1}{2}-\delta \big (\frac{p^n+1}{2}\big ), &{} \text { if }\, v = f ; \\ p^n-\delta \big (\frac{p^n+1}{2}\big ), &{} \text { if }\, v | \frac{f}{2}, \text { or } v=2 \text { and } v\ne f. \end{array}\right. } \end{aligned}$$

Remark 1

Suppose $2\equiv g^u \pmod {p}$ for some integer u. It is easily seen that $\gcd \big (\frac{p-1}{\mathrm{ord}_p(2)}, f\big )=\gcd (u, f)$. Thus the condition $2\in D_0^{(p)}$ in Conjecture 1 is equivalent to $v=\gcd \big (\frac{p-1}{\mathrm{ord}_p(2)}, f\big ) = f$. In the case that $f=2^r$ for a positive integer r, the integer v is also a power of 2, which either equals f or divides f / 2. Hence Conjecture 1 is included in Theorem 5 as a special case.

Remark 2

A recent paper [24] studied the linear complexity of a family of generalized cyclotomic sequences and also proved Conjecture 1. The authors of [24] pointed out that their work is significantly different from the early version [9] of this paper with respect to the sequences in consideration and the technique used in the computation of linear complexity. When the sequences in the two papers are the same, the explicit result obtained in [24] is a special case of Theorem 5.

Remark 3

Given an odd prime p with $p\equiv \pm 1 \pmod {8}$, one can flexibly choose a number of even integers f satisfying the conditions in Theorem 5 (ii) according to the parity of $\frac{p-1}{{\text {ord}}_p(2)}$ as follows.

• (i) If ${\text {ord}}_p(2)$ is even, then any integer f with $\nu _2(f) > \nu _2(\frac{p-1}{{\text {ord}}_p(2)})$ will satisfy the condition $v\, |\, \frac{f}{2}$, where $\nu _2(t)$ denotes the exponent of the largest power of 2 dividing an integer t. In particular, when 2 is a primitive root modulo p, any even integer f satisfies the condition.

• (ii) If ${\text {ord}}_p(2)$ is odd, then any even integer $f=2f_1$ with $\gcd (\frac{p-1}{{\text {ord}}_p(2)}, f_1)=1$ will satisfy the condition $v = 2$.

On the other hand, when an even integer f is not covered by Theorem 5 (ii), the experimental result indicates that the linear complexity of $s^{\infty }$ varies for different choices of f (see, e.g., Example 2).

Before we start with the proof of Theorem 5, we need to introduce some polynomials derived from the sequence $s^{\infty }$ and investigate their properties.

Let $S(x)=s_0+s_1x+\cdots +s_{p^n-1}x^{p^n-1}$ for the generalized cyclotomic sequences $s^{\infty }$ defined in (4) . Then,

$$\begin{aligned} S(x) = \sum \limits _{i=0}^{p^n-1} s_ix^i = \sum \limits _{t\in \mathscr {C}_1^{(p^n)}} x^t = 1 + \sum \limits _{j=1}^n\sum \limits _{i=0}^{d_j/2-1}\sum _{t \in D^{(p^j)}_{i+b \pmod {d_j}}} x^{p^{n-j}t}. \end{aligned}$$

(5)

For simplicity of presentation, we define polynomials

$$\begin{aligned} E^{(p^j)}_i(x) =\sum _{t \in D^{(p^j)}_i} x^t, \quad 1\le j \le n, \, 0\le i<d_j, \end{aligned}$$

(6)

and

$$\begin{aligned} H^{(p^j)}_{k}(x)&=\sum _{i=0}^{ d_j/2-1} E^{(p^j)}_{i+k\pmod {d_j}} (x), \quad 0\le k < d_j,\nonumber \\ T^{(p^m)}_{k }(x)&=\sum \limits _{j=1}^{m}H^{(p^j)}_{k}(x^{p^{m-j}}), \quad m=1, 2, \ldots , n. \end{aligned}$$

(7)

Notice that the subscripts i in $D^{(p^j)}_i$, $H^{(p^j)}_i(x)$ and $T^{(p^j)}_i(x)$ are all taken modulo the order $d_j$. In the rest of this paper the modulo operation will be omitted when no confusion can arise.

It can be easily seen from (5)–(7) that $S(x) = 1 + T^{(p^n)}_b(x)$. By (1) the linear complexity of $s^{\infty }$ in (4) can thus be given by

$$\begin{aligned} L=N-\left| \big \{i \in \mathbb {Z}_{p^n} \,|\, T^{(p^n)}_b(\alpha _n^i)=1\big \}\right| , \end{aligned}$$

(8)

where $\alpha _n$ is a $p^n$th primitive root of unity. In the following we shall investigate the value of $T^{(p^n)}_b(\alpha _n^i)$ as i runs through $\mathbb {Z}_{p^n}$.

From the definitions in (6) and (7), the polynomial $T^{(p^n)}_b(x)$ heavily depends on the polynomials $E^{(p^j)}_{i}(x)$ and $H^{(p^j)}_{i}(x)$ for $1\le j\le n$ and $0\le i <d_j$. Some basic properties of these polynomials are given in the following lemma.

Lemma 6

Let $\alpha _j = \alpha _n^{p^{n-j}}$, $1\le j\le n$, be a $p^j$th primitive root of unity. Given any element $a\in D^{(p^j)}_k$, we have

• (i) $E^{(p^j)}_{i}(\alpha _j^{p^la})=E^{(p^{j-l})}_{i+k}(\alpha _{j-l})$ and $H^{(p^j)}_{i}(\alpha _j^{p^la})=H^{(p^{j-l})}_{i+k}(\alpha _{j-l})$ for $0\le l < j$; and

• (ii) $E^{(p^j)}_{i}(\alpha _j^{p^la})=e~(\bmod ~2)$ and $H^{(p^j)}_{i}(\alpha _j^{p^la})=p^{j-1}(p-1)/2~(\bmod ~2)$ for $l\ge j$.

Proof

• (i) In this case, it follows from Lemma 4 (i) that

  $$\begin{aligned} E^{(p^j)}_{i}\left( \alpha _j^{p^la}\right) = \sum _{t\in D^{(p^j)}_{i}}\left( \alpha _{j}^{p^la}\right) ^t=\sum _{t\in D^{(p^j)}_{i+k}} \left( \alpha _{j}^{p^l}\right) ^t=\sum _{t\in D^{(p^j)}_{i+k}}\alpha _{j-l}^{t}. \end{aligned}$$

  Since $\alpha _{j-l}$ is a $p^{j-l}$th primitive root of unity, one has $\alpha _{j-l}^t = \alpha _{j-l}^{t \pmod {p^{j-l}}}$ for $t\in D^{(p^j)}_{i+k}$. Lemma 4 (ii) implies $D_{i+k}^{(p^j)} \pmod {p^{j-l}} = D_{i+k}^{(p^{j-l})}$, whence

  $$\begin{aligned} E^{(p^j)}_{i}\left( \alpha _j^{p^la}\right) =\sum _{t\in D^{(p^j)}_{i+k}}\alpha _{j-l}^{t} = \sum _{t\in D^{(p^{j-l})}_{i+k}}\alpha _{j-l}^{t} = E^{(p^{j-l})}_{i+k}(\alpha _{j-l}). \end{aligned}$$

  Furthermore, by the definition of $H_i^{(p^j)}(x)$ we have

  $$\begin{aligned} H^{(p^j)}_i\left( \alpha _j^{p^la}\right) =\sum _{i'=0}^{ d_j/2-1} E^{(p^j)}_{i'+i} \left( \alpha _j^{p^la}\right) =\sum _{i'=0}^{ d_j/2-1}E^{(p^{j-l})}_{i'+i+k}(\alpha _{j-l}). \end{aligned}$$

  We observe that

  $$\begin{aligned} \begin{array}{c} \sum \limits _{i'=d_{j-l}/2}^{ d_j/2-1}E^{(p^{j-l})}_{i'+i+k}(\alpha _{j-l}) = \frac{p^l-1}{2}\sum \limits _{i'=0}^{ d_{j-l}-1}E^{(p^{j-l})}_{i'}(\alpha _{j-l}) = \frac{p^l-1}{2}\sum \limits _{t\in \mathbb {Z}^*_{p^{j-l}}}\alpha _{j-l}^t = 0. \end{array} \end{aligned}$$

  This implies

  $$\begin{aligned} H^{(p^j)}_i\left( \alpha _j^{p^la}\right) = \sum _{i'=0}^{ d_{j-l}/2-1} E^{(p^{j-l})}_{i'+i+k}(\alpha _{j-l}) =H^{(p^{j-l})}_{i+k}(\alpha _{j-l}). \end{aligned}$$

• (ii) In this case we have $\alpha _j^{p^l} = 1$. Then

  $$\begin{aligned} E^{(p^j)}_{i}\left( \alpha _j^{p^la}\right) = E^{(p^j)}_{i}(1) = |D^{(p^j)}_{i} | \pmod {2} = e \pmod {2}, \end{aligned}$$

  and $H^{(p^j)}_i(\alpha _j^{p^la}) = e d_j /2 \pmod {2} = p^{j-1}(p-1)/2 \pmod {2}.$

$\square$

The following proposition characterizes some properties of $T^{(p^{m})}_i(x)$ for $1\le m \le n$.

Proposition 1

For any $a\in D^{(p^j)}_k$, we have

• (i) $T^{(p^m)}_i(\alpha _m^{p^la}) =T^{(p^{m-l})}_{i+k}(\alpha _{m-l}) + (p^l-1)/2 \pmod {2}$ for $0\le l <m$; and

• (ii) $T^{(p^m)}_i(\alpha _m^{a}) + T^{(p^m)}_{i+d_m/2}(\alpha _m^{a}) = 1$.

Proof

• (i) From the definition in (6), Lemma 4 (ii) and Lemma 6, it follows that

  $$\begin{aligned} T^{(p^m)}_i\left( \alpha _m^{p^la}\right)&= \sum \limits _{j=1}^{m} H^{(p^{j})}_{i}\big (\alpha _{m}^{p^{m-j+l}a}\big )\nonumber \\&= \sum \limits _{j=l+1}^{m} H^{(p^{j})}_{i}\big (\alpha _{j-l}^{a}\big ) + \sum \limits _{j=1}^{l} H^{(p^{j})}_{i}(1)\nonumber \\&= \sum \limits _{j=l+1}^{m} H^{(p^{j-l})}_{i+k}\big (\alpha _{j-l}\big ) + (p^l-1)/2 \pmod {2} \nonumber \\&= \sum \limits _{j=1}^{m-l} H^{(p^{j})}_{i+k}\big (\alpha _{j}\big ) + (p^l-1)/2 \pmod {2}. \end{aligned}$$

  (9)

  Similarly we have

  $$\begin{aligned} T^{(p^{m-l})}_{i+k}(\alpha _{m-l}) = \sum \limits _{j=1}^{m-l} H^{(p^{j})}_{i+k}\big (\alpha _{m-l}^{p^{m-l-j}}\big ) = \sum \limits _{j=1}^{m-l} H^{(p^{j})}_{i+k}\big (\alpha _{j}\big ). \end{aligned}$$

  The desired result thus follows.

• (ii) By $\gcd (a, p) = 1$ we know that $\alpha ^a_m$ is also a primitive $p^m$th root of unity. Thus $\alpha ^a_m$ is a root of the polynomial $f(x) =(x^{p^m}-1)/(x-1) =x^{p^m-1} + x^{p^m-2} +\cdots + x + 1.$ By the definitions in (2), (6) and (7), it can be readily shown that

  $$\begin{aligned} T^{(p^m)}_i(x)+T^{(p^m)}_{i+d_m/2}(x) = x^{p^m-1} + x^{p^m-2} +\cdots + x = f(x) +1, \end{aligned}$$

  which immediately yields the desired result.

$\square$

We now examine the value of $T_b^{(p^n)}(\alpha _{n}^i)$ for some integers $i\in \mathbb {Z}_{p^n}$.

Proposition 2

Let p be a non-Wieferich prime. Then $T^{(p^n)}_b(\alpha _n^i) \not \in \{0,1\}$ for $i \in \mathbb {Z}_{p^n}\setminus p^{n-1}\mathbb {Z}_{p}$ and $b=0, 1, \ldots , d_n-1.$

Proof

We will show $T^{(p^n)}_b(\alpha _n^i) \not \in \{0,1\}$ by contradiction. Suppose there exists an integer $i_0\in \mathbb {Z}_{p^n}\setminus p^{n-1}\mathbb {Z}_{p}$ such that $T^{(p^n)}_b(\alpha _n^{i_0}) \in \{0,1\}$. The integer $i_0$ can be written as $i_0=p^{n-m}a$, where $1<m\le n$ and $a\in \mathbb { Z}_{p^m}^*$. Assume $a\in D_k^{(p^m)}$. By Proposition 1 (i) we have

$$\begin{aligned} T^{(p^n)}_b(\alpha _n^{i_0}) = T^{(p^n)}_b(\alpha _n^{p^{n-m}a}) = T^{(p^m)}_{b+k}(\alpha _m) + (p^{n-m}-1)/2 \pmod {2}, \end{aligned}$$

whence $T^{(p^m)}_{b+k}(\alpha _m) \in \{0,1\}.$ Without loss of generality, we can assume $b+k \equiv 0 \pmod {d_m}$ and $T^{(p^m)}_0(\alpha _m)=0$.

Suppose $2\equiv g^u \pmod {p^m}$ for some integer u. Letting $u_1 \equiv u \pmod {d_m}$, we have $2 \in D_{u_1}^{(p^m)}$. It then follows from Proposition 1 (i) that

$$\begin{aligned} T^{(p^m)}_0(\alpha _m)=\left( T^{(p^m)}_0(\alpha _m)\right) ^2= T^{(p^m)}_0(\alpha ^2_m) = T^{(p^m)}_{u_1}(\alpha _m), \end{aligned}$$

which implies $T^{(p^m)}_0(\alpha _m) = T^{(p^m)}_{i u_1}(\alpha _m) = 0$ for any integer $i\ge 1$.

Denote $v=\gcd (u_1,d_m)$. Since the subscript of $T_i^{(p^m)}(x)$ is taken modulo $d_m$, it is easily seen that

$$\begin{aligned} 0 = T^{(p^m)}_{0}(\alpha _m) = T^{(p^m)}_{iv}(\alpha _m),\quad i = 1, \ldots , d_m/v - 1. \end{aligned}$$

(10)

By Proposition 1 (ii) we have $T^{(p^m)}_0(\alpha _m)+T^{(p^m)}_{d_m/2}(\alpha _m)= 1$, whence $T^{(p^m)}_{d_m/2}(\alpha _m)= 1$. Thus v does not divide $d_m/2$. Since $v=\gcd (u_1, d_m)=\gcd (u, d_m)$ and $\gcd (u, p) = 1$ (by Lemma 1), it follows that v divides f but does not divide f / 2. A similar argument as in (10) gives

$$\begin{aligned} 1= T^{(p^m)}_{d_m/2 }(\alpha _m) = T^{(p^m)}_{d_m/2 + i f}(\alpha _m) \quad i = 1, \ldots , d_m/v - 1, \end{aligned}$$

which implies $T^{(p^m)}_{f/2}(\alpha _m) = T^{(p^m)}_{d_m/2+f(p^{m-1}+1)/2}(\alpha _m) = 1$. Hence we have

$$\begin{aligned} T^{(p^m)}_{0}(\alpha _m)+T^{(p^m)}_{f/2}(\alpha _m)=1. \end{aligned}$$

Denote $\xi =H^{(p^m)}_{0}(\alpha _m)+H^{(p^m)}_{f/2}(\alpha _m)$. Since

$$\begin{aligned} T^{(p^m)}_{0}(\alpha _m)+T^{(p^m)}_{f/2}(\alpha _m) = \sum \limits _{j=1}^{m}\Big ( H^{(p^j)}_{0}\left( \alpha _{m}^{p^{m-j}}\right) + H^{(p^j)}_{f/2}\left( \alpha _{m}^{p^{m-j}}\right) \Big ), \end{aligned}$$

it follows that

$$\begin{aligned} \xi = 1 + \sum \limits _{j=1}^{m-1}\Big ( H^{(p^j)}_{0}\left( \alpha _{m-1}^{p^{m-1-j}}\right) + H^{(p^j)}_{f/2}\left( \alpha _{m-1}^{p^{m-1-j}}\right) \Big ) \in \mathbb {F}_2(\alpha _{m-1}). \end{aligned}$$

On the other hand, by eliminating the overlapping terms in $H^{(p^m)}_{0}(\alpha _m)$ and $H^{(p^m)}_{f/2}(\alpha _m)$ we obtain

$$\begin{aligned} \xi = E^{(p^m)}_{0}(\alpha _m)+\dots +E^{(p^m)}_{f/2-1}(\alpha _m)+E^{(p^m)}_{d_m/2}(\alpha _m) +\dots +E^{(p^m)}_{f/2+d_m/2-1}(\alpha _m) = \sum \limits _{t\in \mathscr {D}}\alpha _m^t, \quad \end{aligned}$$

(11)

where $\mathscr {D}=D^{(p^m)}_{0}\cup \dots \cup D^{(p^m)}_{f/2-1}\cup D^{(p^m)}_{d_m/2}\cup \dots \cup D^{(p^m)}_{f/2+d_m/2-1}$. Observe that

$$\begin{aligned} \mathscr {D}\,(\text {mod}\,p)&= D^{(p)}_{0}\cup \cdots \cup D^{(p)}_{f/2-1}\cup D^{(p)}_{d_m/2 \pmod {f}}\cup \dots \cup D^{(p)}_{f/2+d_m/2-1 \pmod {f}}\\&= D^{(p)}_{0}\cup \cdots \cup D^{(p)}_{f/2-1}\cup D^{(p)}_{f/2}\cup \dots \cup D^{(p)}_{f-1}\\&= \mathbb {Z}_{p}^*. \end{aligned}$$

Thus, by letting $t \pmod {p} = \bar{t}$ for any $t\in \mathscr {D}$ we have

$$\begin{aligned} \xi = \sum \limits _{t\in \mathscr {D}}\alpha _m^t = \sum \limits _{t\in \mathscr {D}}\alpha _m^{ (t-\bar{t}) + \bar{t}} = \sum \limits _{t\in \mathscr {D}}\alpha _{m-1}^{(t-\bar{t})/p}\alpha _m^{\bar{t}} = \sum \limits _{i=1}^{p-1}c_i\alpha _m^{i}, \quad c_i \in \mathbb {F}_2(\alpha _{m-1}). \end{aligned}$$

It means that $\alpha _{m}$ is a root of the polynomial $f(x) = \sum \limits _{i=1}^{p-1}c_ix^i + \xi$ over $\mathbb { F}_2(\alpha _{m-1})$. This implies $[\mathbb {F}_2(\alpha _{m}):\mathbb {F}_2(\alpha _{m-1})]<p$, which is in contradiction with Lemma 3. $\square$

Remark 4

Proposition 2 greatly excludes the integers $i\in \mathbb { Z}_{p^n}$ that potentially lead to $T_b^{(p^n)}(\alpha _n^i) = 1$, which is critical for the proof of the main theorem. The technique used in the proof of Proposition 2 is generic and works for any integer $n\ge 2$. In the case of $n=2$, it can be used to prove the statement in Lemma 6 [22], where the documented proof works only for $f=2$.

By Proposition 2, we only need to study the value of $T_b^{(p^n)}(\alpha _n^{i})$ for integers i in the set $p^{n-1}\mathbb {Z}_{p}$. For any $a\in \mathbb {Z}_{p}^*$, it follows from Proposition 1 and Lemma 6 that

$$\begin{aligned} T_b^{(p^n)}(\alpha _n^{p^{n-1}a}) = T_b^{(p)}(\alpha _1^{a}) = H_b^{(p)}(\alpha _1^{a})=H_{k}^{(p)}(\alpha _1), \end{aligned}$$

where $a\in D_{i}^{(p)}$ for some integer i and $k \equiv b + i \pmod {f}$. The following proposition examines the value of $H_k^{(p)}(\alpha _1)$ according to the relation between f and ${\text {ord}}_p(2)$.

Proposition 3

Let $p = ef + 1$ be an odd prime with f being an even positive integer and $v = \gcd (\frac{p-1}{{\text {ord}}_p(2)}, f)$. Then,

• (i) $\left| \Big \{k \in \mathbb { Z}_{f} \,|\,H_k^{(p)}(\alpha _1) = 0\Big \}\right| = \left| \Big \{k \in \mathbb { Z}_{f} \,|\,H_k^{(p)}(\alpha _1) = 1\Big \}\right| = f/2$ if $v = f$; and

• (ii) $\left| \Big \{k \in \mathbb { Z}_{f} \,|\,H_k^{(p)}(\alpha _1) = 0\Big \}\right| = \left| \Big \{k \in \mathbb { Z}_{f} \,|\,H_k^{(p)}(\alpha _1) = 1\Big \}\right| = 0$ if $v \,|\, \frac{f}{2}$, or $v = 2$ and $f\ne v$.

Proof

From the definition of $H_k^{(p)}(x)$ we have

$$\begin{aligned} H_k^{(p)}(\alpha _1) + H_{k+f/2}^{(p)}(\alpha _1) = \alpha _1^{p-1} + \alpha _1^{p-2} + \cdots + \alpha _1 = 1 \end{aligned}$$

(12)

for $k = 0, 1, \ldots , f-1$. Thus $\left| \Big \{k \in \mathbb { Z}_{f} \,|\,H_k^{(p)}(\alpha _1) = 0\Big \}\right| = \left| \Big \{k \in \mathbb { Z}_{f} \,|\,H_k^{(p)}(\alpha _1) = 1\Big \}\right|$.

Assume $2\equiv g^u \pmod {p}$ for some integer u in $\mathbb { Z}_p^*$. Since ${\text {ord}}_p(2) = \frac{p-1}{\gcd (p-1, \,u)}$, it follows that $\gcd (p-1, u ) = \frac{p-1}{{\text {ord}}_p(2)}$. Thus we can write u as $u = {\frac{(p-1)t}{{\text {ord}}_p(2)}}$ with t co-prime to f. Denote $u_1 \equiv u \pmod {f}$. It follows that $2\in D^{(p)}_{u_1}$ and $\gcd (u_1, f) =\gcd (u, f) = \gcd (\frac{(p-1)t}{{\text {ord}}_p(2)}, f) =\gcd (\frac{(p-1)}{{\text {ord}}_p(2)}, f) = v$.

• (i) In this case we have $u_1\equiv 0 \pmod {f}$. Then $2\in D^{(p)}_{0}$ and

  $$\begin{aligned} \big (H_k^{(p)}(\alpha _1)\big )^2= H_k^{(p)}(\alpha _1^2)= H_k^{(p)}(\alpha _1) \end{aligned}$$

  for any $k\in \mathbb { Z}_f$, which implies $H_k^{(p)}(\alpha _1)\in \mathbb { F}_2$. The desired result immediately follows from (12).

• (ii) We shall prove this case by contradiction. Suppose $H_k^{(p)}(\alpha _1) \in \mathbb { F}_2$ for some integer k. Without loss of generality, we assume $k=0$ and $H_0^{(p)}(\alpha _1) = 0$.

In the case that $v \ne f$, we have $u_1<f$. Since $2\in D^{(p)}_{u_1}$ and $v = \gcd (u_1, f)$, by a similar argument as in the proof of Proposition 2 we get

$$\begin{aligned} 0 = H_0^{(p)}(\alpha _1) = H_{v}^{(p)}(\alpha _1) = \cdots = H_{(f/v-1)v}^{(p)}(\alpha _1), \end{aligned}$$

and

$$\begin{aligned} 1 = H_{f/2}^{(p)}(\alpha _1) = H_{f/2+v}^{(p)}(\alpha _1) = \cdots = H_{f/2 + (f/v-1)v}^{(p)}(\alpha _1). \end{aligned}$$

If v divides f / 2, then $H_{f/2}^{(p)}(\alpha _1) = H_{{f/2 + v \cdot f/2v}}^{(p)}(\alpha _1) = H_0^{(p)}(\alpha _1),$ which is a contradiction.

Let $v=2, v\ne f$ and v does not divide f / 2, it is clear that f / 2 is odd. Then we get

$$\begin{aligned} 0 = H_0^{(p)}(\alpha _1) = H_{2}^{(p)}(\alpha _1) = \cdots = H_{(f-2)}^{(p)}(\alpha _1), \end{aligned}$$

and

$$\begin{aligned} 1 = H_{1}^{(p)}(\alpha _1) = H_{3}^{(p)}(\alpha _1) = \cdots = H_{f-1}^{(p)}(\alpha _1). \end{aligned}$$

So, we see that $H_{i}^{(p)}(\alpha _1)+ H_{i+1}^{(p)}(\alpha _1)+1=0, i=0,1,\dots ,f-1$ and then

$$\begin{aligned} E_{i}^{(p)}(\alpha _1)+ E_{i+f/2}^{(p)}(\alpha _1)+1=0, \quad i=0, 1,\dots ,f-1. \end{aligned}$$

(13)

By the definition we can easily choose an integer j such that $(p-1) \not \in \left( D_{j}^{(p)}\cup D^{(p)}_{j+f/2}\right)$.

We define $f(x)=E_{j}^{(p)}(x)+E^{(p)}_{j+f/2}(x)+1$. Given any $a\in \mathbb {Z}_p^*$, assuming $a\in D_{k}^{(p)}$ for an integer k, we obtain from Lemma 6 and (13) that $f(\alpha _1^a)=E_{j+k}^{(p)}(\alpha _1)+E^{(p)}_{j+f/2+k}(\alpha _1)+1=0.$ That is to say, $f(\alpha _1^a) = 0$ for any $a\in \mathbb {Z}_p^*$. This is a contradiction since the polynomial f(x) has degree less than $p -1$. $\square$

With the preceding preparations, we are now in a position to prove the main theorem.

Proof of Theorem 5

Recall that the linear complexity of $s^{\infty }$ is given by

$$\begin{aligned} L=p^n-\left| \big \{i \in \mathbb {Z}_{p^n} \,|\, T^{(p^n)}_b(\alpha _n^i)=1\big \}\right| . \end{aligned}$$

From Proposition 2 we know $\left| \big \{i \in \mathbb {Z}_{p^n}\setminus p^{n-1}\mathbb { Z}_p \,|\, T^{(p^n)}_b(\alpha _n^i)=1\big \}\right| = 0$. For the remaining set $p^{n-1}\mathbb { Z}_p$, if $i=0$, then $T^{(p^n)}_b(\alpha _n^i) = \frac{p^n-1}{2} \pmod {2}$; if $i \in p^{n-1}\mathbb { Z}_p^*$, we have

$$\begin{aligned} T^{(p^n)}_b(\alpha _n^i) = T^{(p)}_b(\alpha _1^a) = H^{(p)}_b(\alpha _1^a) \end{aligned}$$

for some integer $a\in \mathbb { Z}_p^*$. It is easily seen that $\left| \big \{a \in \mathbb { Z}_p^*\,|\, H^{(p)}_b(\alpha _1^a)=1\big \}\right| = e \left| \big \{k \in \mathbb { Z}_f\,|\, H^{(p)}_k\right. \left. (\alpha _1)=1\big \}\right|$ for any integer b with $0\le b<d_n$. Hence the linear complexity

$$\begin{aligned} \begin{array}{c} L=p^n-\delta \big (\frac{p^n+1}{2}\big )-e \left| \big \{k \in \mathbb {Z}_{f} \,|\, H^{(p)}_k(\alpha _1)=1\big \}\right| . \end{array} \end{aligned}$$

(14)

Suppose $H^{(p)}_k(\alpha _1)=1$ for some integer k. Then

$$\begin{aligned} 1 = (H^{(p)}_k(\alpha _1))^{2} = H^{(p)}_k(\alpha _1^{2}) = H^{(p)}_{k+u_1}(\alpha _1^{2}), \end{aligned}$$

where $2\in D_{u_1}^{(p)}$ for some integer $u_1$. From the fact that $H^{(p)}_{k}(\alpha _1) + H^{(p)}_{k+f/2}(\alpha _1^a) = 1$ for any $k \in \mathbb {Z}_{f}$, we have

$$\begin{aligned} \begin{array}{c} L=p^n -\delta (\frac{p^n+1}{2}) - r{\text {ord}}_p(2), \end{array} \end{aligned}$$

where r is an integer with $0\le r \le \frac{p-1}{2{\text {ord}}_p(2)}$.

• (i) For $p\equiv \pm 3 \pmod {8}$, it is well known [12] that 2 is a quadratic non-residue of primes since the Legendre symbol $\big (\frac{2}{p}\big )=(-1)^{\frac{p^2-1}{8}}$. Assume $2=g^{u}\pmod {p}$ for some odd integer u. It follows that $\gcd \big (\frac{p-1}{\mathrm{ord}_p(2)}, f\big ) = \gcd (u, f)$ is odd, which always divides f / 2. From Proposition 3 (ii) the desired result follows.

• (ii) For $p\equiv \pm 1 \pmod {8}$, we immediately obtain the desired result from Proposition 3. $\square$

At the end of this section, we give some examples demonstrating the main result in this paper.

Example 1

Choose an odd prime $p = 13$. The possible even divisors f of $p-1$ are 2, 4, 6, 12 and in this case 2 is a primitive root. To avoid confusion we take a primitive root $g=6$.

• (i) For $n=1$ and $f=2, 4, 6, 12$, we take $b=1$ and then obtain the following four sequences:

  $$\begin{aligned} 1010011110010, 1010111000101, 1001011110100, 1010001011101. \end{aligned}$$

  Our experimental result shows that all these sequences have linear complexity 13, which matches the statement of Theorem 5 (i).

• (ii) For $n=2$ and $f=2, 4, 6, 12$, we randomly take $b=7$ and then obtain the following four sequences:

  $$\begin{aligned}&1000110111000001000101001111010001110010111101001010001101010001010010 \\&1110010111111100111111101001110100101000101011000101001011110100111000 \\&10111100101000100000111011000, \\&1000100110000110100101011000100010110111111000101100010011010101100111 \\&1110101101101110001001001010000001100101010011011100101110000001001011 \\&10111001010110100111100110111, \\&1000110010000001110100011100010111110011010001101011000101010010110111 \\&1011011111001000010011111011011110110100101010001101011000101100111110 \\&10001110001011100000010011000, \\&1000110110110111100111111000111011000011101011101000100011111101111101 \\&0110001000100110011011101110010100000100000011101110100010100011110010 \\&00111000000110000100100100111. \end{aligned}$$

  Our experimental result shows that all these sequences have linear complexity 169, which matches the statement of Theorem 5 (i).

• (iii) For $3\le n\le 6$ and $f=2, 4, 6, 12$, we also compute the linear complexities of the sequences $s^{\infty }$ with a Magma program. Our experimental results are all consistent with the statement of Theorem 5 (i).

Example 2

Choose an odd prime $p = 31$. We have ${\text {ord}}_p(2) = 5$ and a primitive root $g=3$. For all possible even integers f that divide $p-1$, the relation between $v = \big (\frac{p-1}{{\text {ord}}_p(2)}, f\big )$ and f is given as follows.

f	2	6	10	30
v	2	6	2	6
relation	$v=f$	$v=f$	$v=2$	–

Here the dash indicates that the relation is not included in Theorem 5 (ii).

• (i) For $n=1$ and $f=2, 6, 10, 30$, we take $b=3$ and then obtain the following four sequences $s_1, s_2, s_3, s_4$, respectively.

  $$\begin{aligned} \begin{array}{l} s_1: \, 1001001000011101010001111011011 \quad s_2: \, 1000000100010111000101110111111 \\ s_3:\, 1010001000110000111100111011101 \quad s_4: \, 1000000010100100110110101111111 \end{array} \end{aligned}$$

  Our experimental result shows that the linear complexities of $s_1, s_2, s_3, s_4$ are $15, \,15, 30, 25$, respectively. The linear complexities of $s_1, s_2, s_3$ match the statement of Theorem 5 (ii), and the linear complexity of $s_4$ matches the general statement of Theorem 5.

• (ii) For $n=2$ and $f=2, 6, 10, 30$, we take $b=0$ and obtain four sequences $s_1, s_2, s_3, s_4$, respectively. Our experimental result shows that the linear complexities of $s_1, s_2, s_3, s_4$ are $946, \,946, 961, 956$, respectively. These results are consistent with the statement of Theorem 5.

• (iii) For $n=3, 4$ and $f=2, 6, 10, \,30$, we also compute the linear complexity of the sequences $s^{\infty }$ with a magma program. Our experimental results show that the linear complexities of $s^{\infty }$ corresponding to $f=2, 6, 10$ match the statement of Theorem 5 (ii), and the linear complexities of $s^{\infty }$ corresponding to $f=30$ match the the general statement of Theorem 5.

Remark 5

Low autocorrelation is one of the desirable properties of pseudo-random sequences in cryptography and digital communication. Unfortunately some cyclotomic binary sequences with high linear complexity do not have satisfactory autocorrelation properties [13, 14, 17]. For the sequences $s^{\infty }$ studied in this paper, because the generalized cyclotomic classes in (2) have varying orders for $1\le j\le n$, it is challenging to obtain theoretical result on the autocorrelation values of $s^{\infty }$. We checked all the sequences in Examples 1 and 2 by a computer program. Unfortunately, these sequences $s^{\infty }$ have many autocorrelation values with a large maximum out-of-phase autocorrelation. This makes a theoretical study of autocorrelation properties of this family of sequences intractable and less interesting.

Very recently Wu et al. [21] studied the error linear complexity of the cyclotomic binary sequences of period $p^2$ in [22] for the case $f=2$, and showed that the sequences are stable in terms of kth error linear complexity. The error linear complexity of the cyclotomic sequences of period $p^n$ is beyond the focus of this paper and interested readers are invited to work on this topic.

4 Conclusion

This paper re-examined the linear complexity of a family of generalized cyclotomic binary sequences of period $p^n$. The major contribution of this paper is that it proved the conjecture by Xiao et al. about the linear complexity of this family of sequences with a new technique, and it applied the new technique to extend the conjectured result to more general cases.