1.   引言

伪随机序列在通信系统、雷达系统及流密码等方面有着极其广泛的应用^[1]。在密码学领域的应用中，序列的线性复杂度性质是影响序列伪随机性的一个重要指标，为了能够抵抗B-M(Berlekamp-Massey)算法的攻击，一般要求序列的线性复杂度不小于其周期长度的一半。

已有大量文献研究了序列的线性复杂度，其中文献[2—6]研究了二元序列的线性复杂度，文献[7]确定了有限域 ${F_4}$ 上一类四元序列的线性复杂度，文献[8—10]计算了Galois环 ${Z_4} = \left\{ {0,1,2,3} \right\}$ 上四元序列的线性复杂度，文献[11]给出了 ${Z_4}$ 上基于模 $2p$ ( $p$ 为奇素数)的广义分圆的一类四元序列的线性复杂度，而周期为 $2{p^2}$ 的四元序列尚未研究。因而，本文在文献[11]的基础上进行了推广，基于模 $2{p^2}$ 的广义分圆定义了一类 ${Z_4}$ 上的新四元序列，并求出了该序列的线性复杂度。值得一提的是，由于 ${Z_4}$ 上的零因子使得计算变得困难，所以本文基于特征为4的Galois环理论来进行研究。

设 $p$ 是奇素数， $g$ 是奇数，且 $g$ 是模 ${p^2}$ 和模 $2{p^2}$ 的公共本原元^[12]。设 $S$ 是集合，定义 $aS \triangleq \{ \!au\;{\rm{ }}(\!od 2{p^2})\!\!:$ $u \in S\}$ , $a + S \triangleq \{ a + u\;{\rm{ }}(\!od 2{p^2}):u \in S\}$ 。模 $2{p^2}$ 的剩余类环为 ${Z_{2{p^2}}} = \{ 0,1, ·\!·\!· ,2{p^2} - 1\}$ 。对 $i = 0,1$ ，令 ${D_i} \!=\!\! \left\{ {g^{2k + i}}\;{\rm{ }}(\!od {\rm{ }}2{p^2}),{\rm{ }}k \!=\! 0,1, ·\!·\!· ,\displaystyle\frac{{p(p - 1)}}{2} - 1 \right\}$ ，且 ${E_i} = 2{D_i}$ , ${P_0} = pZ_{2p}^*$ , ${P_1} = 2{P_0}$ ，即有 ${Z_{2{p^2}}} =$ $\bigcup _{i = 1}^1 {({D_i} \cup {E_i} \cup {P_i}) \cup \{ 0,{p^2}\} }$ 。显然， ${D_0} \cup {D_1} \cup {P_0}$ 是 ${Z_{2{p^2}}}\backslash \{ {p^2}\}$ 中所有奇数的集合， ${E_0} \cup {E_1} \cup {P_1}$ 是 ${Z_{2{p^2}}}\backslash \{ 0\}$ 中所有偶数的集合。定义 ${Z_4}$ 上的四元序列 $({e_u})$ 为

下文将讨论序列 $({e_u})$ 的线性复杂度^[13]。 $({e_u})$ 的线性复杂度定义为满足 ${e_{u + L}} +{c_1}{e_{u + L - 1}} + ·\!·\!· +$ ${c_{L - 1}}{e_{u + 1}} + {c_L}{e_u} = 0,{\rm{ }}u \ge 0,{\rm{ }}{c_1},{c_2}, ·\!·\!·,{c_L} \in {Z_4}$ 的最小正整数 $L$ 。令 $C(x) = 1 + {c_1}x + ·\!·\!· +{c_L}{x^L} \in$ ${Z_4}[x]$ ，显然 $C(0) = 1$ 。设 $({e_u})$ 的生成多项式为 $E(x) =$ ${e_0} + {e_1}x + ·\!·\!· + {e_{2{p^2} - 1}}{x^{2{p^2} - 1}} \in {Z_4}[x]$ ，则

2.   主要结论及其证明

2.1   主要结论

定理 1　 $({e_u})$ 的线性复杂度满足

2.2   辅助引理

本小节给出证明主要结论所需的引理。如无特殊说明，本文中的多项式均属于 ${Z_4}[x]$ 。

