1.   引言

伪随机序列在流密码、扩频通信、雷达导航、全球定位等领域中都有着极为重要的应用^[1]。伪随机序列的密码学性质，如周期性、相关性、线性复杂度、2-adic复杂度等直接影响着一个流密码算法的安全强度。其中线性复杂度是衡量伪随机序列性质的一个重要指标，根据Berlekamp-Massey(B-M)算法，若一个伪随机序列的线性复杂度大于其周期长度的1/2，则可称其为一个好的伪随机序列。

目前，已有大量的文献研究了广义分圆序列的线性复杂度。Ding^[2]基于Whiteman广义分圆理论构造了一类周期为$pq$的2元广义分圆序列，并证明了这类序列具有高的线性复杂度和低的自相关性；Bai等人^[3]基于Ding–Helleseth广义分圆理论构造了一类新的周期为$pq$的2元广义分圆序列，并确定了该类序列具有高的线性复杂度；李胜强等人^[4]基于Whiteman广义分圆理论，通过选取不同的特征集，构造了一类新的周期为$pq$的2元广义分圆序列，得出该类序列的线性复杂度的下界为$pq - p - q + 1$，并指出该类序列为平衡序列。Xiao等人^[5]构造了一类新的周期为${p^2}$的2元广义分圆序列，计算出了该类序列具有高的线性复杂度，最后提出了一类新的周期为${p^m}$的2元广义分圆序列，并给出了一个关于其线性复杂度的猜想；随后Edemskiy等人^[6]证明了这个猜想，并将其结果推广到了更一般的情形；Ouyang等人^[7]基于Edemskiy等人的工作构造了两类周期为$2{p^m}$的2元广义分圆序列，并给出了其线性复杂度的取值范围，结果表明这两类序列都具有好的线性复杂度性质。王艳等人^[8]研究了一类新的周期为$2{p^m}$的$q$阶2元广义分圆序列，并证明了该类序列具有高的线性复杂度；Wang等人^[9]构造了${F_4}$上的一类周期为$2{p^m}{q^n}$的4元广义分圆序列，证明了该类序列的线性复杂度可以达到最大；Ke等人^[10]构造了两类新的周期为$2{p^m}$的4元广义分圆序列，分别确定了这两类序列在${F_4}$和${Z_4}$上都具有高的线性复杂度。Du等人^[11]研究了${F_4}$上的周期为$2p$的4元广义分圆序列的线性复杂度，结果表明其最小值为$p + 1$；Chen等人^[12]确定了${Z_4}$上的周期为$2p$的4元广义分圆序列的线性复杂度，结果表明其最小值为$p$；杜小妮等人^[13]在Chen的基础上进行了推广，给出了${Z_4}$上周期为$2{p^2}$的4元广义分圆序列的线性复杂度，结果表明该类序列具有好的线性复杂度性质。本文基于文献[13]构造的序列，构造了一类${F_q}$上的周期为$2{p^2}$的4元广义分圆序列，并计算了该类序列在${F_q}$上的极小多项式和线性复杂度。本文结构安排如下：第2节给出了${F_q}$上一类周期为$2{p^2}$的4元广义分圆序列；第3节确定了该类序列在${F_q}$上的极小多项式和线性复杂度；第4节对文章的工作做了小结和展望。

2.   基础知识

设$p$是奇素数，$g$是奇数，且$g$是模$p,$$2p,$${p^2}$和$2{p^2}$的公共本原元。记模$2{p^2}$的剩余类环为${Z}_{2{p}^{2}}=$$\left\{0,1,\cdots ,2{p}^{2}-1\right\}$。

对$i = 0,1,$ 令

为了简便，本文记${P}_{0}=p\left({D}_{0}^{(2p)}\cup {D}_{1}^{(2p)}\right),$${P}_{1}=2p\left({D}_{0}^{(p)}\cup {D}_{1}^{(p)}\right),R=\left\{0\right\}$。显然，

构造${F_{{r^m}}}(r \ge 5)$上的4元广义分圆序列

