1. Introduction
Pseudo-random sequences are widely used in various fields, such as code division multiple access, stream cryptography, coding theory etc. [1]-[3]. Quaternary sequences with high complexity, low correlation, and balancedness are the preferred sequences in practical applications.
Trace function over the Galois ring can effectively generate quaternary sequences. And the trace representation of quaternary sequences reveals some important properties of the sequences. In 2017, Chen [4] defined a family of quaternary sequences of period \(pq\) over \(\mathbb{Z}_{4}\), and given their trace representation by using discrete Fourier transform, from which the linear complexity of the sequence is obtained. Recently, Yang et al. [5] constructed a class of balanced quaternary sequences of period \(p\), and determined their trace representation and linear complexity over \(\mathbb{Z}_{4}\). Except above mentioned results, limited works on the trace representation of quaternary sequences over Galois rings are known.
It is convenient to define quaternary sequences by using the classical and generalized cyclotomic classes [6]-[8]. Inspired by the works in [4], [5], we introduce a general construction of balanced quaternary sequences of period \(p^{n}\) by using generalized cyclotomic classes. And we calculate the trace representation of these sequences over \(\mathbb{Z}_{4}\).
The rest of this letter is organized as follows. In Sect. 2, we provide some basic concepts and the required lemmas. In Sect. 3, we define a family of balanced quaternary sequences based on generalized cyclotomic classes, and derive the trace representation and linear complexity of these sequences over \(\mathbb{Z}_{4}\). Section 4 draws the conclusions.
2. Preliminaries
Let \(\mathbb{Z}_{m}=\left\lbrace 0,1,\dots,m-1\right\rbrace\), and \(\mathbb{Z}_{m}^{*}\) denote the set of all elements in \(\mathbb{Z}_{m}\) that are coprime with \(m\).
The Galois ring of characteristic 4 and cardinality \(4^{r}\) is denoted by \(GR(4,4^{r})\). There exists a nonzero element \(\xi\) of order \(2^{r}-1\) in \(GR(4,4^{r})\), which is a root of a basic primitive polynomial of degree \(r\) over \(\mathbb{Z}_{4}\). Let \(\mathcal{T}=\left\lbrace 0,1,\xi,\xi^{2},\dots,\xi^{2^{r}-2}\right\rbrace\), then any element \(c\in GR(4,4^{r})\) can be written uniquely as \(c=c_{0}+2c_{1}\), where \(c_{0}, c_{1}\in \mathcal{T}.\)
Let \(d\) be a positive integer that satisfies \(d|r\). Then \(GR(4,4^{r})\) contains \(GR(4,4^{d})\) as a subring. Define a map \(\phi\):
| \[\begin{eqnarray*} &&\!\!\!\!\! \phi:GR(4,4^{r})\to GR(4,4^{d})\notag\\ &&\!\!\!\!\! c=c_{0}+2c_{1}\mapsto c_{0}^{2^{d}}+2c_{1}^{2^{d}}, \quad c_{0}, c_{1}\in \mathcal{T}.\notag \end{eqnarray*}\] |
Then \(\phi\) is an automorphisms of \(GR(4,4^{r})\) leaving \(GR(4,4^{d})\) fixed elementwise. And \(\phi\) is called the generailzed Frobenius automorphism of \(GR(4,4^{r})\) over \(GR(4,4^{d})\) in [9]. For any \(c\in GR(4,4^{r})\), define \(Tr_{d}^{r}(c)=c+\phi(c)+\dots+\phi^{\frac{r}{d}-1}(c)\) to be the generalized trace of \(c\in GR(4,4^{r})\) relative to \(GR(4,4^{d})\). Especially, if \(c_{0}\in\mathcal{T}\), we have
| \[\begin{equation} Tr_{d}^{r}(c_{0})=c_{0}+c_{0}^{2^{d}}+\dots+c_{0}^{2^{d(\frac{r}{d}-1)}}. \tag{1} \end{equation} \] |
For more detailed description of the theory of Galois rings, please refer to [9].
Let \(p\) be an odd prime and \(\lambda_{n}\) be the order of 2 modulo \(p^{n}\), that is \(2^{\lambda_{n}}\equiv1\:(\mathrm{mod}\;p^{n})\), then \(p^{n}|(2^{\lambda_{n}}-1)\), and there exists a nonzero element \(\xi_{n}\) of order \(2^{\lambda_{n}}-1\) in \(GR(4,4^{\lambda_{n}})\), then \(\xi_{n}^{\frac{2^{\lambda_{n}}-1}{p^{n}}}\) denoted as \(\beta\) has order \(p^{n}\). Thus, the quaternary sequence \(\textbf{s}=(s(0),s(1),\dots)\) over \(\mathbb{Z}_{4}\) of period \(p^{n}\) can be represented as
| \[\begin{equation*} s(t)=\frac{1}{p^{n}}\sum_{k=0}^{p^{n}-1}\hat{s}(k)\beta^{kt},\quad t=0,1,\dots,p^{n}-1, \tag{2} \end{equation*}\] |
where
| \[\begin{equation*} \hat{s}(k)=\sum_{t=0}^{p^{n}-1}s(t)\beta^{-kt},\quad k=0,1,\dots,p^{n}-1. \tag{3} \end{equation*}\] |
Here \(\hat{s}(k)\) is the discrete Fourier transform of \(\textbf{s}\) and \(\hat{\textbf{s}}=(\hat{s}(0),\hat{s}(1),\dots)\) is called the Fourier spectral sequence of \(\textbf{s}\). The polynomial defined as
| \[\begin{equation*} \hat{S}(x)=\frac{1}{p^{n}}\sum_{k=0}^{p^{n}-1}\hat{s}(k)x^{k}\in GR(4,4^{\lambda_{n}})[x]\tag{4} \end{equation*}\] |
is called Mattson-Solomon polynomial in coding theory [10]. We have
| \[\begin{equation*} s(t)=\hat{S}(\beta^{t}),\quad t\ge 0.\tag{5} \end{equation*}\] |
The polynomial satisfying (5) is also called the defining polynomial of \(\textbf{s}\) corresponding to \(\beta\) in [11]. Note that for a given \(\beta\), since \(\mathrm{gcd}(p^{n},4)=1\), thus \(\hat{S}(x)\) is uniquely determined modulo \(x^{p^{n}}-1\).
The following lemma provides a method for calculating the linear complexity of quaternary sequences over \(\mathbb{Z}_{4}\).
Lemma 1: ([12]) Let \(\textbf{s}=(s(0),s(1),\dots)\) be a quaternary sequence over \(\mathbb{Z}_{4}\) of period \(p^{n}\), and let \(\hat{\textbf{s}}=(\hat{s}(0),\hat{s}(1),\dots)\) be its Fourier spectral sequence defined in (3). Then \(LC(\textbf{s})\), the linear complexity of \(\textbf{s}\) over \(\mathbb{Z}_{4}\), is given by
| \[\begin{equation*} LC(\textbf{s})=|\left\lbrace k:\hat{s}(k)\not=0,0\le k\le p^{n}-1\right\rbrace |.\notag \end{equation*}\] |
That is, the linear complexity of the sequence \(\textbf{s}\) is equal to the number of nonzero coefficients in (4).
The following lemma contributes to understand the cyclotomic technique required in this letter.
Lemma 2: ([13]) Let \(p\) be a prime, then the following three assertions are equivalent:
(1) \(g\) is a primitive root of \(p\) and \(g^{p-1}\not\equiv1\:(\mathrm{mod}\;p^{2})\).
(2) \(g\) is a primitive root of \(p^{2}\).
(3) For every \(m\ge 2\), \(g\) is a primitive root of \(p^{m}\).
By Lemma 2, if \(g\) is a primitive root of \(p^{2}\), then \(g\) is a primitive root of \(p^{m}\), where \(1\le m\le n\). Moreover, the order of \(g\) in \(\mathbb{Z}_{p^{m}}^{*}\) is \(\varphi(p^{m})=p^{m-1}(p-1)\), where \(\varphi(\cdot)\) denotes the Euler function.
Let \(p=ef+1\) be an odd prime and \(g\) is a primitive root of \(p^{2}\). For each \(m(1\le m\le n)\), \(i\in \mathbb{Z}_{e}\), define
| \[\begin{align} \!D_{i}^{(m)}\!&=\!\left\lbrace g^{ek+i}\:\!(\mathrm{mod}\;p^{m})\!:\!k=0,1,\dots,\!p^{m-1}f\!-1\!\right\rbrace.\!\tag{6} \end{align}\] |
The division of \(\mathbb{Z}_{p^{m}}^{*}\) can be obtained, that is
| \[\begin{equation*} \mathbb{Z}_{p^{m}}^{*}=D_{0}^{(m)}\cup D_{1}^{(m)}\cup\dots\cup D_{e-1}^{(m)}.\notag \end{equation*}\] |
Due to \(\mathbb{Z}_{p^{m}}=\mathbb{Z}_{p^{m}}^{*}\cup p\mathbb{Z}_{p^{m-1}}\), then \(\mathbb{Z}_{p^{n}}\) can be denotes as
| \[\begin{aligned} \mathbb{Z}_{p^{n}} \!=\!(\bigcup_{m=1}^{n}p^{n-m}D_{0}^{(m)})\!\cup\dots\cup\!( \!\bigcup_{m=1}^{n}p^{n-m}D_{e-1}^{(m)})\!\cup\left\lbrace 0\right\rbrace.\! \end{aligned}\] |
We denote
| \[\begin{equation*} C_{i}=\bigcup_{m=1}^{n}p^{n-m}D_{i}^{(m)},\quad 0\le i\le e-1.\tag{7} \end{equation*}\] |
Then \(\mathbb{Z}_{p^{n}}=\bigcup_{i=0}^{e-1}C_{i}\cup\left\lbrace 0\right\rbrace\).
The following lemma is the property of the cyclotomic classes.
Lemma 3: ([14]) Let \(a\in \mathbb{Z}_{p^{n}}^{*}\), if \(a\:(\mathrm{mod}\;p^{n})\in D_{i}^{(n)}\), then \(aD_{l}^{(m)}\:(\mathrm{mod}\;p^{m})=D_{l+i\:(\mathrm{mod}\;e)}^{(m)}\), \(aC_{l}=C_{l+i\:(\mathrm{mod}\;e)}\), where \(0\le i\le e-1\), \(0\le l\le e-1\), \(1\le m\le n\).
3. Trace Representation of a Family of Balanced Quaternary Sequences
In this section, we will use the generalized cyclotomic classes to define a family of balanced quaternary sequences of period \(p^{n}\), and calculate their trace representation over \(\mathbb{Z}_{4}\).
Let \(p=ef+1\) be an odd prime, where \(e\equiv0\pmod 4\), and \(C_{i}\) is defined in (7). Then a class of balanced quaternary sequences \(\textbf{s}=(s(0),s(1),\dots)\) can be defined as:
| \[\begin{equation*} s(t)=\begin{cases} a_{i},\qquad &\mathrm{if}\ t\:(\mathrm{mod}\;p^{n})\in C_{i},\\ a_{*},&\mathrm{if}\ t\:(\mathrm{mod}\;p^{n})=0, \end{cases}\tag{8} \end{equation*}\] |
where \(a_{*}, a_{0},\dots,a_{e-1}\in\mathbb{Z}_{4}\), and the number of occurrences of 0, 1, 2 and 3 in \(a_{0},a_{1},\dots,a_{e-1}\) is the same. Obviously, \(p^{m}(m<n)\) is not a period of \(\textbf{s}\), then it possesses the least period \(p^{n}\).
Define a sequence \(\textbf{b}_{i}=(b_{i}(0),b_{i}(0),\dots)\) of period \(p^{n}\) as follows:
| \[\begin{equation*} b_{i}(t)=\begin{cases} 1,\qquad &\mathrm{if}\ t\:(\mathrm{mod}\;p^{n})\in C_{i};\\ 0,&\mathrm{if}\ t\:(\mathrm{mod}\;p^{n})=0. \end{cases}\tag{9} \end{equation*}\] |
Easy to verify the balanced quaternary sequence defined in (8) can be represented as
| \[\begin{equation*} \textbf{s}=a_{*}\boldsymbol{\delta}+\sum_{i=0}^{e-1}a_{i}\textbf{b}_{i}, \tag{10} \end{equation*}\] |
where each \(\textbf{b}_{i}\) is defined in (9), and \(\boldsymbol{\delta}=(\delta(0),\delta(1),\dots)\) satisfies
| \[\begin{equation*} \delta(t)=\begin{cases} 1,\qquad &\mathrm{if}\ t\:(\mathrm{mod}\;p^{n})=0;\\ 0,&\mathrm{otherwise}. \end{cases}\tag{11} \end{equation*}\] |
Let \(g\) be a primitive root of \(p^{2}\) and \(v\) be an integer for which \(-1\in D_{v}^{(n)}\). Let \(\lambda_{n}\) be the order of 2 modulo \(p^{n}\), then \(\beta\) is a fixed element of order \(p^{n}\) in \(GR(4,4^{\lambda_{n}})\). Define polynomial \(D_{l}^{(m)}(x)=\sum_{t\in D_{l}^{(m)}}x^{t}\), where \(D_{l}^{(m)}\) is defined in (6), \(0\le l\le e-1\), \(1\le m\le n\). Also define polynomial \(C_{l}(x)=\sum_{t\in C_{l}}x^{t}\), where \(C_{l}\) is defined in (7), \(0\le l\le e-1\).
The defining polynomial of the sequence \(\textbf{s}\) defined in (8) can be calculated by the following lemma.
Lemma 4: Let \(s\) be a sequence defined in (8). Then \(\hat{S}(x)\), the defining polynomial of \(\textbf{s}\) corresponding to \(\beta\) is given by
| \[\begin{equation*} \hat{S}(x)=\rho_{*}+\sum_{l=0}^{e-1}\sum_{m=1}^{n}\rho_{l,m}D_{l}^{(m)}(x^{p^{n-m}}),\notag \end{equation*}\] |
where \(\rho_{*}=a_{*}+\dfrac{p^{n}-1}{e}\sum\limits_{i=0}^{e-1}a_{i},\) and for \(0\le l<e\), \(1\le m\le n\),
| \[\begin{equation*} \rho_{l,m}=a_{*}+\sum\limits_{i=0}^{e-1}a_{i}C_{i+l+v\:(\mathrm{mod}\;e)}(\beta^{p^{n-m}}). \tag{12} \end{equation*}\] |
Proof 1: According to (5) and (10), we have
| \[\begin{aligned} \hat{S}(\beta^{t})&=s(t)=a_{*}\delta(t)+\sum_{i=0}^{e-1}a_{i}b_{i}(t)\\&=a_{*}\hat{\triangle}(\beta^{t})+\sum_{i=0}^{e-1}a_{i}\hat{B}_{i}(\beta^{t}),\notag \end{aligned}\] |
where \(\hat{\triangle}(x)\) and \(\hat{B}_{i}(x)\) denote the defining polynomials of \(\boldsymbol{\delta}\) defined in (11) and \(\textbf{b}_{i}\) defined in (9) corresponding to \(\beta\), respectively. Thus, we will calculate \(\hat{\triangle}(x)\) and \(\hat{B}_{i}(x)\), respectively.
We first calculate \(\hat{B}_{i}(x)\). The Fourier spectral sequence of the sequence \(\textbf{b}_{i}\) defined in (9) write as \(\hat{\textbf{b}_{i}}\). By (3) and (9), we have \(\hat{b}_{i}(0)=\sum_{t=0}^{p^{n}-1}b_{i}(t)=|C_{i}|=\dfrac{p^{n}-1}{e}\), and for \(k=1,2,\dots,p^{n}-1\), \(\hat{b}_{i}(k)=\sum_{t=0}^{p^{n}-1}b_{i}(t)\beta^{-kt}=\sum_{t\in C_{i}}\beta^{-kt}\).
Since we assume that \(-1\in D_{v}^{(n)}\), for any \(k\in \mathbb{Z}_{p^{n}}\setminus\left\lbrace 0\right\rbrace\), there uniquely exitsts a pair \((l,m)\) such that \(k=p^{n-m}k'\), where \(k'\in D_{l}^{(m)}\), \(0\le l\le e-1\) and \(1\le m\le n\). Then by Lemma 3, we have
| \[\begin{aligned} -kC_{i}&=-p^{n-m}k'\left( \bigcup_{u=1}^{n}p^{n-u}D_{i}^{(u)}\right)\\& =p^{n-m}\left( \bigcup_{u=1}^{n}p^{n-u}D_{i+l+v\:(\mathrm{mod}\;e)}^{(u)}\right)\\&=p^{n-m}C_{i+l+v\:(\mathrm{mod}\;e)}. \end{aligned}\] |
Therefore,
| \[\begin{aligned} \hat{b}_{i}(k)&=\sum_{t\in C_{i}}\beta^{-kt}=\sum_{t\in C_{i+l+v\:(\mathrm{mod}\;e)}}\beta^{p^{n-m}t}\\&=C_{i+l+v\:(\mathrm{mod}\;e)}(\beta^{p^{n-m}}),\notag \end{aligned}\] |
which implies that the value of \(\hat{b}_{i}(k)\) depends on \(p^{n-m}D_{l}^{(m)}\) to which \(k\) belongs. By (4), we get
| \[\begin{align} \begin{split} \hat{B}_{i}(x)&=\sum_{k=0}^{p^{n}-1}\hat{b}_{i}(k)x^{k}=\hat{b}_{i}(0)+\sum_{k=1}^{p^{n}-1}\hat{b}_{i}(k)x^{k}\\ &=\dfrac{p^{n}-1}{e}+\sum_{l=0}^{e-1}\sum_{m=1}^{n}\sum_{k\in(p^{n-m}D_{l}^{(m)})}\hat{b}_{i}(k)x^{k}\!\!\!\!\!\!\!\\ &\!=\!\!\dfrac{p^{n}-1}{e}\!\!+\!\!\sum_{l=0}^{e-1}\!\sum_{m=1}^{n}\!\!C_{i+l+v\:(\mathrm{mod}\;e)}(\beta^{p^{n-m}})D_{l}^{(m)}(x^{p^{n-m}}).\!\!\!\!\!\! \end{split}&\tag{13} \end{align}\] |
Next, we calculate \(\hat{\triangle}(x)\). According to (3), the Fourier spectral sequence of the sequence \(\boldsymbol{\delta}\) defined in (11) write as \(\hat{\boldsymbol{\delta}}\). For \(k\in\mathbb{Z}_{p^{n}}\), \(\hat{\boldsymbol{\delta}}\) satisfies
| \[\begin{aligned} \hat{\delta}(k)&=\sum_{t=0}^{p^{n}-1}\delta(t)\beta^{-kt}=\delta(0)\beta^{0}+\sum_{t=1}^{p^{n}-1}\delta(t)\beta^{-kt}=1. \end{aligned}\] |
Thus, by (4), we get
| \[\begin{align} \hat{\triangle}(x)&=\sum_{k=0}^{p^{n}-1}\hat{\delta}(k)x^{k}=\sum_{k=0}^{p^{n}-1}x^{k}=1+\sum_{k=1}^{p^{n}-1}x^{k}\\& =1+\sum_{l=0}^{e-1}\sum_{m=1}^{n}\sum_{k\in(p^{n-m}D_{l}^{(m)})}x^{k}\\&=1+\sum_{l=0}^{e-1}\sum_{m=1}^{n}D_{l}^{(m)}(x^{p^{n-m}}).\tag{14} \end{align}\] |
Therefore, by (5), (10), (13) and (14), we have
| \[\begin{aligned} \begin{split} s(t)&=a_{*}\delta(t)+\sum_{i=0}^{e-1}a_{i}b_{i}(t)=a_{*}\hat{\triangle}(\beta^{t})+\sum_{i=0}^{e-1}a_{i}\hat{B}_{i}(\beta^{t}) \\&=a_{*}+\dfrac{p^{n}-1}{e}\sum_{i=0}^{e-1}a_{i}\\&\!+\sum_{l=0}^{e-1}\sum_{m=1}^{n}[a_{*}+\sum_{i=0}^{e-1}a_{i}C_{i+l+v\:(\mathrm{mod}\;e)}(\beta^{p^{n-m}})]D_{l}^{(m)}(\beta^{p^{n-m}t}).\! \end{split}&\notag \end{aligned}\] |
From (5), it can be concluded that the conclusion is valid. \(\tag*{□}\)
Theorem 1: The trace representation of the sequence \(\textbf{s}\) defined in (8) over \(\mathbb{Z}_{4}\) is given by
(1) If \(2\in D_{0}^{(m)}\) for any \(m(1\le m\le n)\), then
| \[s(t)=\rho_{*}+\sum\limits_{l=0}^{e-1}\sum\limits_{m=1}^{n}\rho_{l,m}\sum\limits_{i=0}^{\frac{p^{m-1}f}{\lambda_{m}}-1}Tr_{1}^{\lambda_{m}}(\beta^{p^{n-m}tg^{ei+l}}),\] |
(2) If \(2\in D_{h}^{(m)}\) for any \(m(1\le m\le n)\), \(1\le h\le e-1\), then
| \[s(t)=\rho_{*}+\sum\limits_{l=0}^{e-1}\sum\limits_{m=1}^{n}\rho_{l, m}\sum\limits_{i=0}^{\frac{p^{m-1}fd}{\lambda_{m}}-1}Tr_{d}^{\lambda_{m}}(\beta^{p^{n-m}tg^{ei+l}}),\] |
where \(\rho_{*}\) and \(\rho_{l, m}\) are defined in (12), and \(d=\dfrac{e}{\mathrm{gcd}(e,h)}\).
Proof 2: According to Lemma 4 and (5), if we can use the trace functions over Galois rings to represent \(D_{l}^{(m)}(\beta^{p^{n-m}t})\) with \(0\le l\le e-1\) and \(1\le m\le n\), then we can obtain the trace representation of the sequence \(\textbf{s}\).
For each \(1\le m\le n\), let \(\lambda_{m}\) is the order of 2 modulo \(p^{m}\), and let \(A_{m}\) denote the cyclic group generated by 2. Then \(A_{m}\) can be represented as
| \[\begin{equation*} A_{m}=\left\langle 2\right\rangle =\left\lbrace 1,2^{1},\dots,2^{\lambda_{m}-1}\right\rbrace,\notag \end{equation*}\] |
where \(\left\langle a\right\rangle\) denotes the cyclic group generated by \(a\).
If \(2\in D_{0}^{(m)}\) for any \(m(1\le m\le n)\), then we have \(\lambda_{m}|p^{m-1}f\) and \(A_{m}\) is a subgroup of \(D_{0}^{(m)}\). And notice that the element \(g^{\frac{p^{m-1}ef}{\lambda_{m}}}=g^{e\cdot\frac{p^{m-1}f}{\lambda_{m}}}\in D_{0}^{(m)}\) is also of order \(\lambda_{m}\). This implies
| \[\begin{aligned} A_{m}&=\left\langle 2\right\rangle =\left\langle g^{\frac{p^{m-1}ef}{\lambda_{m}}}\right\rangle =\left\lbrace g^{e\cdot\frac{p^{m-1}f}{\lambda_{m}}\cdot t}:0\le t<\lambda_{m}\right\rbrace , \end{aligned}\] |
hence we have
| \[\begin{aligned} D_{0}^{(m)}&=\left\lbrace g^{ek}: 0\le k<p^{m-1}f\right\rbrace \\&=\bigcup\limits_{i=0}^{\frac{p^{m-1}f}{\lambda_{m}}-1}g^{ei}\left\langle g^{\frac{p^{m-1}ef}{\lambda_{m}}}\right\rangle =\bigcup_{i=0}^{\frac{p^{m-1}f}{\lambda_{m}}-1}g^{ei}A_{m}.\notag \end{aligned}\] |
Define polynomial \(A_{m}(x)=\sum\limits_{l\in A_{m}}x^{l}=x+x^{2}+x^{2^{2}}+\dots+x^{2^{\lambda_{m}-1}}\), then
| \[\begin{aligned} D_{0}^{(m)}(x) =\sum\limits_{i=0}^{\frac{p^{m-1}f}{\lambda_{m}}-1}\sum\limits_{l\in A_{m}}x^{g^{ei}l}=\sum\limits_{i=0}^{\frac{p^{m-1}f}{\lambda_{m}}-1}A_{m}(x^{g^{ei}}).\notag \end{aligned}\] |
Thus, according to (1), \(D_{0}^{(m)}(\beta^{p^{n-m}t})\) can be described by the trace function from \(GR(4,4^{\lambda_{m}})\) to \(\mathbb{Z}_{4}\) as
| \[\begin{aligned} D_{0}^{(m)}(\beta^{p^{n-m}t})&=\sum\limits_{i=0}^{\frac{p^{m-1}f}{\lambda_{m}}-1}A_{m}(\beta^{p^{n-m}tg^{ei}})\\&=\sum\limits_{i=0}^{\frac{p^{m-1}f}{\lambda_{m}}-1}Tr_{1}^{\lambda_{m}}(\beta^{p^{n-m}tg^{ei}}). \end{aligned}\] |
For \(D_{l}^{(m)}\) with \(0<l<e\), since \(D_{l}^{(m)}=g^{l}D_{0}^{(m)}\), then
| \[\begin{equation*} D_{l}^{(m)}(\beta^{p^{n-m}t})=\sum\limits_{i=0}^{\frac{p^{m-1}f}{\lambda_{m}}-1}Tr_{1}^{\lambda_{m}}(\beta^{p^{n-m}tg^{ei+l}}).\notag \end{equation*}\] |
Therefore, from Lemma 4 and (5), we obtain
| \[\begin{equation*} \!s(t)\!=\!\hat{S}(\beta^{t})\!=\rho_{*}+\sum\limits_{l=0}^{e-1}\sum\limits_{m=1}^{n}\rho_{l,m}\sum\limits_{i=0}^{\frac{p^{m-1}f}{\lambda_{m}}-1}Tr_{1}^{\lambda_{m}}(\beta^{p^{n-m}tg^{ei+l}}).\notag \end{equation*}\] |
The case of \(2\in D_{h}^{(m)}\) for any \(m(1\le m\le n, 0<h<e)\) can be proven similarly, so the proof is omitted here.
The proof is completed. \(\tag*{□}\)
Corollary 1: Let \(\textbf{s}\) be a sequence defined in (8), \(\rho_{*}\) and \(\rho_{l, m}(0\le l\le e-1, 1\le m\le n)\) be defined in (12). For \(1\le m\le n\), denote \(\rho_{m}=(\rho_{0, m},\rho_{1, m},\dots,\rho_{e-1, m})\). Then \(LC(\textbf{s})\), the complexity of \(\textbf{s}\) over \(\mathbb{Z}_{4}\), is given by \(LC(\textbf{s})= \varepsilon(\rho_{*})+\sum_{m=1}^{n}\omega_{H}(\rho_{m})p^{m-1}f\), where if \(\rho_{*}=0\), then \(\varepsilon(\rho_{*})=\)\(0\); otherwise \(\varepsilon(\rho_{*})=1\). And \(\omega_{H}(\rho_{m})\) denotes the number of non-zero terms \(\rho_{l,m}(0\le l\le e-1)\) in \(\rho_{m}\).
4. Conclusions
In this letter, we defined a class of balanced quaternary sequences of period \(p^{n}\) based on the generalized cyclotomic classes. Started from their defining polynomial, we determined the trace representation of these sequences over \(\mathbb{Z}_{4}\). And by determining the number of nonzero coefficients in the defining polynomial of these sequences, their linear complexity over \(\mathbb{Z}_{4}\) is obtained. When the value of \(n\) in period \(p^{n}\) is equal to \(1\), the family of quaternary sequences constructed in this letter becomes the case in [5]. Thus, the results in this letter can be regarded as generalizations of the work in [5].
References
[1] F. Adachi, D. Garg, S. Takaoka, and K. Takeda, “Broadband CDMA techniques,” IEEE Wireless Commun., vol.12, no.2, pp.8-18, April 2005.
CrossRef
[2] S.W. Golomb and G. Gong, Signal Design for Good Correlation for Wireless Communication, Cryptography, and Radar, Cambridge Univ. Press, Cambridge, U.K., 2005.
CrossRef
[3] J.L. Massey and T. Schaub, “Linear complexity in coding theory,” Coding Theory and Applications, Lecture Notes in Computer Science, vol.311, pp.19-32, 1988.
CrossRef
[4] Z.X. Chen, “Linear complexity and trace representation of quaternary sequences over ℤ4 based on generalized cyclotomic classes modulo pq,” Cryptogr. Commun., vol.9, pp.445-458, July 2017.
CrossRef
[5] Z.Y. Yang, Z.B. Xiao, and X.Y. Zeng, “Linear complexity and trace representation of balanced quaternary cyclotomic sequences of prime period p,” Cryptogr. Commun., vol.15, pp.921-940, Sept. 2023.
CrossRef
[6] P.H. Ke and S.Y. Zhang, “New classes of quaternary cyclotomic sequence of length 2pm with high linear complexity,” Inform. Process. Lett., vol.112, no.16, pp.646-650, 2012.
CrossRef
[7] V. Edemskiy, “The linear complexity and autocorrelation of quaternary Whiteman’s sequences,” International Journal of Applied Mathematics Electronics and Computers, vol.1, no.4, pp.7-11, Dec. 2013.
[8] Z.X. Chen and V. Edemskiy, “Linear complexity of quaternary sequences over ℤ4 derived from generalized cyclotomic classes modulo 2p,” International Journal of Network Security, vol.19, pp.613-622, 2016.
[9] Z.X. Wan, Lectures on Finite Fields and Galois Rings, World Scientific Publisher, pp.309-333, 2003.
CrossRef
[10] F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, Elsevier, 1977.
[11] Z. Dai, G. Gong, H.Y. Song, and D. Ye, “Trace representation and linear complexity of binary eth power residue sequences of period p,” IEEE Trans. Inf. Theory, vol.57, no.3, pp.1530-1547, March 2011.
CrossRef
[12] P. Udaya and M.U. Siddiqi, “Generalized GMW quadriphase sequences satisfying the Welch bound with equality,” Appl. Algebra Eng. Commun. Comput., vol.10, no.3, pp.203-225, March 2000.
CrossRef
[13] P. Ribenboim, The Book of Prime Number Records, Mathematical Gazette, vol.73, 1988.
CrossRef
[14] C.H. Wu, Z.X. Chen, and X.N. Du, “The linear complexity of q-ary generalized cyclotomic sequences of period pm,” J. Wuhan Univ. (Nat. Sci. Ed.), vol.59, no.2, pp.129-136, April 2013.
