线性反馈移位寄存器(LFSRs)和带进位的反馈移位寄存器(FCSRs)是两种伪随机序列发生器.它们所产生的序列具有良好的伪随机性质, 如低相关性、长周期等.这些伪随机序列在密码学和通信系统中有着广泛的应用.理论上, 任何二元周期序列都可以由LFSR或FCSR生成.人们通常把能产生序列$s$的最短LFSRs (或FCSRs)的长度称为序列$s$的线性复杂度(或2-adic复杂度), 用符号$LC(s)$(或$\phi_{2}(s)$)表示.而Berlekamp-Massey算法(BMA)^[1]和FCSRs的有理逼近算法(RAA)^[2]分别是针对序列的LFSRs和FCSRs的有效算法.如果序列的线性复杂度或2-adic复杂度偏低, 则该序列在密码学意义下就是不安全的.因此, 线性复杂度和2-adic复杂度被认为是序列的两个重要的安全准则.而对于流密码中的密钥流生成器产生的周期序列, 为了抵抗RAA其2-adic复杂度应不小于其周期的一半.

交织技术是分析和设计序列的重要技术之一.许多最优自相关序列^{[3, 4]}、低相关序列集^{[5, 7]}、或低相关区序列集^[8]都是采用交织技术设计的或者被证明具有特殊的交织结构.例如, 利用交织结构, Tang和Gong在文献[3]中构造了三类具有优自相关性质的序列, 进一步地, Li和Tang在文献[9]证明了这些序列具有大的线性复杂度. Arasu等在文献[10]中构造了一类具有最优自相关性质的序列, 进一步地, Wang和Du等在文献[11]中证明其具有大的线性复杂度.后来, Tang和Ding在文献[4]中给出了比文献[3]和^[10]更一般的构造.上述所提到的交织序列基本都由两类不同的序列构成, 且它们的形式为$s=I(s_{0}, s_{1}, s_{0}^{'}, s_{1}^{'})$或$s=I(s_{0}, s_{0}^{'}, s_{1}, s_{1}^{'})$.但是这类序列的2-adic复杂度一直没人计算, 直到Xiong等在文献[12]中提出一种利用循环矩阵去计算二元序列的2-adic复杂度的方法, 以及Hu在文献[13]中提出运用自相关值的精确分布去计算二元序列的2-adic复杂度的方法.此外, 利用循环矩阵, Xiong等在文献[12]中证明了所有具有理想自相关值的序列的2-adic复杂度可达到其最大值. Xiong等在文献[14]中证明了两类基于交织结构构造的序列也具有最大2-adic复杂度.这两类序列中的一类是由Tang和Ding构造的^[4], 该序列具有最佳自相关性质; 另一类由Zhou等构造^[15], 该序列的相关值可达到最优的Tang-Fan-Matsufuji界.此外, 利用文献[13]提出的方法和精确自相关值分布, Sun等在文献[16]和文献[17]中分别给出了两类序列的2-adic复杂度的下界.

Tang等^[4]给出了一类具有优相关性质的二元序列的构造.最近, Yan等^[18]推广了文献[4]的构造, 并给出了该序列的自相关值的具体分布.本文将研究该序列的2-adic复杂度.具体地, 本文将在Tang和Yan等构造的二元序列的基础上, 利用Hu的方法, 给出这些序列的2-adic复杂度的一个下界.全文安排如下:第2节给出了交织结构和勒让德序列的定义, 并回顾了Tang和Yan等给出的一类具有优相关性质的二元序列的构造及其性质; 第3节, 给出了该二元序列的2-adic复杂度的一个下界; 第4节对本文工作做了小结.

设$v$是一个正整数, $s_{i}=(s_{i}(0), s_{i}(1), \cdots, s_{i}(v-1)), 0\le i\le u-1$为$u$个周期为$v$的二元序列.构造一个$v\times u$矩阵$I=(I_{i, j})$如下