设$r$是奇素数，$m$是正整数，${F_{{r^m}}}$是一个特征为$r$的扩域。设$\left\{ {s(t):t = 0,1, \cdots ,N - 1} \right\}$是${F_{{r^m}}}$上周期为$N$的序列。序列$\left\{ {s(t)} \right\}$在${F_{{r^m}}}$上的线性复杂度是生成序列的最短的线性反馈移位寄存器的级数，记为$LC(s)$，$L$是满足$s(t+L)={c}_{L-1}s(t+L-1)+\cdots +$${c}_{1}s(t+1)+{c}_{0}s(t)$，其中${\rm{ }}t \ge 0,{c_0},{c_1}, \cdots ,{c_{L - 1}} \in {F_{{r^m}}}$的最小正整数。序列$\left\{ {s(t)} \right\}$的极小多项式定义为$m(x) = {x^L} - \displaystyle\sum\nolimits_{i = 0}^{L - 1} {{c_i}{x^i}}$，生成多项式定义为$S(x) =$$\displaystyle\sum\nolimits_{i = 0}^{N - 1} {s(t){x^t}}$，极小多项式和生成多项式的关系为$m(x)=\dfrac{{x}^{N}-1}{{\rm{gcd}}({x}^{N}-1,S(x))}$。序列$\left\{ {s(t)} \right\}$的线性复杂度表示为

设$m={\rm{ord}}_{{p}^{2}}\left(r\right)$，$\beta$是扩域${F_{{r^m}}}$上的$2{p^2}$次单位根，由式(4)可得

记模$N$的$d$阶分圆数为${(i,j)}^{(N)}=\left|({D}_{i}^{(N)}+1)\cap$${D}_{j}^{(N)}\right|, \;i,j=0,1,\cdots ,d-1$。

3.   主要结论及证明

3.1   主要定理及辅助引理

定理1　设$r$为奇素数，且满足$r \ge 5, {\rm{ }}r \ne p$, $m = {\rm{or}}{{\rm{d}}_{{p^2}}}(r)$，并设$\beta$为扩域${F_{{r^m}}}$上的$2{p^2}$次单位根。由式(3)定义的周期为$2{p^2}$的4元广义分圆序列$\left\{ {s(t)} \right\}$在${F_{{r^m}}}$上的线性复杂度为

下面给出证明定理1所需的引理。

引理1^[10,14]　设$p$为奇素数，有

(1) ${\rm{2}} \in D_{\rm{0}}^{({p^{\rm{2}}})}$当且仅当${\rm{2}} \in D_{\rm{0}}^{(p)}$，${\rm{2}} \in D_{\rm{0}}^{(p)}$当且仅当$p\equiv \pm 1({\rm{mod}}\;8)$。

(2) ${\rm{2}} \in D_1^{({p^{\rm{2}}})}$当且仅当${\rm{2}} \in D_1^{(p)}$，${\rm{2}} \in D_1^{(p)}$当且仅当$p\equiv \pm 3({\rm{mod}}\;8)$。

引理2^[14]　设$p$为奇素数，有

(1)若$t \in Z_{2{p^2}}^ * ,i = 0,1,j = 1,2$，则

(2)若$t \in Z_{{p^2}}^ * ,i = 0,1,j = 1,2$，则

引理3　设$a$为正整数，$p$为奇素数，若$i,j \in$$\left\{ {0,1} \right\}$，则

(1) 若$a \in D_i^{(2{p^2})},$ 则$a{P_j} = {P_j}$；

(2) 若$a \in 2D_i^{({p^2})},$ 则$aD_j^{(2{p^2})} = 2D_{i + j(\boldsymbolod 2)}^{({p^2})},{\rm{ }}$$a{P_j} = {P_1}$；

(3) 若$a \in {P_0},$ 则$aD_i^{(2{p^2})} = {P_0},{\rm{ }}a \cdot 2D_i^{({p^2})} = {P_1},{\rm{ }}$$a{P_0} = {p^2},{\rm{ }}a{P_1} = R$；

(4) 若$a \in {P_1},$ 则$aD_i^{(2{p^2})} = a \cdot 2D_i^{({p^2})} = {P_1},$$a{P_i} = R$；

(5) $D_i^{({p^2})}(\boldsymbolod p) \;=\; D_i^{(p)},\;\;D_i^{(2{p^2})}(\boldsymbolod {p^2}) =$$D_i^{({p^2})}$ 。

证明　(1)—(4)的证明可参考文献[13]。下证(5)：

因为$g$是模$p$和${p^2}$的公共本原元，所以

同理可得$D_i^{(2{p^2})}(\boldsymbolod {p^2}) = D_i^{({p^2})}$。证毕