设 $r$ 为2模 ${p^2}$ 的阶，记 ${\rm{GR}}({4^r},4)$ 是阶为 ${4^r}$ 且特征为4的Galois环，同构于剩余类环 ${Z_4}[x]\backslash f(x)$ ，其中 $f(x) \in {Z_4}[x]$ 是次数为 $r$ 的基本不可约多项式^[14]。记 ${\rm{GR}}({4^r},4)$ 的单位群为 ${\rm{G}}{{\rm{R}}^{\rm{*}}}({4^r},4)$ ，因为 ${p^2}|({2^r} - 1)$ ，所以 ${\rm{G}}{{\rm{R}}^{\rm{*}}}({4^r},4)$ 包含了一个 ${2^r} - 1$ 阶的循环子群。任取 $\beta \in {\rm{G}}{{\rm{R}}^{\rm{*}}}({4^r},4)$ ，且阶为 ${p^2}$ 。取

$\gamma = 3\beta \in {\rm{G}}{{\rm{R}}^{\rm{*}}} ({4^r},4)$

则 $\gamma$ 的阶为 $2{p^2}$ 。由式(1)，为确定 $({e_u})$ 的线性复杂度，需计算 $E({\gamma ^v})$ , $v = 0,1, ·\!·\!· ,2{p^2} - 1$ 的值。

引理 1^[11] 　设非零次多项式 $F(x) \in {Z_4}[x]$ ，若 $\xi ,{\rm{ }}\eta \in {\rm{GR}}({4^r},4)$ 满足 $F(\xi ) = F(\eta ) = 0$ ，且 $\eta - \xi \in$ ${\rm{G}}{{\rm{R}}^{\rm{*}}}({4^r},4)$ ，则存在 ${F_1}(x)$ , ${F_2}(x)$ 使得 $F(x) = (x - \xi )$ $·{F_1}(x) = (x - \xi )(x - \eta ){F_2}(x)$ ，其中 ${F_1}(x) = (x - \eta )$ $·{F_2}(x)$ 。

引理 2　(1) 若 $F({\gamma ^v}) = 0{\rm{ }}$ , $v \in A$ ，则存在 ${F_A}(x) \in {\rm{GR}}({4^r},4)[x]$ 使得

$\quad\quad\quad\quad F(x) = {F_A}(x)\displaystyle\prod\limits_{v \in A} {(x - {\gamma ^v})}$

其中， $A$ 取为 ${D_i}$ ，或 ${E_i}$ ，或 ${P_i}$ , $i = 0,1$ 。

(2) 若 $F({\gamma ^v}) = 0$ , $v \in \{ {p^2}\} \cup {D_0} \cup {D_1} \cup {P_0}$ ，则存在 ${F_3}(x) \in {\rm{GR}}({4^r},4)[x]$ 使得 $F(x) = {F_3}(x)({x^{{p^2}}}$ $+ 1)$ 。

(3) 若 $F(0) = 1$ , $F({\gamma ^v}) = 0{\rm{ }}$ , $v \in {Z_{2{p^2}}}\backslash \{ 0,{p^2}\}$ ，且 $F( \pm 1) \in \{ 0,2\}$ ，则有 $\deg (F(x)) \ge 2{p^2} - 1$ 。进一步，若 $F( \pm 1) = 0$ 或 $F( \pm 1) = 2$ ，则 ${\rm deg} (F(x))$ $\ge 2{p^2}$ 。

证明　(1) 只证 $A = {D_i}$ 的情形，其它情形同理可得。由 $\gamma$ 的选择，有 $\displaystyle\frac{{({x^{{p^2}}} - 1)}}{{(x - 1)}} = \prod\limits_{m = 1}^{{p^2} - 1} {(x - {\gamma ^{2m}})}$ ，因此 ${p^2} = \displaystyle\prod\nolimits_{m = 1}^{{p^2} - 1} {(1 - {\gamma ^m})} (1 + {\gamma ^m})$ ，所以当 $0 \le m,$ $n < 2{p^2}$ 且 $m \equiv \!\!\!\!\!\!/\;n\;{\rm{ }}(od {p^2})$ 时， ${\gamma ^m} - {\gamma ^n} \in {\rm{G}}{{\rm{R}}^{\rm{*}}}({4^r},$ $4)$ ，从而，当 $F(\gamma ) = 0$ , $m \in {D_i}$ 时，由引理1得， $\displaystyle\prod\nolimits_{m \in {D_i}} {(x - {\gamma ^m})} |F(x)$ ，即该引理得证。