$ I=\left[ \begin{matrix} s_{0}(0) & s_{1}(0) & \cdots & s_{u-1}(0) \\ s_{0}(1) & s_{1}(1) & \cdots & s_{u-1}(1) \\ \vdots & \vdots & \ddots & \vdots \\ s_{0}(v-1) & s_{1}(v-1) & \cdots & s_{u-1}(v-1) \\ \end{matrix} \right]. $

按行连接上述矩阵可得到一条长为$uv$的周期序列$s$, 称序列$s$为$s_i$, $0\le i \le u-1$的交织序列, 记为$s=I(s_{0}, s_{1}, \cdots s_{u-1}), $其中$I$表示交织算子.

设$p$是一个奇素数, 勒让德符号定义如下

$ \begin{equation*} \left(\frac{t}{p}\right)=\left\{ \begin{array}{ll} 1, &\mbox{若}\ t\in {\rm{QR}}_{p}, \\ -1, &\mbox{若}\ t\in {\rm{NQR}}_{p}. \end{array}\right. \end{equation*} $

其中${\rm{QR}}_{p}$和${\rm{NQR}}_{p}$分别为模$p$的二次剩余和非二次剩余.

勒让德序列定义如下

$ \begin{equation*} l(t)=\left\{ \begin{array}{ll} 0\mbox{或}1, &\mbox{若}\ t=0, \\ \frac{1}{2}(1-(\frac{t}{p})), &\mbox{其他}. \end{array}\right. \end{equation*} $

当$l(0)=1$时, 称$l(t)$为第一类勒让德序列, 记作$l(t)$; 当$l(0)=0$时, 称$l(t)$为第二类勒让德序列, 记作$l_{0}(t)$.

设$p$是一个奇素数, $a$和$b$是周期为$p$的第一类或第二类勒让德序列, 定义二元序列$s$如下

$ \begin{equation} s=I(a, L^{\eta}(\overline{a}), b, L^{\eta}(b)), \end{equation} $

(2.1)

其中${L}^{\eta}(a)$表示序列$a$左循环移$\eta$位, $\overline{a}$表示$a$的补序列.

引理1^[18]  设序列$s$定义如上, 则

(ⅰ) 当$p\equiv 1 \pmod 4$, 且$a=l(t), b=l_{0}(t)$时, 序列$s$的自相关值分布如下

$ \begin{equation*} R_{s}(\tau)=\left\{ \begin{array}{ll} -4, &\mbox{若}\ \tau_{2}=0;\\ -4, &\mbox{若}\ \tau_{2}=1\ \mbox{且}\ \tau_{1}+\eta\in {\rm{QR}}_{p};\\ 4, &\mbox{若}\ \tau_{2}=1\ \mbox{且}\ \tau_{1}+\eta\in {\rm{NQR}}_{p};\\ 0, &\mbox{若}\ \tau_{2}=1\ \mbox{且}\ \tau_{1}-\eta=0;\\ 0, &\mbox{若}\ \tau_{2}=2;\\ -4, &\mbox{若}\ \tau_{2}=3\ \mbox{且}\ \tau_{1}+1-\eta\in {\rm{QR}}_{p};\\ 4, &\mbox{若}\ \tau_{2}=3\ \mbox{且}\ \tau_{1}+1-\eta\in {\rm{NQR}}_{p};\\ 0, &\mbox{若}\ \tau_{2}=3\ \mbox{且}\ \tau_{1}+1-\eta=0. \end{array}\right. \end{equation*} $

(ⅱ) 当$p\equiv 1 \pmod 4$, 且$a=l_{0}(t), b=l(t)$时, 序列$s$的自相关值分布如下

$ \begin{equation*} R_{s}(\tau)=\left\{ \begin{array}{ll} -4, &\mbox{若}\ \tau_{2}=0;\\ 4, &\mbox{若}\ \tau_{2}=1\ \mbox{且}\ \tau_{1}+\eta\in {\rm{QR}}_{p};\\ -4, &\mbox{若}\ \tau_{2}=1\ \mbox{且}\ \tau_{1}+\eta\in {\rm{NQR}}_{p};\\ 0, &\mbox{若}\ \tau_{2}=1\ \mbox{且}\ \tau_{1}-\eta=0;\\ 0, &\mbox{若}\ \tau_{2}=2;\\ 4, &\mbox{若}\ \tau_{2}=3\ \mbox{且}\ \tau_{1}+1-\eta\in {\rm{QR}}_{p};\\ -4, &\mbox{若}\ \tau_{2}=3\ \mbox{且}\ \tau_{1}+1-\eta\in {\rm{NQR}}_{p};\\ 0, &\mbox{若}\ \tau_{2}=3\ \mbox{且}\ \tau_{1}+1-\eta=0. \end{array}\right. \end{equation*} $

(ⅲ) 当$p\equiv 3 \pmod 4$, 且$a=l(t), b=l_{0}(t)$时, 序列$s$的自相关值分布如下

$ \begin{equation*} R_{s}(\tau)=\left\{ \begin{array}{ll} -4, &\mbox{若}\ \tau_{2}=0;\\ -4, &\mbox{若}\ \tau_{2}=1\ \mbox{且}\ \tau_{1}-\eta\in {\rm{QR}}_{p};\\ 4, &\mbox{若}\ \tau_{2}=1\ \mbox{且}\ \tau_{1}-\eta\in {\rm{NQR}}_{p};\\ 0, &\mbox{若}\ \tau_{2}=1\ \mbox{且}\ \tau_{1}-\eta=0;\\ 0, &\mbox{若}\ \tau_{2}=2;\\ 4, &\mbox{若}\ \tau_{2}=3\ \mbox{且}\ \tau_{1}+\eta\in {\rm{QR}}_{p};\\ -4, &\mbox{若}\ \tau_{2}=3\ \mbox{且}\ \tau_{1}+\eta\in {\rm{NQR}}_{p}. \end{array}\right. \end{equation*} $

(ⅳ)  当$p\equiv 3 \pmod 4$, 且$a=l_{0}(t), b=l(t)$时, 序列$s$的自相关值分布如下

$ \begin{equation*} R_{s}(\tau)=\left\{ \begin{array}{ll} -4, &\mbox{若}\ \tau_{2}=0;\\ 4, &\mbox{若}\ \tau_{2}=1\ \mbox{且}\ \tau_{1}-\eta\in {\rm{QR}}_{p};\\ -4, &\mbox{若}\ \tau_{2}=1\ \mbox{且}\ \tau_{1}-\eta\in {\rm{NQR}}_{p};\\ 0, &\mbox{若}\ \tau_{2}=2;\\ -4, &\mbox{若}\ \tau_{2}=3\ \mbox{且}\ \tau_{1}+\eta\in {\rm{QR}}_{p};\\ 4, &\mbox{若}\ \tau_{2}=3\ \mbox{且}\ \tau_{1}+\eta\in {\rm{NQR}}_{p};\\ 0, &\mbox{若}\ \tau_{2}=3\ \mbox{且}\ \tau_{1}+1-\eta=0. \end{array}\right. \end{equation*} $

设$N$是一个正整数, $\mathbb{Z}_{N}$为模$N$的剩余类环.设$s=(s(0), s(1), \cdots, s(N-1))$为周期为$N$的二元序列, 定义其序列多项式为$S(x)=\sum\limits_{i=0}^{N-1}s(i)x^{i}\in \mathbb{Z}[x]$.由文献[19]可知, 若

$ \frac{S(2)}{2^{N}-1}=\frac{\sum\limits_{i=0}^{N-1}s(i)2^{i}}{2^{N}-1}=\frac{e}{f}, $

其中$0\le e\le f, \gcd(e, f)=1$.则序列$s$的2-adic复杂度$\phi_{2}(s)$为$\phi_{2}(s)=\lfloor\log_{2}\frac{2^{N}-1}{\gcd(2^{N}-1, S(2))}\rfloor, $其中$\lfloor z\rfloor$为小于或等于$z$的最大正整数.

引理2^[13] 设$s=(s(0), s(1), \cdots, s(N-1))$是一条周期为$N$的二元序列, $S(x)$为$s$的序列多项式, 记$T(x)=\sum\limits_{i=0}^{N-1}(-1)^{s_{i}}x^{i}$, 则

$ -2S(x)T(x^{-1})=N+\sum\limits_{i=1}^{N-1}R_{s}(i)x^{i}-T(x^{-1})\sum\limits_{i=0}^{N-1}x^{i}\pmod {x^{N}-1}. $

引理3 设$p$为奇素数且$p \equiv 1 \pmod 4$, $s$为式(2.1)定义的二元序列, 其中$a=l, b=l_0$, 则有$\gcd(S(2), 5)=1.$

证 由

$ S(x)=1+\sum\limits_{i\in{\rm{NQR}}_p}x^{4i}+\sum\limits_{i\in{\rm{QR}}_p}x^{4(i+\eta)+1}+\sum\limits_{i\in{\rm{NQR}}_p}x^{4i+2}+\sum\limits_{i\in{\rm{NQR}}_p}x^{4(i+\eta)+3}, $

有

$ \begin{equation*} \begin{split} S(2)&=1+\frac{p-1}{2}+2\times\frac{p-1}{2}+4\times\frac{p-1}{2}+8\times\frac{p-1}{2}\\ &=1\pmod5. \end{split} \end{equation*} $

进而$\gcd(S(2), 5)=1.$

引理4 设$p$为奇素数, 则有(1)$3|(2^{2p}-1), 5|(2^{2p}+1)$; (2)$\gcd(2p, \frac{2^{2p}+1}{5})=1, $ $\gcd(2p, \frac{2^{2p}-1}{3})=1$.

证  (1)  由$2^{2p}\equiv1\pmod3$及$2^{2p}\equiv-1\pmod5$易知.

(2)  显然有$\gcd(2, \frac{2^{2p}+1}{5})=\gcd(2, \frac{2^{2p}-1}{3})=1.$又由$2^{2p}+1\equiv5\pmod p$及$2^{2p}-1\equiv3\pmod p, $知$\gcd(p, \frac{2^{2p}+1}{5})=\gcd(p, \frac{2^{2p}-1}{3})=1.$进而

$ \gcd(2p, \frac{2^{2p}+1}{5})=1, \quad \gcd(2p, \frac{2^{2p}-1}{3})=1. $

定理1 设$p$为奇素数且$p \equiv 1 \pmod 4$, $s$为式(2.1)定义的二元序列, 其中$a=l, b=l_0$, 且$\eta=\frac{3p+1}{4}$, 则序列$s$的2-adic复杂度$\phi_2(s)$满足$\phi_2(s)\ge 2p, $即序列$s$的2-adic复杂度大于其周期的一半.

证 设$\tau=4\tau_{1}+\tau_{2}$, 其中$0\leq\tau_{1}< p, 0\leq\tau_{2}<4$.由引理1(ⅰ)有

$ \begin{equation*} \begin{split} \sum\limits_{\tau=0}^{4p-1}R_{s}(\tau)x^{\tau}=&(-4)(\sum\limits_{\tau_{2}=0, \tau_{1}\in\mathbb{Z}_p}x^{\tau}+\sum\limits_{\tau_{2}=1, \tau_{1}+\eta\in {\rm{QR}}_{p}}x^{\tau}+\sum\limits_{\tau_{2}=3, \tau_{1}+1-\eta\in {\rm{QR}}_{p}}x^{\tau})\\ &+4(\sum\limits_{\tau_{2}=1, \tau_{1}+\eta\in {\rm{NQR}}_{p}}x^{\tau}+\sum\limits_{\tau_{2}=3, \tau_{1}+1-\eta\in {\rm{NQR}}_{p}}x^{\tau})\pmod {x^{4p}-1}. \end{split} \end{equation*} $

由$\eta=\frac{3p+1}{4}$, 则

$ \begin{equation*} \begin{split} \sum\limits_{\tau=0}^{4p-1}R_{s}(\tau)x^{\tau}=&(-4)(\sum\limits_{\tau_{1}=0}^{p-1}x^{4\tau_{1}}+x^{p}\sum\limits_{\tau_{1}\in {\rm{QR}}_{p}}x^{4\tau_{1}}+x^{3p}\sum\limits_{\tau_{1}\in {\rm{QR}}_{p}}x^{4\tau_{1}})\\ &+4(x^{p}\sum\limits_{\tau_{1}\in {\rm{NQR}}_{p}}x^{4\tau_{1}}+x^{3p}\sum\limits_{\tau_{1}\in {\rm{NQR}}_{p}}x^{4\tau_{1}})\pmod {x^{4p}-1}\\ =&(-4)[\sum\limits_{\tau_{1}=0}^{p-1}x^{4\tau_{1}}+x^{p}(\sum\limits_{\tau_{1}\in {\rm{QR}}_{p}}x^{4\tau_{1}}-\sum\limits_{\tau_{1}\in {\rm{NQR}}_{p}}x^{4\tau_{1}})\\ &+x^{3p}(\sum\limits_{\tau_{1}\in {\rm{QR}}_{p}}x^{4\tau_{1}}-\sum\limits_{\tau_{1}\in {\rm{NQR}}_{p}}x^{4\tau_{1}})]\pmod {x^{4p}-1}\\ =&(-4)[\sum\limits_{\tau_{1}=0}^{p-1}x^{4\tau_{1}}+x^{p}(1+x^{2p})\sum\limits_{i\in \mathbb{Z}_{P}^{*}}\left(\frac{i}{p}\right)x^{4i}]\pmod {x^{4p}-1}. \end{split} \end{equation*} $

由引理2, 有

$ S(2)T(2^{-1})=-2p+2[\frac{2^{4p}-1}{15}+2^{p}(1+2^{2p})\sum\limits_{i\in\mathbb{Z}_{p}^{*}}\left(\frac{i}{p}\right)2^{4p}]\pmod{2^{4p}-1}. $

进而$S(2)T(2^{-1})=-2p\pmod{\frac{2^{2p}+1}{5}}.$

由引理3及引理4, 有$\gcd(S(2), 2^{4p}-1)\leq 2^{2p}-1$.因此有$\frac{2^{4p}-1}{\gcd(S(2), 2^{4p}-1)}\geq2^{2p}+1$, 由$\phi_{2}(s)$的定义知结论成立.

推论1 设$p$为奇素数且$p \equiv 1 \pmod 4$, $s$为式(2.1)定义的二元序列, 其中$a=l_0, b=l$, 且$\eta=\frac{3p+1}{4}$, 则序列$s$的2-adic复杂度$\phi_2(s)$满足: $\phi_2(s)\ge 2p, $即序列$s$的2-adic复杂度大于其周期的一半.

证 注意到, 该序列和定理1中序列很相似, 差别在于交织构造中的基序列略有差异.进而它们的2-adic复杂度的分析类似, 但是具体的计算细节也略有差异.设$\tau=4\tau_{1}+\tau_{2}$, 其中$0\leq\tau_{1}< p, 0\leq\tau_{2}<4$, 则

$ \begin{equation*} \begin{split} \sum\limits_{\tau=0}^{4p-1}R_{s}(\tau)x^{\tau}=&(-4)(\sum\limits_{\tau_{2}=0, \tau_{1}\in\mathbb{Z}_p}x^{\tau}+\sum\limits_{\tau_{2}=1, \tau_{1} +\eta\in {\rm{NQR}}_{p}}x^{\tau}+\sum\limits_{\tau_{2}=3, \tau_{1}+1-\eta\in {\rm{NQR}}_{p}}x^{\tau})\\ &+4(\sum\limits_{\tau_{2}=1, \tau_{1}+\eta\in {\rm{QR}}_{p}}x^{\tau}+\sum\limits_{\tau_{2}=3, \tau_{1}+1-\eta\in {\rm{QR}}_{p}}x^{\tau})\pmod {x^{4p}-1}. \end{split} \end{equation*} $

由$\eta=\frac{3p+1}{4}$, 则

$ \begin{equation*} \begin{split} \sum\limits_{\tau=0}^{4p-1}R_{s}(\tau)x^{\tau}=&(-4)(\sum\limits_{\tau_{1}=0}^{p-1}x^{4\tau_{1}}+x^{p}\sum\limits_{\tau_{1}\in {\rm{NQR}}_{p}}x^{4\tau_{1}}+x^{3p}\sum\limits_{\tau_{1}\in {\rm{NQR}}_{p}}x^{4\tau_{1}})\\ &+4(x^{p}\sum\limits_{\tau_{1}\in {\rm{QR}}_{p}}x^{4\tau_{1}}+x^{3p}\sum\limits_{\tau_{1}\in {\rm{QR}}_{p}}x^{4\tau_{1}})\pmod {x^{4p}-1}\\ %&=(-4)[\sum\limits_{\tau_{1}=0}^{p-1}x^{4\tau_{1}}+x^{p}(\sum\limits_{\tau_{1}\in \rm{NQR}_{p}}x^{4\tau_{1}}-\sum\limits_{\tau_{1}\in \rm{QR}_{p}}x^{4\tau_{1}})\\ %&+x^{3p}(\sum\limits_{\tau_{1}\in \rm{NQR}_{p}}x^{4\tau_{1}}-\sum\limits_{\tau_{1}\in \rm{QR}_{p}}x^{4\tau_{1}})]\pmod {x^{4p}-1}\\ =&(-4)\sum\limits_{\tau_{1}=0}^{p-1}x^{4\tau_{1}}+4x^{p}(1+x^{2p})\sum\limits_{i\in \mathbb{Z}_{P}^{*}}\left(\frac{i}{p}\right)x^{4i}\pmod {x^{4p}-1}. \end{split} \end{equation*} $

由引理2, 有

$ \begin{equation*} \begin{split} S(2)T(2^{-1})=& -2p+2\frac{2^{4p}-1}{15}+(-2)2^{p}(1+2^{2p})\sum\limits_{i\in\mathbb{Z}_{p}^{*}}\left(\frac{i}{p}\right)2^{4p}\pmod{2^{4p}-1}\\ =&-2p\pmod{\frac{2^{2p}+1}{5}}. \end{split} \end{equation*} $

类似定理1的证明, 由引理3及引理4, 有$\gcd(S(2), 2^{4p}-1)\leq 2^{2p}-1$.再由$\phi_{2}(s)$的定义知结论成立.

引理5 设$p$为奇素数且$p \equiv 3 \pmod 4$, $s$为式(2.1)定义的二元序列, 其中$a=l, b=l_0$, 其序列多项式为$S(x)$, 则有$\gcd(S(2), 3)=1.$

证 由

$ S(x)=1+\sum\limits_{i\in {\rm{NQR}}_p}x^{4i}+\sum\limits_{i\in {\rm{QR}}_p}x^{4(i+\eta)+1}+\sum\limits_{i\in {\rm{NQR}}_p}x^{4i+2}+\sum\limits_{i\in {\rm{NQR}}_p}x^{4(i+\eta)+3}, $

有

$ \begin{equation*} \begin{split} S(2)&=1+\frac{p-1}{2}+2\times\frac{p-1}{2}+4\times\frac{p-1}{2}+8\times\frac{p-1}{2}\\ &=1\pmod3. \end{split} \end{equation*} $

进而$\gcd(S(2), 3)=1.$

定理2 设$p$为奇素数且$p \equiv 3 \pmod 4$, $s$为式(2.1)定义的二元序列, 其中$a=l, b=l_0$, 且$\eta=\frac{3p-1}{4}$, 则序列$s$的2-adic复杂度$\phi_2(s)$满足$\phi_2(s)\ge 2p, $即序列$s$的2-adic复杂度大于其周期的一半.

证 设$\tau=4\tau_{1}+\tau_{2}$, 其中$0\leq\tau_{1}< p, 0\leq\tau_{2}<4$由引理1(ⅲ), 有

$ \begin{equation*} \begin{split} \sum\limits_{\tau=0}^{4p-1}R_{s}(\tau)x^{\tau}=&(-4)(\sum\limits_{\tau_{2}=0, \tau_{1}\in\mathbb{Z}_p}x^{\tau}+\sum\limits_{\tau_{2}=1, \tau_{1}-\eta\in { \rm{QR}}_{p}}x^{\tau}+\sum\limits_{\tau_{2}=3, \tau_{1}+\eta\in {\rm{NQR}}_{p}}x^{\tau})\\ &+4(\sum\limits_{\tau_{2}=1, \tau_{1}-\eta\in {\rm{NQR}}_{p}}x^{\tau}+\sum\limits_{\tau_{2}=3, \tau_{1}+\eta\in {\rm{QR}}_{p}}x^{\tau})\pmod {x^{4p}-1}. \end{split} \end{equation*} $

由$\eta=\frac{3p-1}{4}$, 则

$ \begin{equation*} \begin{split} =&(-4)(\sum\limits_{\tau_{1}=0}^{p-1}x^{4\tau_{1}}+x^{p}\sum\limits_{\tau_{1}\in {\rm{QR}}_{p}}x^{4\tau_{1}}+x^{3p}\sum\limits_{\tau_{1}\in {\rm{NQR}}_{p}}x^{4\tau_{1}})\\ &+4(x^{p}\sum\limits_{\tau_{1}\in {\rm{NQR}}_{p}}x^{4\tau_{1}}+x^{3p}\sum\limits_{\tau_{1}\in {\rm{QR}}_{p}}x^{4\tau_{1}})\pmod {x^{4p}-1}\\ =&(-4)\sum\limits_{\tau_{1}=0}^{p-1}x^{4\tau_{1}}+(-4)[x^{p}(\sum\limits_{\tau_{1}\in {\rm{QR}}_{p}}x^{4\tau_{1}}-\sum\limits_{\tau_{1}\in {\rm{NQR}}_{p}}x^{4\tau_{1}})\\ &-x^{3p}(\sum\limits_{\tau_{1}\in {\rm{QR}}_{p}}x^{4\tau_{1}}-\sum\limits_{\tau_{1}\in {\rm{NQR}}_{p}}x^{4\tau_{1}})]\pmod {x^{4p}-1}\\ =&(-4)[\sum\limits_{\tau_{1}=0}^{p-1}x^{4\tau_{1}}+x^{p}(1-x^{2p})\sum\limits_{i\in \mathbb{Z}_{P}^{*}}\left(\frac{i}{p}\right)x^{4i}]\pmod {x^{4p}-1}. \end{split} \end{equation*} $

由引理2, 有

$ S(2)T(2^{-1})=-2p+2[\frac{2^{4p}-1}{15}+2^{p}(1-2^{2p})\sum\limits_{i\in\mathbb{Z}_{p}^{*}}\left(\frac{i}{p}\right)2^{4p}]\pmod{2^{4p}-1}. $

进而$S(2)T(2^{-1})=-2p\pmod{\frac{2^{2p}-1}{3}}.$由引理4及引理5可知

$ \gcd(S(2), 2^{4p}-1)\leq\gcd(S(2), \frac{2^{2p}-1}{3})\cdot\gcd(S(2), 3)\cdot\gcd(S(2), 2^{2p}+1)\leq 2^{2p}+1. $

再由$\phi_{2}(s)$的定义, 有

$ \frac{2^{4p}-1}{\gcd(S(2), 2^{4p}-1)}\geq\frac{2^{4p}-1}{2^{2p}+1}=2^{2p}-1. $

因此结论成立.

推论2 设$p$为奇素数且$p \equiv 3 \pmod 4$, $s$为式(2.1)定义的二元序列, 其中$a=l_0, b=l$, 且$\eta=\frac{3p-1}{4}$, 则序列$s$的2-adic复杂度$\phi_2(s)$满足$\phi_2(s)\ge 2p, $即序列$s$的2-adic复杂度大于其周期的一半.

证 注意到, 该序列和定理2中序列很相似, 差别在于交织构造中的基序列略有差异.进而它们的2-adic复杂度的分析类似, 但是具体的计算细节也略有差异.设$\tau=4\tau_{1}+\tau_{2}$, 其中$0\leq\tau_{1}< p, 0\leq\tau_{2}<4$.由引理1(ⅳ)有

$ \begin{equation*} \begin{split} \sum\limits_{\tau=0}^{4p-1}R_{s}(\tau)x^{\tau}=&(-4)(\sum\limits_{\tau_{2}=0, \tau_{1}\in\mathbb{Z}_p}x^{\tau}+\sum\limits_{\tau_{2}=1, \tau_{1}-\eta\in {\rm{NQR}}_{p}}x^{\tau}+\sum\limits_{\tau_{2}=3, \tau_{1}+\eta\in {\rm{QR}}_{p}}x^{\tau})\\ &+4(\sum\limits_{\tau_{2}=1, \tau_{1}-\eta\in {\rm{QR}}_{p}}x^{\tau}+\sum\limits_{\tau_{2}=3, \tau_{1}+\eta\in {\rm{NQR}}_{p}}x^{\tau})\pmod {x^{4p}-1}. \end{split} \end{equation*} $

由$\eta=\frac{3p-1}{4}$, 则

$ \begin{equation*} \begin{split} \sum\limits_{\tau=0}^{4p-1}R_{s}(\tau)x^{\tau}=&(-4)(\sum\limits_{\tau_{1}=0}^{p-1}x^{4\tau_{1}}+x^{p}\sum\limits_{\tau_{1}\in {\rm{NQR}}_{p}}x^{4\tau_{1}}+x^{3p} \sum\limits_{\tau_{1}\in {\rm{QR}}_{p}}x^{4\tau_{1}})\\ &+4(x^{p}\sum\limits_{\tau_{1}\in {\rm{QR}}_{p}}x^{4\tau_{1}}+x^{3p}\sum\limits_{\tau_{1}\in {\rm{NQR}}_{p}}x^{4\tau_{1}})\pmod {x^{4p}-1}\\ %&=(-4)\sum\limits_{\tau_{1}=0}^{p-1}x^{4\tau_{1}}+4[x^{p}(\sum\limits_{\tau_{1}\in \rm{QR}_{p}}x^{4\tau_{1}}-\sum\limits_{\tau_{1}\in \rm{NQR}_{p}}x^{4\tau_{1}})\\ %&-x^{3p}(\sum\limits_{\tau_{1}\in \rm{QR}_{p}}x^{4\tau_{1}}-\sum\limits_{\tau_{1}\in \rm{NQR}_{p}}x^{4\tau_{1}})]\pmod {x^{4p}-1}\\ =&(-4)\sum\limits_{\tau_{1}=0}^{p-1}x^{4\tau_{1}}+4[x^{p}(1-x^{2p})\sum\limits_{i\in \mathbb{Z}_{P}^{*}}\left(\frac{i}{p}\right)x^{4i}]\pmod {x^{4p}-1}. \end{split} \end{equation*} $

由引理2, 有

$ \begin{equation*} \begin{split} S(2)T(2^{-1})=&-2p-2\frac{2^{4p}-1}{15}+2[2^{p}(1-2^{2p})\sum\limits_{i\in\mathbb{Z}_{p}^{*}}\left(\frac{i}{p}\right)2^{4p}]\pmod{2^{4p}-1}\\ =&-2p\pmod{\frac{2^{2p}-1}{3}}. \end{split} \end{equation*} $

由引理4及引理5, $\gcd(S(2), 2^{4p}-1)\leq 2^{2p}+1.$再由$\phi_{2}(s)$的定义可知

$ \frac{2^{4p}-1}{\gcd(S(2), 2^{4p}-1)}\geq\frac{2^{4p}-1}{2^{2p}+1}=2^{2p}-1. $

本文研究了一类具有优自相关性质的二元序列的2-adic复杂度, 给出了该类序列的2-adic复杂度的一个下界.本文的结果表明这类序列的2-adic复杂度不小于其周期的一半, 这意味着这些序列可以抵抗针对带进位的反馈移位寄存器的有理逼近算法的攻击.