引理4　设$p$为奇素数，有

证明　根据引理1可得。

引理5　设$p$为奇素数，$\beta$为扩域${F_{{r^m}}}$上的$2{p^2}$次单位根，$r$为奇素数，且满足$r \ge 5,{\rm{ }}r \ne p,$有

证明　由$\beta$为${F_{{r^m}}}$上的$2{p^2}$次单位根可得${\beta ^{{p^2}}} = - 1$，所以$k$为偶数时，${\beta ^{{p^2}k}} = 1,$ $k$为奇数时，${\beta ^{{p^2}k}} = - 1$。

证毕

引理6　设$p$为奇素数，$\beta$为${F_{{r^m}}}$上的$2{p^2}$次单位根，有

其中$k\in {D}_{0}^{(2{p}^{2})}\cup {D}_{1}^{(2{p}^{2})}\cup 2{D}_{0}^{({p}^{2})}\cup 2{D}_{1}^{({p}^{2})}$。

证明　由${\beta ^0} + {\beta ^{{p^2}}} + \displaystyle\sum\nolimits_{t \in D_0^{(2{p^2})}} {{\beta ^t}} + \displaystyle\sum\nolimits_{t \in D_1^{(2{p^2})}} {{\beta ^t}} +$$\displaystyle\sum\nolimits_{t \in 2D_0^{({p^2})}} {{\beta ^t}} + \displaystyle\sum\nolimits_{t \in 2D_1^{({p^2})}} {{\beta ^t}} + \displaystyle\sum\nolimits_{t \in {P_0}} {{\beta ^t}} + \displaystyle\sum\nolimits_{t \in {P_1}} {{\beta ^t}} = 0$可得。

引理7　设$p$为奇素数，$\beta$为${F_{{r^m}}}$上的$2{p^2}$次单位根，有${\displaystyle \sum\nolimits_{i\in {P}_{1}}{\beta }^{i}}=-1,{ }{\displaystyle \sum\nolimits_{i\in {P}_{0}}{\beta }^{i}}=1$。

证明　由${\beta ^{2{p^2}}} - 1 = ({\beta ^p} - 1)(1 + {\beta ^p} + {\beta ^{2p}} + \cdots +$${\beta ^{(2p - 1)p}})$${\rm{ = (}}{\beta ^{2p}} - 1{\rm{)(}}1 + {\beta ^{2p}} + {\beta ^{2 \cdot 2p}} + \cdots + {\beta ^{(p - 1) \cdot 2p}}{\rm{)}}$ = 0，可得

即

于是$1{\rm{ + }}\displaystyle\sum\nolimits_{i \in 2pD_0^{\left( p \right)} \cup 2pD_1^{\left( p \right)}} {{\beta ^i}} = 0,$ 进而$\displaystyle\sum\nolimits_{i \in {P_1}} {{\beta ^i}} =$$- 1$, $\displaystyle\sum\nolimits_{i \in {P_0}} {{\beta ^i}} = 1$。证毕

引理8　设$p$为奇素数，$r$为奇素数，且满足$r \ge 5,r \ne p,$ $\beta$为${F_{{r^m}}}$上的$2{p^2}$次单位根，则有

其中$k\in {D}_{0}^{(2{p}^{2})}\cup {D}_{1}^{(2{p}^{2})}\cup 2{D}_{0}^{({p}^{2})}\cup 2{D}_{1}^{({p}^{2})}。$。

证明　记${M_{{p^2}}} \,=\, 2 \cdot ({2^{ - 1}}(\,\boldsymbolod {p^2}\,))\,(\boldsymbolod 2{p^2})$, ${M}_{2}={p}^{2}\cdot ({p}^{2\bullet \left(-1\right)}({\rm{mod}}\;2))({\rm{mod}}\;2{p}^{2})$, $Z_2^ *$表示${Z_2}$中所有可逆元素的集合。当$t\in {D}_{1}^{(2{p}^{2})}{\rm{，}}{\text{且}} j\equiv t({\rm{mod}}\;{p}^{2})$时，构造从$D_1^{(2{p^2})}$到$Z_2^ * \times D_1^{({p^2})}$的同构