(2) 由(1)可得。

(3) 不妨设 $F( - 1) = 0$ 。因为 $F(0) = 1$ ，则由(2)得 $F(x) = \left({x^{{p^2}}} + 1\right){F_3}(x)$ ，且 $2{F_3}(x) \ne 0$ ，显然 $\left({x^{{p^2}}} - 1\right)/(x - 1)|2{F_3}(x)$ ，从而 $\deg (F(x)) \ge 2{p^2}$ –1。进一步，若 $F(1) = 0$ ，则 $\deg (F(x)) \ge 2{p^2}$ 。令 $F( \pm 1) \ne 0$ ，则 $F( \pm 1) = 2$ 且 $F({\gamma ^m}) = 0{\rm{ }}$ , $m \in {D_0}$ $\cup {D_1} \cup {P_0}$ 。由(1)存在 $Q(x) \in {Z_4}[x]$ ，使得 $F(x) =$ $Q(x)\left({x^{{p^2}}} + 1\right)/(x + 1)$ ，且 $2Q(x) \ne 0$ ，不难得到Q $(- 1) \!=\! 2$ ，则存在 $G(x) \in {Z_4}(x)$ 使得 $Q(x) \!=\!(x \!+\! 1)$ $\cdot G(x) + 2$ ，即有， $F(x) = \left({x^{{p^2}}} + 1\right)$ $·G(x)$ $+ 2\left({x^{{p^2}}} \right.$ $\left.+ 1\right)/(x \!+\! 1)$ 。所以 $\left({x^{{p^2}}} \!-\! 1\right)|2F(x)$ ，即有 $\deg (F(x)) \ge$ $2{p^2}$ 。 证毕

除特殊说明外，本文中集合的下标均模2，且 $i,j \in \{ 0,1\}$ 。

引理 3　(1) $v \in {D_i}$ ，则 $v{D_j} = {D_{i + j}}$ , $v{E_j} = {E_{i + j}}{\rm{ }}$ , $v{P_j} = {P_j}$ 。

(2) 若 $v \in {E_i}$ ，则 $v{D_j} = {E_{i + j}}{\rm{ }}$ , ${\rm{ }}v{P_j} = {P_1}$ ，且

(3) 若 $v \in {P_0}$ ，则 $v{D_j} = {P_0}$ , $v{E_j} = {P_1}$ , $v{P_j} =$ ${P_j}$ 。

(4) 若 $v \in {P_1}$ ，则 $v{D_j} = v{E_j} = v{P_j} = {P_1}{\rm{ }}$ 。

(5) ${P_0} = {p^2} + {P_1}$ , ${P_1} = {p^2} + {P_0}$ 。

(6) 若 $p \equiv \pm 1{\rm{ }}\;(\!od 8)$ ，则 ${D_i} = {p^2} + {E_i}$ , ${E_i} = {p^2}$ $+{D_i}$ ；若 ${\rm{ }}p \equiv \pm 3{\rm{ }}\;(\!od 8)$ ，则 ${D_{i + 1}} =$ ${p^2} + {E_i}{\rm{ }}$ , ${E_{i + 1}} =$ ${p^2} + {D_i}$ 。

证明　(1) 只证 $v{D_j} = {D_{i + j}}$ ，其余同理可证。对任意给定的 $v \in {D_i}$ ，若 $u \in {D_j}$ ，则有 $v = {g^{i + 2k}}$ $(\!od 2{p^2})$ , $u = {g^{j + 2l}}\;(\!od 2{p^2})$ , $0 \le k,l < \displaystyle\frac{{p(p - 1)}}{2}$ ，所以 $vu = {g^{i + j + 2(k + l)}}\;(\!od 2{p^2})$ ，因此 $vu \in {D_{i + j}}$ 。又因为 $\left| {v{D_j}} \right| = \left| {{D_{i + j}}} \right|$ ，所以 $v{D_j} = {D_{i + j}}$ 。

