伪随机序列在码分多址、流密码等领域有广泛应用 ^[1-3]. 二元序列和四元序列是实际应用中的首选序列. 相关性和复杂度是伪随机序列的两个重要指标. 在密码学的相关应用中, 要求使用的序列具有较高的线性复杂度. 通过符号替换, 可建立$ \mathbb{Z}_{4} $上的四元序列和$ \mathbb{F}_{4} $上的四元序列的一一对应关系. 因此, 考察四元序列在$ \mathbb{Z}_{4} $和$ \mathbb{F}_{4} $上的线性复杂度是探究四元序列优劣的必要步骤. 根据Berlekamp-Massey算法 ^[4-5]以及Reeds-Sloane算法 ^[6]可知, 使用的四元序列在$ \mathbb{F}_{4} $和$ \mathbb{Z}_{4} $上的线性复杂度至少要达到其周期的一半.

基于经典分圆类和广义分圆类构造的伪随机序列具有较高的复杂度, 近年来受到学者们的关注 ^[7-12]. 逆Gray映射是构造四元序列的一种常用方法 ^[13]. 文^[9] 利用广义分圆二元序列和逆Gray映射构造了一类具有良好自相关性质的四元序列. 文^[10] 确定了文^[9] 中构造的四元序列在$ \mathbb{F}_{4} $和$ \mathbb{Z}_{4} $上的线性复杂度, 并对已有构造进行了改进. 文^[12] 由逆Gray映射构造了一类新的周期为$ pq $的四元序列, 使用与文^[10] 中相似的方法确定了新序列在$ \mathbb{F}_{4} $上的线性复杂度, 并确定了该序列的4-adic复杂度. 文^[11] 分别基于Whiteman广义分圆序列和Ding-Helleseth广义分圆序列给出了两类周期为$ pq $的四元序列, 并计算了序列在$ \mathbb{Z}_{4} $上的线性复杂度.

较之模4剩余类环$ \mathbb{Z}_{4} $, 四阶有限域$ \mathbb{F}_{4} $有更好的代数结构, 注意到$ \mathbb{Z}_{4} $和$ \mathbb{F}_{4} $上序列的性质定义和分析方法是不相同的. 关于四元序列在$ \mathbb{F}_{4} $上的复杂度, 文^[14] 考虑了具有优自相关性质的偶数周期四元序列在$ \mathbb{F}_{4} $上的线性复杂度. 文^[15] 考虑了一类基于交织方法构造的四元序列在$ \mathbb{F}_{4} $上的线性复杂度, 该序列的周期也是$ pq $, 其中$ p $和$ q $是不同的奇素数. 本文将分析文^[11] 中两类序列在$ \mathbb{F}_{4} $上的线性复杂度和极小多项式. 本文的其余部分组织如下. 第2节介绍相关的基本概念以及一些必要的记号. 第3节确定文^[11] 中第一类四元序列在$ \mathbb{F}_{4} $上的线性复杂度和极小多项式. 第4节确定文^[11] 中第二类四元序列在$ \mathbb{F}_{4} $上的线性复杂度和极小多项式. 第5节对文章进行总结.

设$ p $和$ q $是两个不同的奇素数, 且$ N=pq $. 定义$ P=\left\lbrace p, 2p, \dots, \left( q-1\right) p\right\rbrace $, $ Q=\left\lbrace q, 2q, \dots, \left( p-1\right) q\right\rbrace $, $ Z_{N}^{*} $表示剩余类环$ Z_{N} $中所有可逆元素组成的集合. 易知$ Z_{N}=\left\lbrace 0\right\rbrace \cup P\cup Q \cup Z_{N}^{*} $. 由中国剩余定理, 有$ Z_{N}\cong Z_{p}\times Z_{q} $, 对应的同构映射为$ f\left( t\right) =\left( t_{1}, t_{2}\right) $, 其中$ t\equiv t_{1}\, ( \rm{mod}\:p) $, $ t\equiv t_{2}\, ( \rm{mod}\:q) $. 文中$ \left( \frac{\cdot}{\cdot}\right) $表示勒让德符号.

逆Gray映射$ \phi=\left[ a, b\right] $定义为

$ \begin{equation} \phi\left[ 0, 0\right] =0, \phi\left[ 0, 1\right] =1, \phi\left[ 1, 1\right] =2, \phi\left[ 1, 0\right] =3.\nonumber \end{equation} $

定义二元序列$ s_{i} $, $ i=1, 2, 3 $如下：

$ \begin{equation} s_{1}\left( t\right) =\begin{cases} 1, & \rm{若 }t\in P;\\ 0, \qquad & \rm{若 } t\in \left\lbrace 0\right\rbrace \cup Q;\\ \frac{1-\left( \frac{t}{p}\right) \left( \frac{t}{q}\right) }{2}, \qquad & \rm{若} \; t\in Z_{N}^{*}. \end{cases}\notag s_{2}\left( t\right) =\begin{cases} 1, & \rm{若 }t\in P;\\ 0, \qquad & \rm{若 } t\in \left\lbrace 0\right\rbrace \cup Q;\\ \frac{1-\left( \frac{t}{q}\right) }{2}, \qquad & \rm{若} \; t\in Z_{N}^{*}. \end{cases}\notag \end{equation} $

$ \begin{equation} s_{3}\left( t\right) =\begin{cases} 1, & \rm{若 }t\in P;\\ 0, \qquad & \rm{若 } t\in \left\lbrace 0\right\rbrace \cup Q;\\ \frac{1-\left( \frac{t}{p}\right) }{2}, \qquad & \rm{若} \; t\in Z_{N}^{*}. \end{cases}\notag \end{equation} $

利用逆Gray映射, 文^[11] 定义了第一类四元序列$ s'\left( t\right) $和第二类四元序列$ s''\left( t\right) $如下：

$ \begin{equation} s'\left( t\right) =\phi\left[ s_{1}\left( t\right) , s_{2}\left( t\right) \right]. \end{equation}$

(1)

$ \begin{equation} s''\left( t\right) =\phi\left[ s_{2}\left( t\right) , s_{3}\left( t\right) \right]. \end{equation}$

(2)

设$ A_{i} $, $ B_{i} $, $ i=0, 1 $分别表示模$ p $和模$ q $的平方剩余及非平方剩余, $ A_{2}=B_{2}=\left\lbrace 0\right\rbrace $. 设$ F_{k, l}=f^{-1} \left( A_{k}\times B_{l}\right), k, l=0, 1, 2. $则$ Z_{N}=\bigcup_{k, l=0}^{2}F_{k, l} $. 那么, 序列$ s'\left( t\right) $和$ s''\left( t\right) $可以分别地表示为：