由中国剩余定理可得${\rm{ }}t \equiv 1 \cdot {M_2}{\rm{ + }}j \cdot {M_{{p^2}}}(\boldsymbolod 2{p^2})$$\equiv {p^2} + j \cdot 2 \cdot ({2^{ - 1}}(\boldsymbolod {p^2}))(\boldsymbolod 2{p^2})$，所以

证毕

引理9　若$p\equiv 1({\rm{mod}}\;4)$，则$- 1 \in D_0^{(p)}{\rm{ }}$；若$p\equiv 3({\rm{mod}}\;4)$，则 $-1\in {D}_{1}^{(p)}$。

证明　当$p \equiv 1(\boldsymbolod 4)$时，不妨设$p = 4t + 1$，$t$为正整数。因为${\rm{or}}{{\rm{d}}_p}(g) = p - 1$，即${g^{p - 1}} \equiv$$1(\boldsymbolod p)$，所以有${g^{4t}} - 1 \equiv 0(\boldsymbolod p)$。又因为${g^{4t}} - 1 = ({g^{2t}} + 1)({g^{2t}} - 1)$，且$g$为模$p$的本原根，所以有${g^{2t}} - 1 \equiv /0(\boldsymbolod p)$, ${g^{2t}} + 1 \equiv 0(\boldsymbolod p)$，故$- 1 \equiv {g^{2t}}(\boldsymbolod p)$，即$-1\in {D}_{0}^{\left(p\right)}$。

当$p \equiv 3(\boldsymbolod 4)$时，记$p = 4t + 3$，$t$为正整数，同理可得$-1\in {D}_{1}^{\left(p\right)}$。证毕

引理10^[15]　设$p$是一个奇素数。若$p\equiv 1$$({\rm{mod}}\;4)$，则

若$p\equiv 3({\rm{mod}}\;4)$，则

引理11　设$p$为奇素数，$\beta$为${F_{{r^m}}}$上的$2{p^2}$次单位根，${\eta _0} = \displaystyle\sum\nolimits_{i \in 2D_0^{({p^2})}} {{\beta ^i}} ,{\eta _1} = \displaystyle\sum\nolimits_{i \in 2D_1^{({p^2})}} {{\beta ^i}}$，则有${\eta _0}{\rm{ = }}{\eta _1}{\rm{ = }}0$。

证明　设$\gamma ={\beta }^{2}$，因为$\beta$是扩域${F_{{r^m}}}$上的$2{p^2}$次单位根，所以$\gamma$是扩域${F_{{r^m}}}$上的${p^2}$次单位根。记$d = \dfrac{{p(p - 1)}}{2}$，可得

由引理3可知当$k$跑遍$\left\{0，1，\cdots ，d-1\right\}$时，$D_1^{({p^2})}(\boldsymbolod p)$取$D_1^{\left( p \right)}$中每个元素$p$次。下面分两种情况计算${\eta _0}{\eta _1}$。

(1)当$p\equiv 1({\rm{mod}}\;4)时$，根据引理9知$- 1 \in D_0^{(p)}$，即对任意的$t$，有${g^{2t + 1}} \equiv - 1(\boldsymbolod p),$ 其中$0 \le$$t \le d - 1$。存在${v_1},{v_2}$，使得${g^{2{v_1} + {v_2}}} = 1 + {g^{2t + 1}},$ 其中$0\le {v}_{1}\le d-1,0\le {v}_{2}\le 1$。当$t$确定时，有

(a) 若${v_2} = 0,$则${g}^{2{v}_{1}}=1+{g}^{2t+1}$。由$1 +$${g^{2t + 1}} \in 1{\rm{ + }}D_1^{({p^2})}$, ${g^{2{v_1}}} \in D_0^{({p^2})}$，知${g^{2{v_1}}} = 1 + {g^{2t + 1}} \in$$\left(\left(D_1^{({p^2})} + 1\right) \cap D_0^{({p^2})}\right)$，即${g^{2{v_1}}} = 1 + {g^{2t + 1}}$有$\left| (D_1^{({p^2})} + 1)$$\cap D_0^{({p^2})} \right|$个解。由分圆数定义，${g^{2{v_1}}} = 1 + {g^{2t + 1}}$有${(1,0)^{({p^2})}}$个解。