(2) 仅考虑 $v{E_j}$ ，其余证明同(1)。首先，从 (1) 得 $v{E_j} = 2u{E_j} = 2{E_{i + j}}$ 。显然，对任意的 $\omega \in 2{E_{i + j}}$ ，有 $\omega \equiv 4a{\rm{ }}\;(\!od 2{p^2})$ , $a \in {D_{i + j}}$ ，即 $\omega \in {E_0} \cup {E_1}$ ，则存在 $b \in {D_0} \cup {D_1}$ 使得 $\omega = 2b{\rm{ }}\;(\!od 2{p^2})$ ，从而 $b \equiv 2a{\rm{ }}\;(\!od {p^2})$ 。当 $p \equiv \pm 1{\rm{ }}\;(\!od 8)$ ，即2是模 $p$ 的平方剩余^[2]，则 $b \in {D_{i + j}}$ ，从而 $\omega = 2b \in {E_{i + j}}$ ，所以 $v{E_j} = 2{E_{i + j}} = {E_{i + j}}$ ; 当 ${\rm{ }}p \equiv \pm 3{\rm{ }}\;(\!od 8)$ 时，同理可证。

(3)～(6)显然。 证毕

在 ${Z_4}[x]$ 中，令 ${D_i}(x) = \displaystyle\sum\nolimits_{u \in {D_i}} {{x^u}}$ , ${E_i}(x) =$ $\displaystyle\sum\nolimits_{u \in {E_i}} {{x^u}}$ , ${P_0}(x) = \displaystyle\sum\nolimits_{u \in {P_0}} {{x^u}}$ , ${P_1}(x) = \displaystyle\sum\nolimits_{u \in {P_1}} {{x^u}}$ 。则

注意到在 ${\rm{GR}}({4^r},4)$ 上有

为计算 $E({\gamma ^v})$ ，需要如下几个引理。

引理4　令 $\gamma \!\in\! {\rm{G}}{{\rm{R}}^{\rm{*}}}({4^r},4)$ 的阶为 $2{p^2}$ ，则 ${P_0}(\gamma ) \!=\! 1$ 。

证明　因为 $0 = {\gamma ^{2{p^2}}} - 1 = ({\gamma ^p} - 1) \Big({P_0}(\gamma ) +$ ${P_1}(\gamma ) + 1 + \left.{\gamma ^{{p^2}}}\big\right) = \left({\gamma ^{2p}} - 1\right)({P_1}(\gamma ) + 1)$ ，则由 $\gamma$ 的定义得 ${P_1}(\gamma ) = - 1$ , ${P_0}(\gamma ) = 1$ 。 证毕

接下来计算 ${D_0}(\gamma )$ 。记 $[i,j] = \left| {(1 + {D_i}) \cap {E_j}} \right|$ , $[i,2] = \left| {(1 + {D_i}) \cap {P_1}} \right|$ , $i,j \in \{ 0,1\}$ 。

引理 5　符号含义同上，则

证明　记 ${H_i} = \big\{ {g^{2n + i}}{\rm{ }}\;\left(\!od {p^2}\right):\;0 \le n < p$ $\cdot (p - 1)/2\big\}$ ，且 $\,R = \{ 0,p, ·\!·\!· ,(p - 1)p\}$ 。则

当 $p \equiv \pm 1{\rm{ }}\;(\!od 8)$ 时， $l = 0$ ；否则 $l = 1$ 。因此， $[i,j] \!=\! \left| {(1 \!+\! {H_i}) \cap {H_{j + l}}} \right|$ , $[0,2] \!\!=\!\! \left| {(1 + {H_0}) \cap (R\backslash \{ 0\} )} \right|$ 。由 $\left| {(1 + {H_i}) \cap {H_j}} \right|$ 的取值^[15]。 证毕

引理 6　若 $p \equiv \pm 1{\rm{ }}\;(\!od 8)$ ，则 ${p^2} + 2 \in {D_0}$ ；否则 ${p^2} + 2 \in {D_1}$ 。

证明　只证 $p \equiv \pm 1{\rm{ }}\;(\!od 8)$ 时的情形。设 ${p^2} \!+\! 2 \in {D_1}$ ，则存在整数 $q$ 使得 ${p^2} \!+\! 2 \equiv {g^{2n + 1}}{\rm{ + }}2{p^2}q$ ，即2是模 $p$ 的平方非剩余，矛盾，所以 ${p^2} + 2 \in {D_0}$ 。 证毕