$ \begin{equation} s'\left( t\right)=\begin{cases} 0, & \rm{若 }t\, ( \rm{mod}\:N)\in F_{0, 0}\cup F_{0, 2}\cup F_{1, 2}\cup\left\lbrace 0\right\rbrace ;\\ 1, \qquad & \rm{若 } t\, ( \rm{mod}\:N) \in F_{1, 1};\\ 2, \qquad & \rm{若 } t\, ( \rm{mod}\:N) \in F_{0, 1}\cup F_{2, 0}\cup F_{2, 1};\\ 3, \qquad & \rm{若 } t\, ( \rm{mod}\:N) \in F_{1, 0}. \end{cases} \end{equation}$

(3)

$ \begin{equation} s''\left( t\right)=\begin{cases} 0, & \rm{若 }t\, ( \rm{mod}\:N)\in F_{0, 0}\cup F_{0, 2}\cup F_{1, 2}\cup\left\lbrace 0\right\rbrace ;\\ 1, \qquad & \rm{若 } t\, ( \rm{mod}\:N)\in F_{1, 0};\\ 2, \qquad & \rm{若 } t\, ( \rm{mod}\:N) \in F_{1, 1}\cup F_{2, 0}\cup F_{2, 1};\\ 3, \qquad & \rm{若 } t\, ( \rm{mod}\:N) \in F_{0, 1}. \end{cases} \end{equation}$

(4)

定义四阶有限域$ \mathbb{F}_{4}=\left\lbrace 0, 1, \mu, \mu^{2}\right\rbrace $, 其中$ \mu $满足$ \mu^{2}=\mu+1 $, 即$ \mathbb{F}_{4} $是$ \mathbb{F}_{2} $上以1, $ \mu $为基的向量空间. 若$ s=\left( s\left( 0\right) , s\left( 1\right), \dots, \!s\left( N-1\right) \right) \! $是$ \mathbb{F}_{4} $上的周期为$ N $的四元序列, 则序列$ s $的生成多项式为$ M_{s}\left( x\right)\! \!=\!\sum_{t=0}^{N-1}s\left( t\right) x^{t} $, 其极小多项式$ m_{s}\left( x\right) $的计算公式为

$ \begin{equation} m_{s}\left( x\right) =\frac{x^{N}-1}{ \rm{gcd}\left( x^{N}-1, M_{s}\left( x\right) \right) }. \end{equation}$

(5)

序列$ s $的线性复杂度$ LC\left( s\right) $为

$ \begin{equation} LC\left( s\right) =N- \rm{deg}\left( \rm{gcd}\left( x^{N}-1, M_{s}\left( x\right) \right) \right). \end{equation}$

(6)

设$ t $是4模$ N $的阶, 即$ t $是满足$ 4^{t}\equiv1( \rm{mod}\:N) $的最小正整数. 假设$ \xi $是$ \mathbb{F}_{4^{t}} $的本原元, 则$ \xi^{\frac{4^{t}-1}{N}} $的阶为$ N $. 记$ \alpha=\xi^{\frac{4^{t}-1}{N}} $. 因此$ \mathbb{F}_{4^{t}} $是$ x^{N}-1 $的分裂域. 由(6)可得

$ \begin{align*} LC\left( s\right) & =N- \rm{deg}\left( \rm{gcd}\left( x^{N}-1, M_{s}\left( x\right) \right) \right) \nonumber\\ &=N-\vert \left\lbrace v|M_{s}\left( \alpha^{v}\right) =0, v=0, 1, \dots, N-1\right\rbrace \vert. \end{align*} $

(7)

设$ \beta=\alpha^{aq} $, $ \gamma=\alpha^{bp} $, 其中$ a $, $ b $是满足$ aq+bp=1 $的整数. 即$ \beta $和$ \gamma $分别为$ \mathbb{F}_{4^{t}} $上的$ p $次和$ q $次本原单位根. 设$ R_{2}\left( x\right) =\sum_{i\in A_{0}}x^{i} $且$ T_{2}\left( x\right) =\sum_{i\in B_{0}}x^{i} $. 易知$ R_{2}\left( 1\right) =\left( p-1\right) /2 $, $ T_{2}\left( 1\right) =\left( q-1\right) /2 $.

引理1  ^[16] $ \rm (1) $若$ p\equiv \pm 1\, ( \rm{mod}\:8) $或$ q\equiv \pm 1\, ( \rm{mod}\:8) $, 则

$ \begin{equation} R_{2}\left( \beta^{v}\right) =\begin{cases} 1, & \rm{若 }v \, ( \rm{mod}\:p) \in A_{0}, \\ 0, \qquad & \rm{若 }v\, ( \rm{mod}\:p) \in A_{1}. \end{cases}\notag \rm{ 且 }\quad T_{2}\left( \gamma^{v}\right) =\begin{cases} 1, & \rm{若 }v\, ( \rm{mod}\:q)\in B_{0}, \\ 0, \qquad & \rm{若 }v\, ( \rm{mod}\:q) \in B_{1}. \end{cases}\notag \end{equation} $

$ \rm (2) $若$ p\equiv \pm 3\, ( \rm{mod}\:8) $或$ q\equiv \pm 3\, ( \rm{mod}\:8) $, 则

$ \begin{equation} \!R_{2}\left( \beta^{v}\right)\! =\begin{cases} \!\mu, \!&\! \rm{若 }v\, ( \rm{mod}\:p)\in A_{0}, \!\\ \!\mu+1, \!\qquad &\! \rm{若 }v\, ( \rm{mod}\:p)\in A_{1}.\! \end{cases}\notag \rm{ 且 }\quad \!T_{2}\left( \gamma^{v}\right) \!=\begin{cases} \!\mu, \!&\! \rm{若 }v\, ( \rm{mod}\:q)\in B_{0}, \!\\ \!\mu+1, \!\qquad &\! \rm{若 }v\, ( \rm{mod}\:q)\in B_{1}.\! \end{cases}\notag \end{equation} $