(b) 若${v_2} = 1$，则${g}^{2{v}_{1}{+}1}=1+{g}^{2t+1}$。由${g^{2{v_1} + 1}} \in D_1^{({p^2})},$知${g^{2{v_1} + 1}} = 1 + {g^{2t + 1}} \in \Bigr(\left(D_1^{({p^2})} + 1\right)$$\cap D_1^{({p^2})}\Bigr),$ 即${g^{2{v_1} + 1}} = 1 + {g^{2t + 1}}$有$\left| {(D_1^{({p^2})} + 1) \cap D_1^{({p^2})}} \right|$个解。由分圆数定义，${g^{2{v_1}{\rm{ + }}1}} = 1 + {g^{2t + 1}}$有${(1,1)^{({p^2})}}$个解。

所以当$t$跑遍$\left\{0，1，\cdots ，d-1\right\}$时，${g^{2{v_1} + {v_2}}} =$$1 + {g^{2t + 1}}$有${(1,{v}_{2})}^{({p}^{2})}$个解，因而

(2)当$p\equiv 3({\rm{mod}}\;4)时$，根据引理9知$- 1 \in D_1^{\left( p \right)},$则存在$t$，使得${g^{2t + 1}} \equiv - 1(\boldsymbolod p),$ 即${g^{2t + 1}} + 1 \equiv$$0(\boldsymbolod p),$其中$0\le t\le d-1$。设$L = \left\{ t:{g^{2t + 1}} {\not{\equiv }}$$- 1(\boldsymbolod p),0 \le t \le d - 1 \right\}$。注意到${g^{2t + 1}} + 1 \equiv 0$$(\boldsymbolod p)$有$p$个不同的解，当$t$跑遍$\left\{ {0,1, \cdots ,d - 1} \right\}$时，${g^{2t + 1}} + 1$恰好取$p{Z_p}$中每个元素1次。当$k$跑遍$\left\{0, 1，\cdots ,d-1\right\}$时，${g^{2k}}({g^{2t + 1}} + 1)$恰好取$p{Z_p}$中每个元素$d$次。与(1)类似有${\displaystyle \sum\nolimits _{k=0}^{d-1}{\gamma }^{{g}^{2k}({g}^{2t+1}+1)}}=$${\displaystyle \sum\nolimits _{k=0}^{d-1}{\gamma }^{{g}^{2k}({g}^{2k+1}+1)}}={\eta }_{{v}_{2}}$，且${g^{2{v_1} + {v_2}}} = 1 + {g^{2t + 1}}$有${(1,{v}_{2})}^{({p}^{2})}$个解。

所以可得

根据引理6、引理7和引理10知${\eta }_{0}{+}{\eta }_{1}=0$，且${\eta }_{0}{\eta }_{1}=0$，所以得 ${\eta _0}{\rm{ = }}{\eta _1}{\rm{ = }}0$。　证毕

序列$\left\{ {s(t)} \right\}$的生成多项式为

引理12　设$p$为奇素数，$\beta$为${F_{{r^m}}}$上的$2{p^2}$次单位根，$r$为奇素数，且满足$r \ge 5,{\rm{ }}r \ne p,$ 则当$k \in {Z_{2{p^2}}}$时，$S({\beta ^k})$的值可以确定为

证明　设$\gamma ={\beta }^{2}$，即$\gamma$为${p^2}$次单位根。由式(26)，

当$k = 0$时，有

当$k = {p^2}$时，根据引理5，有

当$k \in {P_0}$时，根据引理3和引理5，有

当$k \in {P_1}$时，根据引理3和引理5，有

下面讨论当$k \in D_0^{(2{p^2})} \cup D_1^{(2{p^2})} \cup 2D_0^{({p^2})} \cup 2D_1^{({p^2})}$时$S({\beta ^k})$的值，为了简便，记$2_{{p^2}}^{ - 1} = {2^{ - 1}}(\boldsymbolod {p^2}),$根据引理8可得

接下来分两种情况讨论：

(1)当$p \equiv \pm 1(\boldsymbolod 8)$时，根据引理4知$2_{{p^2}}^{ - 1} \in$$D_0^{({p^2})}$，所以

(a) $k \in D_0^{(2{p^2})} \cup D_1^{(2{p^2})}$时，根据引理2，引理5和引理7可得

(b) $k \in 2D_0^{({p^2})} \cup 2D_1^{({p^2})}$时，根据引理5，引理6和引理7可得

(2) 当$p \equiv \pm 3(\boldsymbolod 8)$时，根据引理4知$2_{{p^2}}^{ - 1} \in$$D_1^{({p^2})}$，所以