引理 7　令 ${\omega _p} = {D_0}(\gamma )$ ，则

证明　只证 $p \equiv 1{\rm{ }}\;(od 8)$ 时的情形，其余情形同理可证。由于

且 ${g^{2n}}{\rm{ + 1 }}\;(\!od 2{p^2}) \in {E_0} \cup {E_1} \cup {P_1} \cup \{ 0\}$ 。令

下面分3种情况讨论：

(1) 令

${N_i} = \Biggr\{ n,\ 0 \le n \displaystyle\frac{{p(p - 1)}}{2},\ {g^{2n}}{\rm{ + 1 }}(od 2{p^2}) \in {E_i}\Biggr\}$

则 $\left| {{N_i}} \right| = [0,i]$ 。当 $n \in {N_i}$ ，由引理3，引理6有

(2) 令

${N_2} = \Biggr\{ n,\ 0 \le n < \displaystyle\frac{{p(p - 1)}}{2},\ {g^{2n}}{\rm{ + 1 }} (od 2{p^2}) \in {E_i}\Biggr\}$

则 $\;\left| {{N_i}} \right| = [0,i]$ 。当 $\;n \in {N_2}$ ，有

(3) 若 ${g^{2n}}{\rm{ + 1}} \equiv {\rm{0 }}\;\left(\!od 2{p^2}\right)$ ，则 $p \equiv 1{\rm{ }}\;(\!od 4)$ 且 $n = p(p - 1)/4$ ，因而 ${\lambda _n} = p(p - 1)/2$ 。即：由式(3)得 ${({\omega _p})^2} = \left| {{N_0}} \right|( - {\omega _P}) + \left| {{N_1}} \right|{\omega _P} -\left| {{N_2}} \right|+p(p -$ $1)/2$ 。又从引理5得 ${({\omega _p})^2} = {\omega _p}$ ，即 ${\omega _p} \in$ $\{ 0,1\}$ 。 证毕

引理 8　(1) 若 $p \equiv \pm 3{\rm{ }}\;(\!od 8)$ ，则

否则

(2) 当 $v = 0$ 时， $E({\gamma ^v}) = 3{p^2} + p + 2$ ；当 $v =$ ${p^2}$ 时， $E({\gamma ^v}) = 2p$ 。

证明　仅证 (1)中 $p \equiv \pm 3{\rm{ }}\;(\!od 8)$ 的情形，其余证明类似。 对任意的 $v \in {E_i} \cup {P_1}$ ，记 $v = 2\overline v$ ，其中 $\overline v \in {D_i} \cup {P_0}$ ，由引理3(5)和(6)得， ${p^2} +2\overline v$ $\in {D_{j + 1}} \cup {P_0}$ 且有 ${\gamma ^v} = {\gamma ^{2\overline v }} = - {\gamma ^{{p^2} + 2\overline v }}$ ，又由引理3(1)可得

进一步地，由引理3可得，当 $v \in {Z_{2{p^2}}}\backslash \{ 0,{p^2}\}$ 时， ${P_0}({\gamma ^v}) = {( - 1)^{v + 1}}$ , ${P_1}({\gamma ^v}) = - 1$ ；且有

则根据式(2)结论得证。

定义

引理 9　 $M(x)$ , $N(x)$ , ${\varGamma _j}(x)$ , ${\varLambda _j}(x) \in {Z_4}[x]$ 。

证明　显然 $M(x)$ , $N(x) \in {Z_4}[x]$ 。仅考虑 ${\varGamma _0}(x)$ ，对 ${\varGamma _1}(x)$ , ${\varLambda _j}(x)$ 同理可得。不难得到 ${\varGamma _0}(x)$ 的系数满足

设 ${\gamma ^b}$ 为和式中的一项， $b \equiv \displaystyle\sum\nolimits_{k = 1}^m {{d_k}} \;\left(\!od 2{p^2}\right)$ , $b \equiv \!\!\!\!\!\!/\;{\rm{0 }}\;(\!od {p^2})$ 。由引理3易得