为计算序列在$ \mathbb{F}_{4} $上的线性复杂度, 分别把(3), (4)式定义的$ \mathbb{Z}_{4} $上的序列修改为$ \mathbb{F}_{4} $上的序列, 即令$ 0=0 $, $ 1=1 $, $ 2=\mu+1 $, $ 3=\mu $. 在不引起混淆的情况下, 把修改后的序列记为$ U' $和$ U'' $.

易知, $ \mathbb{F}_{4} $上的序列$ U' $的生成多项式为

$ \begin{equation} M_{U'}\left( \alpha^{v}\right) \!= \! \sum\limits_{t\, ( \rm{mod}\:N) \in F_{1, 1}}\alpha^{vt}+\left( \mu+1\right) \sum\limits_{t\, ( \rm{mod}\:N) \in F_{0, 1}\cup F_{2, 0}\cup F_{2, 1}}\alpha^{vt}+\mu\sum\limits_{t\, ( \rm{mod}\:N) \in F_{1, 0}}\alpha^{vt} \nonumber. \end{equation} $

设$ \theta $和$ \eta $分别表示模$ p $和模$ q $的本原根. 由$ F_{1, 1}=f^{-1}\left( A_{1}\times B_{1}\right)=\left\lbrace aqt_{1}+bpt_{2}|t_{1}\in \right.\\\left.A_{1}, t_{2}\in B_{1}\right\rbrace $, 可得

$ \begin{equation} \sum\limits_{t\, ( \rm{mod}\:N) \in F_{1, 1}}\alpha^{vt}=\sum\limits_{t_{1}\in A_{1}}\sum\limits_{t_{2}\in B_{1}}\alpha^{vaqt_{1}+vbpt_{2}}=\sum\limits_{i\in A_{0}}\left( \alpha^{aq}\right) ^{v\theta i}\sum\limits_{j\in B_{0}}\left( \alpha^{bp}\right) ^{v\eta j}=R_{2}\left( \beta^{v\theta}\right) T_{2}\left( \gamma^{v\eta}\right) \nonumber. \end{equation} $

对其余情形$ F_{i, j}, i, j\in\left\lbrace 0, 1, 2\right\rbrace $类似可证. 综上, 有

$ \begin{align*} M_{U'}\left( \alpha^{v}\right) &\!= \!R_{2}\left( \beta^{v\theta}\right) T_{2}\left( \gamma^{v\eta}\right)\! +\!\left( \mu+1\right)\!\! \left(R_{2}\left( \beta^{v}\right) T_{2}\left( \gamma^{v\eta}\right)+T_{2}\left( \gamma^{v}\right)\!+\!T_{2}\left( \gamma^{v\eta}\right)\right)\! \nonumber\\&+\!\mu R_{2}\left( \beta^{v\theta}\right) T_{2}\left( \gamma^{v}\right).\! \end{align*} $

(8)

将$ R_{2}\left( 1\right) =\left( p-1\right) /2 $, $ T_{2}\left( 1\right) =\left( q-1\right) /2 $带入(8)中有

$ M_{U'}\left( 1\right) =0. $

(9)

引理2   设$ U'\left( t\right) $是(3)定义的序列在$ \mathbb{F}_{4} $上对应的四元序列, $ M_{U'}\left( x\right) $是其生成多项式. 则

$ \rm (1) $ $ M_{U'}\left( \alpha^{v}\right) =\begin{cases} \mu+1, & \rm{若\; } v\in P \rm{ 且\; } p\, ( \rm{mod}\:4) \equiv1, \\ 1, \qquad & \rm{若\; } v\in P \rm{ 且\; } p\, ( \rm{mod}\:4) \equiv-1. \end{cases} \notag $

$ \rm (2) $$ M_{U'}\left( \alpha^{v}\right) =\begin{cases} 0, & \rm{若\; } v\in Q \rm{ 且\; } q\, ( \rm{mod}\:4) \equiv1, \\ \mu+1, \qquad & \rm{若\; } v\in Q \rm{ 且\; } q\, ( \rm{mod}\:4) \equiv-1. \end{cases}\notag $

证   设$ v\in P $, 则$ R_{2}\left( \beta^{v}\right) =\left( p-1\right) /2 $, $ R_{2}\left( \beta^{v\theta}\right) =\left( p-1\right) /2 $. 若$ p\, ( \rm{mod}\:4) \equiv1 $, 则$ R_{2}\left( \beta^{v}\right)=0 $且$ R_{2}\left( \beta^{v\theta}\right) =0 $. 由(8)可得$ M_{U'}\left( \alpha^{v}\right)=\left( \mu+1\right)\!\! \left( T_{2}\left( \gamma^{v}\right) +T_{2}\left( \gamma^{v\eta}\right) \right) $. 由引理1, $ T_{2}\left( \gamma^{v\eta}\right) =\sum_{i\in B_{0}}\gamma^{v\eta i}=\sum_{i\in B_{1}}\gamma^{vi}=T_{2}\left( \gamma^{v}\right)+1 $, 则$ M_{U'}\left( \alpha^{v}\right)=\mu+1 $. 若$ p\, ( \rm{mod}\:4)\equiv-1 $, 则$ R_{2}\left( \beta^{v}\right)=1 $且$ R_{2}\left( \beta^{v\theta}\right) =1 $. 由(8)可得$ M_{U'}\left( \alpha^{v}\right)=T_{2}\left( \gamma^{v\eta}\right)+\left( \mu+1\right)\!\! \left( T_{2}\left( \gamma^{v\eta}\right)+T_{2}\left( \gamma^{v}\right)+T_{2}\left( \gamma^{v\eta}\right) \right)+\mu T_{2}\left( \gamma^{v}\right)=T_{2}\left( \gamma^{v\eta}\right)+T_{2}\left( \gamma^{v}\right) $. 由$ T_{2}\left( \gamma^{v\eta}\right)=T_{2}\left( \gamma^{v}\right)+1 $可得, $ M_{U'}\left( \alpha^{v}\right)=1 $. $ v\in Q $的情形类似可证.

引理3   记号同上. 若$ v\in Z_{N}^{*} $, 则

$ \begin{align*} \!M_{U'}\left( \alpha^{v}\right)\!&\!=\!\begin{cases} \!R_{2}\left( \beta^{\theta}\right) T_{2}\left( \gamma^{\eta}\right)\!+\!\left( \mu+1\right)\! \!\left(R_{2}\left( \beta\right) T_{2}\left( \gamma^{\eta}\right)+ T_{2}\left( \gamma\right)+T_{2}\left( \gamma^{\eta}\right)\right)\!+\!\mu R_{2}\left( \beta^{\theta}\right) T_{2}\left( \gamma\right), \! \\\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\:\:\:\:\:\, \rm{若 }\!v\in F_{0, 0};\! \\ \!R_{2}\left( \beta\right) T_{2}\left( \gamma\right)\!+\!\left( \mu+1\right)\! \!\left(R_{2}\left( \beta^{\theta}\right) T_{2}\left( \gamma\right)+ T_{2}\left( \gamma\right)+T_{2}\left( \gamma^{\eta}\right)\right)\!+\!\mu R_{2}\left( \beta\right) T_{2}\left( \gamma^{\eta}\right), \! \\\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\:\:\:\:\:\, \rm{若 }\!v\in F_{1, 1};\! \\ \!R_{2}\left( \beta\right) T_{2}\left( \gamma^{\eta}\right)\!+\!\left( \mu+1\right)\! \!\left(R_{2}\left( \beta^{\theta}\right) T_{2}\left( \gamma^{\eta}\right)+ T_{2}\left( \gamma\right)+T_{2}\left( \gamma^{\eta}\right)\right)\!+\mu R_{2}\left( \beta\right) T_{2}\left( \gamma\right), \! \\\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\:\:\:\:\:\, \rm{若 }v\in F_{1, 0}; \\ \!R_{2}\left( \beta^{\theta}\right) T_{2}\left( \gamma\right)+\!\left( \mu+1\right)\! \!\left(R_{2}\left( \beta\right) T_{2}\left( \gamma\right)+ T_{2}\left( \gamma\right)+T_{2}\left( \gamma^{\eta}\right)\right)\!+\mu R_{2}\left( \beta^{\theta}\right) T_{2}\left( \gamma^{\eta}\right), \! \\\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\:\:\:\:\:\, \rm{若 }v\in F_{0, 1}. \\ \end{cases} \notag \end{align*} $

证   若$ v\in F_{0, 0} $, 则$ v\, ( \rm{mod}\:p)\in A_{0} $且$ v\, ( \rm{mod}\:q)\in B_{0} $, 则$ R_{2}\left( \beta^{v\theta}\right) =\sum_{i\in A_{0}}\beta^{v\theta i}=\sum_{i\in A_{0}}\beta^{\theta i}=R_{2}\left(\beta^{\theta}\right) $, $ T_{2}\left( \gamma^{v\eta}\right) =\sum_{i\in B_{0}}\gamma^{v\eta i}=\sum_{i\in B_{0}}\gamma^{\eta i}=T_{2}\left(\gamma^{\eta}\right) $, $ T_{2}\left( \gamma^{v}\right)= \sum_{i\in B_{0}}\gamma^{vi}= \sum_{i\in B_{0}}\gamma^{i}= T_{2}\left(\gamma\right) $且$ R_{2}\left( \beta^{v}\right)= \sum_{i\in A_{0}}\beta^{vi}=\sum_{i\in A_{0}}\beta^{i}=R_{2}\left(\beta\right) $. 则由(8), $ M_{U'}\left( \alpha^{v}\right)=R_{2}\left( \beta^{\theta}\right) T_{2}\left( \gamma^{\eta}\right)+\left( \mu+1\right)\! \!\left(R_{2}\left( \beta\right) T_{2}\left( \gamma^{\eta}\right)+ T_{2}\left( \gamma\right)+T_{2}\left( \gamma^{\eta}\right)\right)+\mu R_{2}\left( \beta^{\theta}\right) T_{2}\left( \gamma\right) $. 其余情形类似可证.

引理4   记号同上, 则

$ \rm (1) $若$ p\, ( \rm{mod}\:8) \equiv\pm1 $, 当$ q\, ( \rm{mod}\:8) \equiv\pm1 $或$ q\, ( \rm{mod}\:8) \equiv\pm3 $, 则

$ \begin{equation} M_{U'}\left( \alpha^{v}\right) =\begin{cases} \mu+1, & \rm{若 }v\in F_{0, 0}, \\ \mu, \qquad & \rm{若 }v\in F_{1, 1}, \\ 1, \qquad & \rm{若 }v\in F_{1, 0}, \\ 0, \qquad & \rm{若 }v\in F_{0, 1}. \end{cases} \notag \rm{ 或\; } M_{U'}\left( \alpha^{v}\right) =\begin{cases} 1, & \rm{若 }v\in F_{0, 0}, \\ 0, \qquad & \rm{若 }v\in F_{1, 1}, \\ \mu+1, \qquad & \rm{若 }v\in F_{1, 0}, \\ \mu, \qquad & \rm{若 }v\in F_{0, 1}. \end{cases} \notag \end{equation} $

$ \rm (2) $若$ p\, ( \rm{mod}\:8) \equiv\pm3 $, 当$ q\, ( \rm{mod}\:8) \equiv\pm1 $或$ q\, ( \rm{mod}\:8) \equiv\pm3 $, 则

$ \begin{equation} M_{U'}\left( \alpha^{v}\right) =\begin{cases} \mu, & \rm{若 }v\in F_{0, 0}, \\ \mu+1, \qquad & \rm{若 }v\in F_{1, 1}, \\ 0, \qquad & \rm{若 }v\in F_{1, 0}, \\ 1, \qquad & \rm{若 }v\in F_{0, 1}. \end{cases} \notag \rm{ 或\; } M_{U'}\left( \alpha^{v}\right) =\begin{cases} 0, & \rm{若 }v\in F_{0, 0}, \\ 1, \qquad & \rm{若 }v\in F_{1, 1}, \\ \mu, \qquad & \rm{若 }v\in F_{1, 0}, \\ \mu+1, \qquad & \rm{若 }v\in F_{0, 1}. \end{cases} \notag \end{equation} $

证   对不同的情形, 证明方法是类似的, 因此只证明$ p\, ( \rm{mod}\:8) \equiv\pm1 $且$ q\, ( \rm{mod}\:8) \equiv\pm1 $的情形. 当$ p\, ( \rm{mod}\:8) \equiv\pm1 $且$ q\, ( \rm{mod}\:8) \equiv\pm1 $时, 由引理1和引理3, 若$ v\in F_{0, 0} $, 则$ M_{U'}\left( \alpha^{v}\right) =0+\left( \mu+1\right)\! \!\left( 0+1+0\right) +\mu\times0=\mu+1 $; 若$ v\in F_{1, 1} $, 则$ M_{U'}\left( \alpha^{v}\right) =1+\left( \mu+1\right)\! \! \left( 0+0+1\right) +\mu\times0=\mu $; 若$ v\in F_{1, 0} $, 则$ M_{U'}\left( \alpha^{v}\right) =0+\left( \mu+1\right)\! \! \left( 0+1+0\right) +\mu\times1=1 $; 若$ v\in F_{0, 1} $, 则$ M_{U'}\left( \alpha^{v}\right) =0+\left( \mu+1\right)\! \! \left( 1+0+1\right) +\mu\times0=0 $.

定理1    记号同上. 记$ H_{1}\left( x\right) =\prod_{t\in F_{0, 0}} \left( x-\alpha^{t}\right) $, $ H_{2}\left( x\right)\! \!=\!\prod_{t\in F_{1, 1}} \left( x-\alpha^{t}\right) $, $ H_{3}\left( x\right) =\prod_{t\in F_{1, 0}} \left( x-\alpha^{t}\right) $, $ H_{4}\left( x\right) =\prod_{t\in F_{0, 1}} \left( x- \alpha^{t}\right) $且$ Q\left( x\right) =\prod_{t\in Q} \left( x-\alpha^{t}\right) $. 则$ U'\left( t\right) $的线性复杂度$ LC\left( U'\left( t\right) \right) $和极小多项式$ m_{U'}\left( x\right) $如下：

$ \rm (1) $若$ p\, ( \rm{mod}\:8) \equiv\pm1 $且$ q\, ( \rm{mod}\:8) \equiv1 $, 则

$ \begin{equation} LC\left( U'\left( t\right) \right) =\frac{3pq-3p+q-1}{4}, m_{U'}\left( x\right) =\frac{ x^{pq}-1}{\left( x-1\right) H_{4}\left( x\right) Q\left( x\right)};\notag \end{equation} $

$ \rm (2) $若$ p\, ( \rm{mod}\:8) \equiv\pm1 $且$ q\, ( \rm{mod}\:8) \equiv-1 $, 则

$ \begin{equation} LC\left( U'\left( t\right) \right) =\frac{3pq+p+q-5}{4}, m_{U'}\left( x\right) =\frac{x^{pq}-1}{\left( x-1\right) H_{4}\left( x\right)}; \notag \end{equation} $

$ \rm (3) $若$ p\, ( \rm{mod}\:8) \equiv\pm1 $且$ q\, ( \rm{mod}\:8) \equiv3 $, 则

$ \begin{equation} LC\left( U'\left( t\right) \right) =\frac{3pq+p+q-5}{4}, m_{U'}\left( x\right) =\frac{x^{pq}-1}{\left( x-1\right) H_{2}\left( x\right)};\notag \end{equation} $

$ \rm (4) $若$ p\, ( \rm{mod}\:8) \equiv\pm1 $且$ q\, ( \rm{mod}\:8) \equiv-3 $, 则

$ \begin{equation} LC\left( U'\left( t\right) \right) =\frac{3pq-3p+q-1}{4}, m_{U'}\left( x\right) =\frac{x^{pq}-1}{\left( x-1\right) H_{2}\left( x\right) Q\left( x\right)};\notag \end{equation} $

$ \rm (5) $若$ p\, ( \rm{mod}\:8) \equiv\pm3 $且$ q\, ( \rm{mod}\:8)\equiv1 $, 则

$ \begin{equation} LC\left( U'\left( t\right) \right) =\frac{3pq-3p+q-1}{4}, m_{U'}\left( x\right) =\frac{x^{pq}-1}{\left( x-1\right) H_{3}\left( x\right)Q\left( x\right)};\notag \end{equation} $

$ \rm (6) $若$ p\, ( \rm{mod}\:8) \equiv\pm3 $且$ q\, ( \rm{mod}\:8) \equiv-1 $, 则

$ \begin{equation} LC\left( U'\left( t\right) \right) =\frac{3pq+p+q-5}{4}, m_{U'}\left( x\right) =\frac{x^{pq}-1}{\left( x-1\right) H_{3}\left( x\right)};\notag \end{equation} $

$ \rm (7) $若$ p\, ( \rm{mod}\:8) \equiv\pm3 $且$ q\, ( \rm{mod}\:8) \equiv3 $, 则

$ \begin{equation} LC\left( U'\left( t\right) \right) =\frac{3pq+p+q-5}{4}, m_{U'}\left( x\right) =\frac{x^{pq}-1}{\left( x-1\right) H_{1}\left( x\right)};\notag \end{equation} $

$ \rm (8) $若$ p\, ( \rm{mod}\:8) \equiv\pm3 $且$ q\, ( \rm{mod}\:8) \equiv-3 $, 则

$ \begin{equation} LC\left( U'\left( t\right) \right) =\frac{3pq-3p+q-1}{4}, m_{U'}\left( x\right) =\frac{ x^{pq}-1}{\left( x-1\right) H_{1}\left( x\right)Q\left( x\right)}.\notag \end{equation} $

证   当$ p\, ( \rm{mod}\:8) \equiv\pm1 $且$ q\, ( \rm{mod}\:8) \equiv1 $时, 由引理4, 有$ |\left\lbrace v|v\in Z_{N}^{*}, M_{U'}\left( \alpha^{v}\right)=0\right\rbrace |=\frac{\left( p-1\right) \left( q-1\right) }{4} $, 又由引理2, 有$ |\left\lbrace v|v\in P, M_{U'}\left( \alpha^{v}\right) =0\right\rbrace |=0 $, $ |\left\lbrace v|v\in Q, M_{U'}\left( \alpha^{v}\right) =0\right\rbrace |=p-1 $. 结合式(9), 可得线性复杂度为$ LC\left( U'\left( t\right) \right) =pq-\frac{\left( p-1\right) \left( q-1\right) }{4}-\left( p-1\right) -1=\frac{3pq-3p+q-1}{4} $, 且极小多项式为$ m_{U'}\left( x\right) =\frac{x^{pq}-1}{\left( x-1\right) H_{4}\left( x\right) Q\left( x\right)} $. 其余情形类似可证.

利用Magma程序, 验证了取不同参数时$ U'\left( t\right) $的线性复杂度, 见表 1. 结果与定理1结论一致.

本节计算序列$ U'' $在$ \mathbb{F}_{4} $上的线性复杂度. 与第2节类似, 同样用$ U'' $表示该序列在$ \mathbb{F}_{4} $上的对应. 记号同上. 此时$ U'' $的生成多项式为

$ \begin{equation} M_{U''}\left( \alpha^{v}\right) \!= \! \sum\limits_{t\, ( \rm{mod}\:N) \in F_{1, 0}}\alpha^{vt}+\left( \mu+1\right) \sum\limits_{t\, ( \rm{mod}\:N) \in F_{1, 1}\cup F_{2, 0}\cup F_{2, 1}}\alpha^{vt}+\mu\sum\limits_{t\, ( \rm{mod}\:N)\in F_{0, 1}}\alpha^{vt} \nonumber\\. \end{equation} $

由$ F_{1, 0}=f^{-1}\left( A_{1}\times B_{0}\right)=\left\lbrace aqt_{1}+bpt_{2}|t_{1}\in A_{1}, t_{2}\in B_{0}\right\rbrace $, 可得

$ \begin{equation} \sum\limits_{t\, ( \rm{mod}\:N) \in F_{1, 0}}\alpha^{vt}=\sum\limits_{t_{1}\in A_{1}}\sum\limits_{t_{2}\in B_{0}}\alpha^{vaqt_{1}+vbpt_{2}}=\sum\limits_{i\in A_{0}}\left( \alpha^{aq}\right) ^{v\theta i}\sum\limits_{j\in B_{0}}\left( \alpha^{bp}\right) ^{vj}=R_{2}\left( \beta^{v\theta}\right) T_{2}\left( \gamma^{v}\right) \nonumber. \end{equation} $

对其余情形$ F_{i, j}, i, j\in\left\lbrace 0, 1, 2\right\rbrace $类似可证. 综上, 有

$ \begin{align*} M_{U''}\left( \alpha^{v}\right) \!=\!R_{2}\left( \beta^{v\theta}\right) T_{2}\left( \gamma^{v}\right)\!+\!\left( \mu+1\right)\!\! \left(R_{2}\left( \beta^{v\theta}\right) T_{2}\left( \gamma^{v\eta}\right)\!+\!T_{2}\left( \gamma^{v}\right)\!+\!T_{2}\left( \gamma^{v\eta}\right)\right)\!+\!\mu R_{2}\left( \beta^{v}\right) T_{2}\left( \gamma^{v\eta}\right).\! \end{align*} $

(10)

将$ R_{2}\left( 1\right) =\left( p-1\right) /2 $, $ T_{2}\left( 1\right) =\left( q-1\right) /2 $带入(10)中有

$ M_{U''}\left( 1\right) =0. $

(11)

引理5  设$ U''\left( t\right) $是(4)定义的序列在$ \mathbb{F}_{4} $上对应的四元序列, $ M_{U''}\left( x\right) $是其生成多项式. 则

$ \rm (1) $ $ M_{U''}\left( \alpha^{v}\right) =\begin{cases} \mu+1, & \rm{若\; }v\in P \rm{ 且\; } p\, ( \rm{mod}\:4) \equiv1, \\ \mu, \qquad & \rm{若\; }v\in P \rm{ 且\; } p\, ( \rm{mod}\:4) \equiv-1. \end{cases} \notag $

$ \rm (2) $ $ M_{U''}\left( \alpha^{v}\right) =\begin{cases} 0, & \rm{若\; }v\in Q \rm{ 且\; } q\, ( \rm{mod}\:4) \equiv1, \\ \mu, \qquad & \rm{若\; }v\in Q \rm{ 且\; } q\, ( \rm{mod}\:4) \equiv-1. \end{cases}\notag $

证   设$ v\in P $, 则$ R_{2}\left( \beta^{v}\right) =\left( p-1\right) /2 $, $ R_{2}\left( \beta^{v\theta}\right) =\left( p-1\right) /2 $. 若$ p\, ( \rm{mod}\:4) \equiv1 $, 则$ R_{2}\left( \beta^{v}\right)=0 $且$ R_{2}\left( \beta^{v\theta}\right) =0 $. 由(10)可得$ M_{U''}\left( \alpha^{v}\right)=\left( \mu+1\right)\!\! \left( T_{2}\left( \gamma^{v}\right) +T_{2}\left( \gamma^{v\eta}\right) \right) $. 由引理1, $ T_{2}\left( \gamma^{v\eta}\right)=\sum_{i\in B_{0}}\gamma^{v\eta i}=\sum_{i\in B_{1}}\gamma^{vi}=T_{2}\left( \gamma^{v}\right)+1 $, 则$ M_{U''}\left( \alpha^{v}\right)=\mu+1 $. 若$ p\, ( \rm{mod}\:4) \equiv-1 $, 则$ R_{2}\left( \beta^{v}\right)=1 $且$ R_{2}\left( \beta^{v\theta}\right) =1 $. 由(10)可得$ M_{U''}\left( \alpha^{v}\right)=T_{2}\left( \gamma^{v}\right)+\left( \mu+1\right)\!\!\left( T_{2}\left( \gamma^{v\eta}\right)+T_{2}\left( \gamma^{v}\right)+T_{2}\left( \gamma^{v\eta}\right) \right)+\mu T_{2}\left( \gamma^{v\eta}\right)=\mu\left( T_{2}\left( \gamma^{v}\right)+T_{2}\left( \gamma^{v\eta}\right)\right) $. 由$ T_{2}\left( \gamma^{v\eta}\right)=T_{2}\left( \gamma^{v}\right)+1 $可得, $ M_{U''}\left( \alpha^{v}\right)=\mu $. $ v\in Q $的情形类似可证.

引理6   记号同上. 若$ v\in Z_{N}^{*} $, 则

$ \begin{align*} \!M_{U''}\left( \alpha^{v}\right)\!&\!=\!\begin{cases} \!R_{2}\left( \beta^{\theta}\right) T_{2}\left( \gamma\right)\!+\!\left( \mu+1\right)\! \!\left(R_{2}\left( \beta^{\theta}\right) T_{2}\left( \gamma^{\eta}\right)+ T_{2}\left( \gamma\right)+T_{2}\left( \gamma^{\eta}\right)\right)\!+\!\mu R_{2}\left( \beta\right) T_{2}\left( \gamma^{\eta}\right), \! \\\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\:\:\:\:\:\, \rm{若 }v\in F_{0, 0}; \\ \!R_{2}\left( \beta\right) T_{2}\left( \gamma^{\eta}\right)\!+\!\left( \mu+1\right)\! \!\left(R_{2}\left( \beta\right) T_{2}\left( \gamma\right)+ T_{2}\left( \gamma\right)+T_{2}\left( \gamma^{\eta}\right)\right)\!+\!\mu R_{2}\left( \beta^{\theta}\right) T_{2}\left( \gamma\right), \!\\\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\:\:\:\:\:\, \rm{若 }v\in F_{1, 1}; \\ \!R_{2}\left( \beta\right) T_{2}\left( \gamma\right)\!+\!\left( \mu+1\right)\! \!\left(R_{2}\left( \beta\right) T_{2}\left( \gamma^{\eta}\right)+ T_{2}\left( \gamma\right)+T_{2}\left( \gamma^{\eta}\right)\right)\!+\!\mu R_{2}\left( \beta^{\theta}\right) T_{2}\left( \gamma^{\eta}\right), \! \\\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\:\:\:\:\:\, \rm{若 }v\in F_{1, 0}; \\ \!R_{2}\left( \beta^{\theta}\right) T_{2}\left( \gamma^{\eta}\right)\!+\!\left( \mu+1\right)\! \!\left(R_{2}\left( \beta^{\theta}\right) T_{2}\left( \gamma\right)+ T_{2}\left( \gamma\right)+T_{2}\left( \gamma^{\eta}\right)\right)\!+\!\mu R_{2}\left( \beta\right) T_{2}\left( \gamma\right), \! \\\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\:\:\:\:\:\, \rm{若 }v\in F_{0, 1}. \\ \end{cases} \notag \end{align*} $

证   若$ v\in F_{0, 0} $, 则$ v\, ( \rm{mod}\:p)\in A_{0} $且$ v\, ( \rm{mod}\:q)\in B_{0} $, 则$ R_{2}\left( \beta^{v\theta}\right) =\sum_{i\in A_{0}}\beta^{v\theta i}=\sum_{i\in A_{0}}\beta^{\theta i}=R_{2}\left(\beta^{\theta}\right) $, $ T_{2}\left( \gamma^{v\eta}\right) =\sum_{i\in B_{0}}\gamma^{v\eta i}=\sum_{i\in B_{0}}\gamma^{\eta i}=T_{2}\left(\gamma^{\eta}\right) $, $ T_{2}\left( \gamma^{v}\right)= \sum_{i\in B_{0}}\gamma^{vi}= \sum_{i\in B_{0}}\gamma^{i}= T_{2}\left(\gamma\right) $且$ R_{2}\left( \beta^{v}\right)= \sum_{i\in A_{0}}\beta^{vi}=\sum_{i\in A_{0}}\beta^{i}=R_{2}\left(\beta\right) $. 则由(10), $ M_{U''}\left( \alpha^{v}\right)=R_{2}\left( \beta^{\theta}\right) T_{2}\left( \gamma\right)+\left( \mu+1\right)\!\!\left(R_{2}\left( \beta^{\theta}\right) T_{2}\left( \gamma^{\eta}\right)+ T_{2}\left( \gamma\right)+T_{2}\left( \gamma^{\eta}\right)\right)+\mu R_{2}\left( \beta\right) T_{2}\left( \gamma^{\eta}\right) $. 其余情形类似可证.

引理7   记号同上, 则

$ \rm (1) $若$ p\, ( \rm{mod}\:8) \equiv\pm1 $, 当$ q\, ( \rm{mod}\:8) \equiv\pm1 $或$ q\, ( \rm{mod}\:8) \equiv\pm3 $, 则

$ \begin{equation} M_{U''}\left( \alpha^{v}\right) =\begin{cases} \mu+1, & \rm{若 }v\in F_{0, 0}, \\ 0, \qquad & \rm{若 }v\in F_{1, 1}, \\ \mu, \qquad & \rm{若 }v\in F_{1, 0}, \\ 1, \qquad & \rm{若 }v\in F_{0, 1}. \end{cases} \notag \rm{ 或\; } M_{U''}\left( \alpha^{v}\right) =\begin{cases} \mu, & \rm{若 }v\in F_{0, 0}, \\ 1, \qquad & \rm{若 }v\in F_{1, 1}, \\ \mu+1, \qquad & \rm{若 }v\in F_{1, 0}, \\ 0, \qquad & \rm{若 }v\in F_{0, 1}. \end{cases} \notag \end{equation} $

$ \rm (2) $若$ p\, ( \rm{mod}\:8) \equiv\pm3 $, 当$ q\, ( \rm{mod}\:8) \equiv\pm1 $或$ q\, ( \rm{mod}\:8) \equiv\pm3 $, 则

$ \begin{equation} M_{U''}\left( \alpha^{v}\right) =\begin{cases} 0, & \rm{若 }v\in F_{0, 0}, \\ \mu+1, \qquad & \rm{若 }v\in F_{1, 1}, \\ 1, \qquad & \rm{若 }v\in F_{1, 0}, \\ \mu, \qquad & \rm{若 }v\in F_{0, 1}. \end{cases} \notag \rm{ 或\; } M_{U''}\left( \alpha^{v}\right) =\begin{cases} 1, & \rm{若 }v\in F_{0, 0}, \\ \mu, \qquad & \rm{若 }v\in F_{1, 1}, \\ 0, \qquad & \rm{若 }v\in F_{1, 0}, \\ \mu+1, \qquad & \rm{若 }v\in F_{0, 1}. \end{cases} \notag \end{equation} $

证   对不同的情形, 证明方法是类似的, 因此只证明$ p\, ( \rm{mod}\:8) \equiv\pm1 $且$ q\, ( \rm{mod}\:8) \equiv\pm1 $的情形. 当$ p\, ( \rm{mod}\:8)\equiv\pm1 $且$ q\, ( \rm{mod}\:8) \equiv\pm1 $时, 由引理1和引理6, 若$ v\in F_{0, 0} $, 则$ M_{U''}\left( \alpha^{v}\right) =0+\left( \mu+1\right)\! \! \left( 1+0+0\right) +\mu\times0=\mu+1 $; 若$ v\in F_{1, 1} $, 则$ M_{U''}\left( \alpha^{v}\right) =0+\left( \mu+1\right)\! \! \left( 0+1+1\right) +\mu\times0=0 $; 若$ v\in F_{1, 0} $, 则$ M_{U''}\left( \alpha^{v}\right) =1+\left( \mu+1\right)\! \! \left( 1+0+0\right) +\mu\times0=\mu $; 若$ v\in F_{0, 1} $, 则$ M_{U''}\left( \alpha^{v}\right) =0+\left( \mu+1\right)\! \! \left( 0+1+0\right) +\mu\times1=1 $.

定理2   记号同上. 记$ H_{1}\left( x\right) =\prod_{t\in F_{0, 0}} \left( x-\alpha^{t}\right) $, $ H_{2}\left( x\right)\! \!=\!\prod_{t\in F_{1, 1}} \left( x-\alpha^{t}\right) $, $ H_{3}\left( x\right) =\prod_{t\in F_{1, 0}} \left( x-\alpha^{t}\right) $, $ H_{4}\left( x\right) =\prod_{t\in F_{0, 1}} \left( x- \alpha^{t}\right) $且$ Q\left( x\right) =\prod_{t\in Q} \left( x-\alpha^{t}\right) $. 则$ U''\left( t\right) $的线性复杂度$ LC\left( U''\left( t\right) \right) $和极小多项式$ m_{U''}\left( x\right) $如下：

$ \rm (1) $若$ p\, ( \rm{mod}\:8) \equiv\pm1 $且$ q\, ( \rm{mod}\:8) \equiv1 $, 则

$ \begin{equation} LC\left( U''\left( t\right) \right) =\frac{3pq-3p+q-1}{4}, m_{U''}\left( x\right) =\frac{ x^{pq}-1}{\left( x-1\right) H_{2}\left( x\right) Q\left( x\right)};\notag \end{equation} $

$ \rm (2) $若$ p\, ( \rm{mod}\:8) \equiv\pm1 $且$ q\, ( \rm{mod}\:8) \equiv-1 $, 则

$ \begin{equation} LC\left( U''\left( t\right) \right) =\frac{3pq+p+q-5}{4}, m_{U''}\left( x\right) =\frac{x^{pq}-1}{\left( x-1\right) H_{2}\left( x\right)};\notag \end{equation} $

$ \rm (3) $若$ p\, ( \rm{mod}\:8) \equiv\pm1 $且$ q\, ( \rm{mod}\:8) \equiv3 $, 则

$ \begin{equation} LC\left( U''\left( t\right) \right) =\frac{3pq+p+q-5}{4}, m_{U''}\left( x\right) =\frac{x^{pq}-1}{\left( x-1\right) H_{4}\left( x\right)};\notag \end{equation} $

$ \rm (4) $若$ p\, ( \rm{mod}\:8) \equiv\pm1 $且$ q\, ( \rm{mod}\:8) \equiv-3 $, 则

$ \begin{equation} LC\left( U''\left( t\right) \right) =\frac{3pq-3p+q-1}{4}, m_{U''}\left( x\right) =\frac{x^{pq}-1}{\left( x-1\right) H_{4}\left( x\right) Q\left( x\right)};\notag \end{equation} $

$ \rm (5) $若$ p\, ( \rm{mod}\:8) \equiv\pm3 $且$ q\, ( \rm{mod}\:8) \equiv1 $, 则

$ \begin{equation} LC\left( U''\left( t\right) \right) =\frac{3pq-3p+q-1}{4}, m_{U''}\left( x\right) =\frac{x^{pq}-1}{\left( x-1\right) H_{1}\left( x\right)Q\left( x\right)};\notag \end{equation} $

$ \rm (6) $若$ p\, ( \rm{mod}\:8) \equiv\pm3 $且$ q\, ( \rm{mod}\:8) \equiv-1 $, 则

$ \begin{equation} LC\left( U''\left( t\right) \right) =\frac{3pq+p+q-5}{4}, m_{U''}\left( x\right) =\frac{x^{pq}-1}{\left( x-1\right) H_{1}\left( x\right)};\notag \end{equation} $

$ \rm (7) $若$ p\, ( \rm{mod}\:8) \equiv\pm3 $且$ q\, ( \rm{mod}\:8) \equiv3 $, 则

$ \begin{equation} LC\left( U''\left( t\right) \right) =\frac{3pq+p+q-5}{4}, m_{U''}\left( x\right) =\frac{x^{pq}-1}{\left( x-1\right) H_{3}\left( x\right)};\notag \end{equation} $

$ \rm (8) $若$ p\, ( \rm{mod}\:8) \equiv\pm3 $且$ q\, ( \rm{mod}\:8) \equiv-3 $, 则

$ \begin{equation} LC\left( U''\left( t\right) \right) =\frac{3pq-3p+q-1}{4}, m_{U''}\left( x\right) =\frac{ x^{pq}-1}{\left( x-1\right) H_{3}\left( x\right)Q\left( x\right)}.\notag \end{equation} $

证   当$ p\, ( \rm{mod}\:8) \equiv\pm1 $且$ q\, ( \rm{mod}\:8) \equiv1 $时, 由引理7, 有$ |\left\lbrace v|v\in Z_{N}^{*}, M_{U''}\left( \alpha^{v}\right) =0\right\rbrace |=\frac{\left( p-1\right) \left( q-1\right) }{4} $, 又由引理5, 有$ |\left\lbrace v|v\in P, M_{U''}\left( \alpha^{v}\right) =0\right\rbrace |=0 $, $ |\left\lbrace v|v\in Q, M_{U''}\left( \alpha^{v}\right) =0\right\rbrace |=p-1 $. 结合式(11), 可得线性复杂度为$ LC\left( U''\left( t\right) \right) =pq-\frac{\left( p-1\right) \left( q-1\right) }{4}-\left( p-1\right) -1=\frac{3pq-3p+q-1}{4} $, 且极小多项式为$ m_{U''}\left( x\right) =\frac{ x^{pq}-1}{\left( x-1\right) H_{2}\left( x\right) Q\left( x\right)} $. 其余情形类似可证.

利用Magma程序, 验证了取不同参数时$ U''\left( t\right) $的线性复杂度, 见表 2. 结果与定理2结论一致.

由于代数结构的差异, $ \mathbb{Z}_{4} $和$ \mathbb{F}_{4} $上序列的综合算法也略有差异. 本文分析了两类四元序列在$ \mathbb{F}_{4} $上的线性复杂度和极小多项式. 证明了这两类四元序列在$ \mathbb{F}_{4} $上的线性复杂度不小于其周期的一半, 即这两类序列具有高的线性复杂度. 因此这两类序列可以有效地抵抗Berlekamp-Massey算法的攻击.