(a)$k \in D_0^{(2{p^2})} \cup D_1^{(2{p^2})}$时，根据引理5和引理7可得

(b)$k \in 2D_0^{({p^2})}$时，存在$k,{\rm{ }}k = 2n,{\rm{ }}n \in D_0^{({p^2})}$，根据引理2可得

根据引理5和引理7可得

(c)$k \in 2D_1^{({p^2})}$时，同理存在$k,{\rm{ }}k = 2n, {\rm{ }}n \in D_1^{({p^2})}$，根据引理2、引理5和引理7可得

证毕

3.2   定理1的证明

证明　由引理12知$S({\beta ^k})$取值有$3{p}^{2}+p-2,$${p}^{2}-2,p-4,p-2$，要确定序列$s(t)$的线性复杂度，则需考虑这4种情况的不同组合，分别讨论如下：

(1)若$r\left| {3{p^2} + p - 2} \right.$，则极小多项式为$m(x) =$$\dfrac{{{x^{2{p^2}}} - 1}}{{x - 1}}$，线性复杂度为$LC(s) = 2{p^2} - 1$。

(2)若$r\left| {{p^2} - 2} \right.$，则极小多项式为$m(x) =$$\dfrac{{{x^{2{p^2}}} - 1}}{{x - {\beta ^{{p^2}}}}},$ 线性复杂度为 $LC(s) = 2{p^2} - 1$。

(3)若$r\left| {p - 4} \right.$，则极小多项式为$m(x) =$$\dfrac{{{x^{2{p^2}}} - 1}}{{\displaystyle\prod\limits_{k \in {P_0}} {(x - {\beta ^k})} }}$，线性复杂度为 $LC(s) = 2{p^2} - p + 1$。

(4)若$r\left| {p - 2} \right.$，则极小多项式为$m(x) =$$\dfrac{{{x^{2{p^2}}} - 1}}{{\displaystyle\prod\limits_{k \in {P_1}} {(x - {\beta ^k})} }}$，线性复杂度为 $LC(s) = 2{p^2} - p + 1$。

(5)若$r|3{p}^{2}+p-2{\text{且}}r|{p}^{2}-2$，则极小多项式为$m(x) = \dfrac{{{x^{2{p^2}}} - 1}}{{(x - 1)(x - {\beta ^{{p^2}}})}}$，线性复杂度为$LC(s) = 2{p^2} - 2$。

(6)若$r|{p}^{2}-2{\text{且}}r|p-4$，则极小多项式为$m(x) = \dfrac{{{x^{2{p^2}}} - 1}}{{(x \,-\, {\beta ^{{p^2}}})\displaystyle\prod\limits_{k \in {P_0}} {(x \,-\, {\beta ^k})} }}$，线性复杂度为$LC(s) = 2{p^2} - p$。

(7)若$r|3{p}^{2}+p-2{\text{且}}r|p-4$，则极小多项式为$m(x) = \dfrac{{{x^{2{p^2}}} - 1}}{{(x - 1)\displaystyle\prod\limits_{k \in {P_0}} {(x - {\beta ^k})} }}$，线性复杂度为$LC(s) =$$2{p^2} - p$。

(8)若$r|p-2{\text{且}}r|{p}^{2}-2$，则极小多项式为$m(x) =$$\dfrac{{{x^{2{p^2}}} - 1}}{{(x - {\beta ^{{p^2}}})\displaystyle\prod\limits_{k \in {P_1}} {(x - {\beta ^k})} }}$，线性复杂度为$LC(s) =$$2{p^2} - p$。

(9)若$r|3{p}^{2}+p-2{\text{且}}r|p-2$，则极小多项式为$m(x) = \dfrac{{{x^{2{p^2}}} - 1}}{{(x - 1)\displaystyle\prod\limits_{k \in {P_1}} {(x - {\beta ^k})} }}$，线性复杂度为$LC(s) =$$2{p^2} - p$。

(10)若$r|3{p}^{2}+p-2{\text{且}}r|{p}^{2}-2{\text{且}}r|p-4$，则极小多项式为$m(x)=\dfrac{{x}^{2{p}^{2}}-1}{(x-1)(x-{\beta }^{{p}^{2}}){\displaystyle \prod _{k\in {P}_{0}}(x-{\beta }^{k})}}$，线性复杂度为$LC(s) = 2{p^2} - p - 1$。