　　　　 $x - {\gamma ^{{g^{2n}}{d_k}}}|\displaystyle\prod\limits_{v \in {D_0}}$ ${(x - {\lambda ^v})}$

所以 ${\gamma ^{{g^{2n}}{d_1}}} ·\!·\!· {\gamma ^{{g^{2n}}{d_m}}} = {\gamma ^{{g^{2n}}b}}$ 为和式的一项，即 ${\gamma ^b} + {\gamma ^{{g^2}b}} + ·\!·\!· + {\gamma ^{{g^{p(p - 1) - 2}}b}} = {D_0}({\gamma ^b})$ ，则存在 ${b_1},{b_2} ·\!··$ ${b_n}$ 使得 ${a_m} = {( - 1)^m}\displaystyle\sum\nolimits_{k = 0}^n {{D_0}\left({\gamma ^{{b_k}}}\right)} + l$ ，其中 $l =$ $\left| \left\{ a\left|a \equiv \displaystyle\sum\nolimits_{k = 1}^m {{d_k}} \equiv 0{\rm{ }}\;\left(\!od {p^2}\right){{且}}{d_1} < ·\!·\!· < \right.\right.\right.{d_m},{\rm{ }}{d_1}, ·\!·\!· ,$ ${d_m} \in {D_0} \Big\} \Big|$ 。又与引理8的证明类似可得 ${D_0}$ $\left({\gamma ^{{b_k}}}\right) = {\omega _p} \in {Z_4}$ 。 证毕

由于 ${\gamma ^v}$ 为 ${x^{{p^2}}} + 1$ 的根， $v \in \{ {p^2}\} \cup {D_0} \cup {D_1}$ $\cup{P_0}$ ，则

同样地，有

引理 10　存在 ${V_k}(x) \in {Z_4}[x]$ , $k = 1,2, ·\!·\!· ,5$ ，使得

证明　仅对 $p \equiv 3{\rm{ }}\;(\!od 8)$ 的情形进行证明，其余证明类似。由引理3得 ${D_1}(x) + 3{E_0}(x) =$ $- \left({x^{{p^2}}} - 1\right){D_1}(x)$ 。由引理8可知，当 $v \in {D_0}$ 时，有 ${D_1}({\gamma ^v}) = - {\omega _p}$ ，则存在 ${V_1}(x)$ 使得 ${D_1}(x) = - {\omega _p}$ $+{\varGamma _0}(x){V_1}(x)$ 。

注意到

且 ${P_1}({\gamma ^v}) = {P_1}(\gamma ) =- 1$ , $v \in {D_1}$ ，则结论易证。

因为 $2{x^{{p^2}}} + 2{E_1}(x) \!=\! 2({x^{{p^2}}} - 1) + 2 + 2{D_1}({x^2})$ 。由引理8 (1)，当 $v \in {P_i}$ 时， $2 + 2{D_1}({\gamma ^v}) = 0$ ，则由引理2, $2 + 2{D_1}(x) = M(x)N(x)G(x)$ ，其中 $G(x)$ $\in {Z_4}[x]$ 。即 $2 + 2{D_1}({x^2}) = M({x^2})N({x^2})G({x^2})$ 。由引理3 (5)得 $N(x) = \displaystyle\prod\nolimits_{v \in {P_0}} {\left(x - {\gamma ^{v + {p^2}}}\right)}$ ，则 $N ({x^2})$ = $\displaystyle\prod\nolimits_{v \in {P_1}} {\left({x^2} - {\gamma ^u}\right)} \!=\! \displaystyle\prod\nolimits_{v \in {P_0}} {(x - {\gamma ^u})} \left(x - {\gamma ^{{p^2} + u}}\right)$ $=M(x) N(x)$ 。

另一方面， $2 + 2{E_1}(1) = 0$ ，则存在 ${V_4}(x)$ 使得 $M\left({x^2}\right)G\left({x^2}\right) = (x - 1){V_4}(x)$ ，从而 $2{x^{{p^2}}} + 2{E_1}(x)$ $=2\left({x^{{p^2}}} - 1\right) + (x - 1)M(x)N(x){V_4}(x)$ 。

综上，即可得 $p \equiv 3{\rm{ }}\;(\!od 8)$ 时的结论。 证毕