(11)若$r|3{p}^{2}+p-2{\text{且}}r|{p}^{2}-2{\text{且}}r|p-2$，则极小多项式为$m(x) = \dfrac{{{x^{2{p^2}}} - 1}}{{(x - 1)(x - {\beta ^{{p^2}}})\displaystyle\prod\limits_{k \in {P_1}} {(x - {\beta ^k})} }}$，线性复杂度为$LC(s) = 2{p^2} - p - 1$。

(12)若$r{\not |}3{p}^{2}+p-2{\text{且}}r{\not |}{p}^{2}-2{\text{且}}r{\not |}p-4{\text{且}}$$r {\not |}p-2$，则极小多项式为$m(x) = {x^{2{p^2}}} - 1,$ 线性复杂度为$LC(s) = 2{p^2}$。　证毕

注　如果$r|p-4{\text{且}}r|p-2$，那么有$p\equiv 4 \left({\rm{mod}}\;r\right),$$p\equiv 2\left({\rm{mod}}\;r\right)$，则$4 \equiv 2\left( {\boldsymbolod r} \right),$ $2 \equiv 0\left( {\boldsymbolod r} \right)$。因为$r$为奇素数，且$r \ge 5$，所以这两种情况不同时发生。

通过使用Magma，我们计算下面的例子来验证本文的结果。

例1　设$p = 5,g = 3,r = 7$，则周期为50的4元广义分圆序列为00312121303031212130303122213030312121303031212130。

由Magma计算得$LC(s) = 2{p^2} - p + 1 = 92$，且$r,p$符合文中的第(12)种情况$r{\not |}3{p^2} + p - 2 {\text{且}}$$r{\not |}{p^2} - 2$且 $r{\not |}p - 4{\text{且}}r{\not |}p - 2$。

例2　设$p = 7,g = 3,r = 5$，则周期为98的4元广义分圆序列为00313121302021303131213020213031312130202130313122302021303131213020213031312130202130313121302021。

由Magma计算得$LC(s)=2{p}^{2}-p+1=92$，且$r,p$符合文中的第(4)种情况$r\left| {p - 2} \right.$。

例3　设$p = 7,g = 3,r = 11$，则由Magma计算得$LC(s) = 2{p^2} = 98,$且$r,p$ 符合文中的第(12)种情况$r{\not |}3{p^2} + p - 2{\text{且}}r{\not |}{p^2} - 2{\text{且}}r{\not |}p - 4{\text{且}}r{\not |}p - 2$。

例4　设$p = 11,g = 7,r = 17$，则周期为242的4元广义分圆序列为00302031303121202131213030203130312120213121303020313031212021312130302031303121202131213030203130312120213121303020313033212021312130302031303121202131213030203130312120213121303020313031212021312130302031303121202131213030203130312120213121。

由Magma计算得$LC(s)=2{p}^{2}-1=241$，且$r,p$符合文中的第(2)种情况$r\left| {{p^2} - 2} \right.$。

例5　设$p = 17,g = 3,r = 7$，则周期为578的4元广义分圆序列为003131213021202031302021203121313030313121302120203130202120312131303031312130212020313020212031213130303131213021202031302021203121313030313121302120203130202120312131303031312130212020313020212031213130303131213021202031302021203121313030313121302120203130202120312131303031312130212020333020212031213130303131213021202031302021203121313030313121302120203130202120312131303031312130212021302021203121313030313121302120203130202120312131303031312130212020313020212031213130303131213021202031302021203121313030313121302120203130202120312131303031312130212020313020212031213130。

由Magma计算得$LC(s)=2{p}^{2}-2=576$，且$r,p$符合文中的第(5)种情况 $r|3{p}^{2}+p-2{\text{且}}r|{p}^{2}-2$。

4.   结束语

本文基于杜小妮等人^[13]的工作，构造了一类周期为$2{p^2}$的4元广义分圆序列，研究了这类序列在${F_q}$上的极小多项式和线性复杂度。结果表明，这类序列在${F_q}$上的线性复杂度的最小值为$2{p^2} - p - 1$，大于其周期的1/2，即这类序列有高的线性复杂度，能够有效地抵抗B-M算法的攻击。后期研究该类序列4-adic复杂度也将是有意义的工作。