引理 11　存在 ${W_k}(x) \in {Z_4}[x]$ , $k = 1,2, ·\!·\!· ,4$ ，使得

证明　仅证明 $p \equiv 3{\rm{ }}\;(\!od 8)$ 的情形，其余证明同理。由引理10和式(5)可得 $E(x) = (x - 1)$ $·N(x)H(x)$ ，其中， $H(x) \!=\! {\varLambda _0}(x){\varLambda _1}(x)({\omega _p} \!+\!1 \!- \!{\varGamma _0}(x)$ $·{V_p}(x) + {\varGamma _1}(x){V_p}(x)) + M(x){V_p}(x)$ 。

又由引理8易得若 $v \in {D_0} \!\cup\! {E_0} \!\cup\! {E_1}$ ，则 $H({\gamma ^v}) \!\ne\! 0$ ；若 $v \in {D_1} \cup {P_0}$ ，则 $H({\gamma ^v}) = 0$ ，则由引理1可得，存在 ${W_1}(x) \in {Z_4}[x]$ 且 ${W_1}({\gamma ^v}) \ne 0$ , $v \in {D_0} \cup {E_0} \cup {E_1}$ 使得 $H(x) = M(x){\varGamma _1}(x){W_1}(x)$ 。 证毕

2.3   定理1的证明

证明　若 $p \equiv 3{\rm{ }}\;(\!od 8)$ 。由引理11和引理8 (2)可得 ${W_1}({\gamma ^v}) \ne 0$ , $v \in {D_0} \cup {E_0} \cup {E_1} \cup \{ {p^2}\}$ ，从而

所以 ${\rm{LC}}({e_u}) \le 3p(p - 1)/2 + 1$ 。又因为 $\gcd ((x - 1)$ $·M(x)N(x){\varGamma _1}(x),{\rm{ }}(x + 1){\varGamma _0}(x){\varLambda _0}(x){\varLambda _1}(x)) = 1$ ，所以由式(1)，式(4)，式(5)和引理11得 ${W_1}(x)C(x) \equiv$ $0{\rm{ }}\;(\!od {\rm{ }}(x + 1){\varGamma _0}(x){\varLambda _0}(x){\varLambda _1}(x))$ ，则有 ${W_1}({\gamma ^v})C({\gamma ^v})$ $= 0{\rm{ }}$ , $v \in \{ {D_0} \cup {E_0} \cup {E_1} \cup \{ {p^2}\} \}$ ，从而，若 ${W_1}({\gamma ^v})$ $\in {\rm{G}}{{\rm{R}}^{\rm{*}}}({4^r},4)$ ，则 $C({\gamma ^v}) \!=\! 0{\rm{ }}$ ；若 $2{W_1}({\gamma ^v}) \in {\rm{GR}}({4^r},$ $4)\backslash \{ 0\}$ ，则 $2C({\gamma ^v}) = 0{\rm{ }}$ 。显然有 $(x + 1){\varGamma _0}(x){\varLambda _0}(x)$ $\cdot {\varLambda _1}(x)|2C(x)$ ，即 ${\rm{LC}}({e_u}) \ge \displaystyle\frac{{3p(p - 1)}}{2} + 1$ 。因此， ${\rm{LC}}({e_u}) = \displaystyle\frac{{3p(p - 1)}}{2} + 1$ 。

其它情形同理可证。 证毕

3.   结束语

本文在 ${Z_4}$ 上定义了一类周期为 $2{p^2}$ 的新四元广义分圆序列 $({e_u})$ ，并研究了该序列的关联多项式和线性复杂度。结果表明，当 $p \equiv 3{\rm{ }}\;(\!od 4)$ 和 $p \equiv$ $- 3{\rm{ }}\;(\!od 8)$ 时，这类序列拥有好的线性复杂度，能够抵抗B-M算法的攻击，在保密通讯中可以有广泛的应用。此外，若定义序列 $({s_u})$ 为

与前面的证明类似可得，该序列的线性复杂度达到最大值，即当 $p \equiv 1{\rm{ }}\;(\!od 4)$ 时， ${\rm{LC}}({s_u}) = 2{p^2}$ ；否则 ${\rm{LC}}({s_u}) = 2{p^2} - 1$ 。