设有限域${\mathbb{F}}_p=\{0,1,\cdots ,p-1\}$，其中p为奇素数。g为模p的一个本原根。若r|(p-1),则r阶割圆类定义为

其中,$j=0,1,\cdots ,r-1$。易知，$D_j^{(r)}$构成${\mathbb{F}}_p\backslash \left\{0\right\}$的一个划分，并被广泛应用于定义伪随机序列^[1]。

当r=2时，Legendre序列(s_u)^[2,3,4]定义为

其中，u≥0。

当r=4时,Ding-Helleseth-Lam序列(s_u)^[5]定义为

其中，u≥0。

当r=6且p形如4x²+27，$x\in \mathbb{N}$时，Hall 六次剩余序列(s_u)^[6,7]定义为

其中，u≥0。

需要注意的是，在文献[6,7]中，g的选择需满足$3\in D_1^{(6)}$。

上述几类二元序列已受到广泛的关注和研究。研究表明，这些二元序列具有好的伪随机特性，包括一致分布性、最优相关性、高的线性复杂度等^{[1,2,3,5,6,8,9,10,11,12]}。Xiong 等^[13]证明了 Legendre、Ding-Helleseth-Lam 二元序列的 2-adic 复杂度等于周期p。最近，Su等^[14]基于Ding-Helleseth-Lam二元序列使用交织的方法构造了一个周期为4p的具有优的自相关值的二元序列。通常把上面这种$Z_p^{*}$(p为素数)上的割圆类称为经典割圆类，对应的序列称为经典割圆序列，而把$Z_n^{*}$(n为合数)上的割圆类称为广义割圆类，对应的序列称为广义割圆序列^{[15,16,17,18,19,20,21,22]}。

文献[23,24]把上述类型序列(s_u)视为p-进制序列并研究了其在有限域${\mathbb{F}}_p$上的k-错线性复杂度。但是，(s_u)在${\mathbb{F}}_2$上的k-错线性复杂度还未彻底解决。文献[1,25]证明了任意的非常数二元序列的k错线性复杂度的一个下界。

命题1 ([1，Theorem 3.3.1]) 对周期为p的任意非常数二元序列(s_u)，其在${\mathbb{F}}_2$上的k-错线性复杂度 LC _k((s_u)) 满足 k<min{W_H((s_u)),p-W_H((s_u))}时，LC _k((s_u))≥ord _p(2)。其中，ord _p(2)表示2在模p的阶，W_H((s_u))表示序列(s_u)的一个周期中所含1的个数。

本文工作主要是考虑由经典割圆类定义的序列(s_u)的k-错线性复杂度。本文计算了 Legendre序列、Ding-Helleseth-Lam序列和Hall六次剩余序列在${\mathbb{F}}_2$上的1-错线性复杂度，并限制2在模p的阶的某些取值，给出了这些序列在${\mathbb{F}}_2$上的k-错线性复杂度的一些结果。周期序列的离散傅里叶变换在本文的证明中起到了关键作用。

下面介绍线性复杂度、k-错线性复杂度和周期序列的离散傅里叶变换等概念。

对于${\mathbb{F}}_2$上周期为T的序列(s_u)，其线性复杂度（记为LC((s_u))）定义为(s_u)满足${\mathbb{F}}_2$上的如下线性递归关系的最小阶L。

其中，u≥0,c₀ ≠0,$c_1,\cdots ,c_{L-1}\in {\mathbb{F}}_2$。记$S(X)=s_0+s_{1}X+s_2{X}^2+\cdots +s_{T-1}{X}^{T-1}\in {\mathbb{F}}_2[X]$,S(X) 为 $(s_u)$ 的生成多项式。

那么，(s_u)在${\mathbb{F}}_2$上的线性复杂度可通过式(4)计算。

对于整数k≥0，(s_u)在${\mathbb{F}}_2$上的k-错线性复杂度（记为LC _k((s_u))）是指在序列的一个周期中改变至多k个元素后所得这些序列在${\mathbb{F}}_2$上的线性复杂度的最小值^[26]。即

其中，(e_u)为周期为T的错误序列，W_H((e_u))为(e_u)的一个周期中所含1的个数。k-错线性复杂度也被称为球体复杂度^[27]，本文不做详细描述。易知， LC₀((s_u))=LC((s_u))，且

其中，l=W_H((s_u))。

线性复杂度和k-错线性复杂度是序列的重要密码学性质，它们刻画的是序列的可预测性，从而衡量该序列是否适用于密码学领域。从密码学应用角度考虑，一个序列的线性复杂度应尽可能大，并且序列在改变若干项后其线性复杂度不应明显降低。

对于奇数T，序列(s_u) 的离散傅里叶变换$({\rho }_0,{\rho }_1,\cdots ,{\rho }_{T-1})$和序列(s_u)的线性复杂度具有紧密的联系。记m=ord_T(2)表示2在模T的乘法阶。对于T阶本原单位根$\beta \in {\mathbb{F}}_{2^m}$，离散傅里叶变换（DFT， discrete Fourier transform）^[28,29]定义为

Blahut定理^[30]给出了序列$(s_u)$的线性复杂度及其与DFT之间的关系，如式(7)所示。

其中，#{⋅}表示集合{⋅}中的元素个数。

多项式$G(X)={\displaystyle \sum _{0\le i<T}{\rho }_i}{X}^i\in {\mathbb{F}}_{2^m}[x]$≤在编码理论中被称为 Mattson-Solomon 多项式^[31]。由 DFT 的逆变换，有

对于给定的β，G(X)在模x^T -1下是唯一确定的，G(X)也称为序列(s_u)对应于β的 defining多项式^[34]。

Alecu 和 Sǎlǎgean^[33,34]利用离散傅里叶变换给出了一个计算序列的k-错线性复杂度的近似算法。他们的方法有助于本文考虑 Legendre 序列、Ding-Helleseth-Lam 序列和Hall六次剩余序列的k错线性复杂度。本节计算了这些序列的离散傅里叶变换。更详细的讨论见文献[32]。

由$D_l^{(r)}$的定义可知

其中，u∈D_j。下文中D^(r)下标的计算都是在模r下进行的，即对所有的0≤l<r，有$D_{l+r}^{(r)}=D_l^{(r)}$。定义

其中，0≤l<r。本文首先给出并证明如下关于内积计算${\mathcal{C}}_i^{(r)}(\beta ){\mathcal{C}}_j^{(r)}(\beta )$的引理，其中0≤i,j<r。

引理1 设β为${\mathbb{F}}_2$的某一个扩域上的p阶本原单位根。对任意一对整数i,j满足0≤i,j<r，有

证明 对任意的0≤l<r，由于$D_l^{(r)}=g^l{D}_0^{(r)}$，可得

设ord(γ_w)表示γ_w的阶。由于β是p阶本原单位根，则有ord(γ_w)|p。若ord(γ_w)= p，则

若ord(γ_w)=1，则

下面分别计算使ord(γ_w)=1和ord(γ_w)= p的元素$w\in D_0^{(r)}$的个数。

可以注意到ord(γ_w)=1当且仅当$g^{i-j}+w\equiv 0\left(\mathrm{mod}p\right)$,$w\equiv g^{\frac{p-1}{2}+i-j}\left(\mathrm{mod}p\right)$即 。由于$w\in D_0^{(r)}$，则$r|(\frac{(p-1)}{2}+i-j)$。也就是说，存在 $w\in D_0^{(r)}$使$g^{i-j}+w\equiv 0\left(\mathrm{mod}p\right)$i等式成立，当且仅当$r|(\frac{p-1}{2}+，i-j)$并且w是唯一的，因此，当$r|(\frac{p-1}{2}+i-j)$时，有$\frac{p-1}{r}-1$个元素$w\in D_0^{(r)}$满足$\text{ord}({\gamma }_w)=p$，而只有一个$w\in D_0^{(r)}$满足$\text{ord}({\gamma }_w)=1$。若$r\nmid (\frac{p-1}{2}+i-j)$，则对所有的$w\in D_0^{(r)}$，都有ord(γ_w)= p。

综上所述，可得

证毕。

下面给出Legendre序列、Ding-Helleseth-Lam序列和Hall六次剩余序列的Mattson-Solomon 多项式。

当r=2时，若$2\in D_0^{(2)}$，则$D_i^{(2)}(\beta )\in {\mathbb{F}}_2$；若$2\in D_1^{(2)}$ ，则$D_i^{(2)}(\beta )\in {\mathbb{F}}_4\backslash {\mathbb{F}}_2$，其中i=0,1。

注意到$2\in D_0^{(2)}$（即 2 为模p的平方剩余）当且仅当p≡±1(mod 8)， $2\in D_1^{(2)}$当且仅当p≡±3(mod 8)。

命题2 设β为${\mathbb{F}}_2$的某一个扩域上的p阶本原单位根满足：当p≡±1(mod 8)时，$D_0^{(2)}(\beta )=0$；当p≡±3(mod 8)时，$D_0^{(2)}(\beta )=\omega$，其中$\omega \in {\mathbb{F}}_4\backslash {\mathbb{F}}_2$ 。那么，式(1)定义的Legendre序列(s_u)的对应于β的Mattson-Solomon 多项式为

需要说明的是，当 p≡±1(mod 8)时，选择$D_0^{(2)}(\beta )=1$；当 p≡±3(mod 8)时，选择$D_0^{(2)}(\beta )={\omega }^2\in {\mathbb{F}}_4$。这样虽然得到不同形式的G(x)，但是并不影响本文的讨论结果。

证明 由引理 1 可得式(1)定义的 Legendre 序列(s_u)的Mattson-Solomon多项式为

显然，在已知条件$D_0^{(2)}(\beta )$( 的取值假设下，当p≡1 (mod 4)时，易知

即s _u =G(β^u)，当u≥0。对于p≡3 (mod 4)的情况可类似验证。

证毕。

由式(7)可得如下结论。

推论1^[3] 由式(1)定义的Legendre序列(s_u)的线性复杂度为

对于r=4的情况，由4|(p-1)，则 p 满足p≡1(mod 8)或p≡-3(mod 8)。由引理 1 可知，由式(2)定义的 Ding-Helleseth-Lam 序列(s_u) 的Mattson-Solomon多项式如下所示。

当 p≡1 (mod 8)时，

当p≡-3( mod 8)时，

另外，注意到${\displaystyle \sum _{i=0}^3{D}_i^{(4)}}(\beta )=1$ ,易证对于0≤i<4有

和

因此，可得

其中，0≤i≤4。

注意到，若 p≡1(mod 8)，则$2\in D_0^{\left(4\right)}\cup D_2^{\left(4\right)}$（即2 是模p的平方剩余），有$D_0^{(4)}(\beta )=D_2^{(4)}(\beta )\in {\mathbb{F}}_2$。综上所述，可得命题3。

命题3 设β为${\mathbb{F}}_{\text{2}}$的某一个扩域上的p阶本原单位根。

1) 若p≡1(mod 8)，令$D_0^{(4)}(\beta )=D_2^{(4)}(\beta )=0$，则由式(2)定义的Ding-Helleseth-Lam序列(s_u)对应于β的Mattson-Solomon多项式G(x)如下。

若$2\in D_0^{\left(4\right)}$且$D_0^{\left(4\right)}\left(\beta \right)+D_1^{\left(4\right)}\left(\beta \right)=0$，则

若$2\in D_2^{(4)}$且$D_0^{(4)}\left(\beta \right)+D_1^{(4)}\left(\beta \right)=\omega \in {\mathbb{F}}_4\backslash {\mathbb{F}}_2$，则$\tilde{G}(X)=G(X)+G_k(X),=\omega D_0^{(4)}(X)+\omega D_1^{(4)}(X)+(1+\omega )D_2^{(4)}(X)+(1+\omega )D_3^{(4)}(X)$。

2) 若 p≡-3(mod 8) ,令 $D_0^{(4)}(\beta )+D_1^{(4)}(\beta )=D_1^{(4)}(\beta )=\theta \in {\mathbb{F}}_{16}$且 θ⁴ =1+θ，则由式 (2)定义的Ding-Helleseth-Lam 序列 (s_u)对应于β 的Mattson-Solomon多项式G(x)如下。

若$2\in D_1^{(4)}$，则

若$2\in D_3^{(4)}$，则

在命题 3 中，当 p≡1 (mod 8)时，若选择$D_0^{(4)}(\beta )+D_2^{(4)}(\beta )$和$D_0^{(4)}(\beta )+D_1^{(4)}(\beta )$的其他取值，虽然得到不同形式的G(x)，但是并不影响讨论结果。

推论 2^[5]由式(2)定义的 Ding-Helleseth-Lam序列(s_u)的线性复杂度为

对于 Hall 六次剩余序列，由于p=4 ²x+27，则有p≡-1 (mod 8)或 p≡3(mod 8)。

此外，若p≡-1 (mod 8)，那么由[6,Lemma 2]，可知 $D_0^{(6)}(\beta )+D_3^{(6)}(\beta )$、 $D_1^{(6)}(\beta )+D_4^{(6)}(\beta )$和$D_2^{(6)}(\beta )+D_5^{(6)}(\beta )$ 中有一个值为1，其他2个值为0，其中β是${\mathbb{F}}_2$的某一个扩域的p阶本原单位根。由[6,Theorem 1]，存在β使得 $D_0^{(6)}(\beta )+D_1^{(6)}(\beta )+D_3^{(6)}(\beta )=1$，对同一个β，由[6,Theorem 1]的证明可得式(9)。

若 p≡3 (mod 8)，类似地，由[6,Lemma 1]，可知 $D_0^{(6)}(\beta )+D_3^{(6)}(\beta )$、 $D_1^{(6)}(\beta )+D_4^{(6)}(\beta )$和$D_2^{(6)}(\beta )+D_5^{(6)}(\beta )$ 中有一个值为1，而其他2个值为0。事实上，此时$2\in D_3^{(6)}$，则有${\left(D_i^{(6)}(\beta )+D_{i+3}^{(6)}(\beta )\right)}^2=D_i^{(6)}(\beta )+D_{i+3}^{(6)}(\beta )$，其中i=0,1,2。注意到

若$D_0^{(6)}(\beta )+D_3^{(6)}(\beta )=D_1^{(6)}(\beta )+D_4^{(6)}(\beta )=D_2^{(6)}(\beta )+D_5^{(6)}(\beta )=1$，则导出矛盾。因此，设$D_1^{(6)}(\beta )+D_4^{(6)}(\beta )=1$，且$D_0^{(6)}(\beta )+D_3^{(6)}(\beta )=D_2^{(6)}(\beta )+D_5^{(6)}(\beta )=0$。注意到，$D_0^{(6)}(\beta ),D_2^{(6)}(\beta ),D_3^{(6)}(\beta ),D_5^{(6)}(\beta )\in {\mathbb{F}}_2$且$D_1^{(6)}(\beta ),D_4^{(6)}(\beta )\in {\mathbb{F}}_4\backslash {\mathbb{F}}_2$。与[6,Theorem 1]的证明类似，有

则由引理1，可得命题4。

命题 4 设β是${\mathbb{F}}_2$的某个扩域上的p阶本原单位根，且当 p≡-1 (mod 8)时，β满足式(9)；而当 p≡3 (mod 8)时，β满足式(10)，则由式(3)定义的Hall六次剩余序列(s_u)对应于β的MattsonSolomon多项式如下所示。

若p≡-1 (mod 8)，则$G(X)=1+D_3^{(6)}(X)$,

若p≡3(mod 8)，则

推论 3^[6]由式(3)定义的 Hall 六次剩余序列(s_u)的线性复杂度为

由式(5)可知，周期为p的二元序列(s_u)的k错线性复杂度是指在改变序列(s_u)的第一个周期中至多k项后（随后的其他周期中做相同改变），可得序列$({\tilde{s}}_u)$的最小线性复杂度，即

其中，(e_u)为一个错误序列满足W_H((e_u))≤k。受到文献[33,34]的启发，下面给出使用(e_u)的离散傅里叶变换求序列的k-错线性复杂度的方法。

设G(x)、G_k(X)和$\tilde{G}(X)$分别是(s_u)、(e_u)和$({\tilde{s}}_u)$的Mattson-Solomon多项式。记

由式(8)知$\tilde{G}(X)=G(X)+G_k(X)$ ,则有

由式(7)可知，序列 $({\tilde{s}}_u)$ 的线性复杂度$\text{LC}(({\tilde{s}}_u))=\#\{i:{\xi }_i\ne 0,0\le i<p\}$ 。只要知道ρ_i，则可计算得到η_i，并由式(11)确定式(12)是否成立

由此证明，序列(s_u)在改变若干项之后其线性复杂度降低了。

命题 5 由式(1)定义的Legendre序列(s_u)在F₂上的1-错线性复杂度如下

证明 不妨设错误序列(e_u)的第一个周期中对某个0≤u₀< p 满足$e_{u_0}=1$，而对其他0≤ u≠u ₀< p 满足e_u =0。(e_u) 的离散傅里叶变换为${\eta }_i={\beta }^{i{u}_0}$,0≤i< p。特别地，若u₀=0，则对所有的0≤i< p 有η_i =1；否则，η₀=1且对所有的1≤i< p有η_i的阶为p。

下面考虑p≡-1 (mo d 8)的情况。由命题 2 和式(11)，可得

若u₀ ≠0，则对所有的1≤i< p有ξ_i ≠0，且修改后的序列 $({\tilde{s}}_u)$的线性复杂度满足$LC(({\tilde{s}}_u))=p-1>LC((s_u))$ 。而当u₀=0时，有

这说明若改变序列(s_u)的第一项s₀的值后，其线性复杂度从$\frac{p+1}{2}$降低为$\frac{p-1}{2}$。这就证明了第一种情况，而对于其他3种情况的证明方法类似。

证毕。

用命题5的证明方法，可以得到下面2个结论。

命题6 由式(2)定义的Ding-Helleseth-Lam序列(s_u)在${\mathbb{F}}_2$上的1-错线性复杂度为

命题7 由式(3)定义的Hall六次剩余序列(s_u)在${\mathbb{F}}_2$上的1-错线性复杂度为

对于k≥2的情况，要确定 Legendre 序列、Ding-Helleseth-Lam序列和Hall六次剩余序列的k错线性复杂度是不容易的。但是，在一些特定的条件下可以得到部分结果。通过错误序列(e_u)的离散傅里叶变换$({\eta }_0,{\eta }_1,\cdots ,{\eta }_{p-1})$的适当取值，并通过式(11)使得式(13)成立。

也就是说，改变序列(s_u)的W_H((e_u))项可使其线性复杂度降低。然后，从$({\eta }_0,{\eta }_1,\cdots ,{\eta }_{p-1})$中计算得到(e_u)，从而得到W_H((e_u))，即k的值。

假设${\text{ord}}_p(2)=\frac{p-1}{d}$，并定义

$T_i=g^i{T}_0=\{g^i{2}^j\text{(}\mathrm{mod}p):0\le j<{\text{ord}}_p(2)\}$，1≤i<d其中g为第1节中定义的模p的本原元。令

设${\mathcal{l}}_i$表示集合T_i中的最小元素值（也称为陪集首元），其中0≤i<d。对于一个二元序列的离散傅里叶变换为$({\varphi }_0,{\varphi }_1,\cdots ,{\varphi }_{p-1})$，有${\varphi }_0\in {\mathbb{F}}_2$，并定义 $({\varphi }_0,{\varphi }_1,\cdots ,{\varphi }_{p-1})$的 DFT-leader-vector 为$[{\varphi }_0;{\varphi }_{{\mathcal{l}}_0},{\varphi }_{{\mathcal{l}}_1},\cdots ,{\varphi }_{{\mathcal{l}}_{d-1}}]$。

由上述T₀的定义易知，DFT-leader-vector 是由$({\varphi }_0,{\varphi }_1,\cdots ,{\varphi }_{p-1})$唯一确定的，反之亦然。具体地，若${\varphi }_{{\mathcal{l}}_i}=a\in {\mathbb{F}}_{2^{\frac{p-1}{d}}}$，则${\varphi }_{2^j{\mathcal{l}}_i\text{(}\mathrm{mod}p)}=a^{2^j}$，其中0≤i<d。

若${\text{ord}}_p(2)=\frac{p-1}{2}$或 $\frac{4}{p-1}$ ，下面先证明Legendre 序列的k-错线性复杂度的部分结果。若ord _p(2)= p-1，由推论1、命题1和命题5可得如下结论。

当p≡-3( mod 8)时，

当p≡3(mod 8)时，

命题8 设${\text{ord}}_p(2)=\frac{p-1}{2}$，则由式(1)定义的Legendre序列在${\mathbb{F}}_2$上的k-错线性复杂度如下。

当p≡1( mod 8)时，

当p≡-1 (mod 8)时，

证明 由于${\text{ord}}_p(2)=\frac{p-1}{2}$， 2 是模p的平方剩余，因此， p≡1( mod 8)或p≡-1 (mod8)。那么，由推论1、命题1和命题5即得所要结果。

命题9 设${\text{ord}}_p(2)=\frac{p-1}{4}$，则由式(1)定义的Legendre序列在${\mathbb{F}}_2$上的k-错线性复杂度如下

或

证明 由${\text{ord}}_p(2)=\frac{p-1}{4}$,$2\in D_0^{(2)}$，则p≡1( mod 8)。另外，根据上述定义的 T_i，有 $D_0^{(2)}=T_0\cup T_2$,$D_1^{(2)}=T_1\cup T_3$ 和$T_i(\beta )\in {\mathbb{F}}_2$ ，其中0≤i<4。由命题2 中假设的$D_0^{(2)}(\beta )=0$，有T₀(β)=T₂(β)=1或T₀(β)=T₂(β)=0。

再由命题 2，序列(s_u) 的离散傅里叶变换$({\rho }_0,{\rho }_1,\cdots ,{\rho }_{p-1})$的DFT-leader-vector是[0;1,0,1,0]。为了使(s_u)的k-错线性复杂度降低，即使序列$({\tilde{s}}_u)$的离散傅里叶变换$({\xi }_0,{\xi }_1,\cdots ,{\xi }_{p-1})$满足

由式(11)可知，错误序列(e_u)的离散傅里叶变换$({\eta }_0,{\eta }_1,\cdots ,{\eta }_{p-1})$的DFT-leader-vector有以下几种情况。

其中${\eta }_0\in {\mathbb{F}}_2$，$a,b\in {\mathbb{F}}_{2^{(p-1)/4}}\backslash \left\{1\right\}$和$c,d\in {\mathbb{F}}_{2^{(p-1)/4}}\backslash \left\{0\right\}$。

取序列(e_u)的离散傅里叶变换$({\eta }_0,{\eta }_1,\cdots ,{\eta }_{p-1})$的 DFT-leader-vector 为[ ₀η;1,1,1,0]，序列(s_u)的线性复杂度从$\frac{p-1}{2}$降低为${\eta }_0+\frac{p-1}{4}$，则可通过如下计算得到(e_u)。

若命题2中选择的β满足T₀(β)=T₂(β)=1，则设η₀ =0。由于$D_1^{(2)}(\beta )=1=T_1(\beta )+T_3(\beta )$ ，则有$W_H((e_u))=\frac{p-1}{4}$，因此T₁(β)=0且T₃(β)=1，或T₁(β)=1且T₃(β)=0。可得

由此完成了第一种情况的证明。

若命题2中选择的β满足T₀(β)=T₂(β)=0，选择η 1₀=，则可计算得到满足$W_H((e_u))=1+\frac{p-1}{4}$的错误序列(e_u)，进而有${\text{LC}}_{1+\frac{p-1}{4}}((s_u))\le 1+\frac{p-1}{4}$。由命题1可完成第二种情况的证明。

证毕。

下面考虑由式(2)定义的Ding-Helleseth-Lam序列(s_u)。若ord _p(2)= p-1，则有$2\in D_1^{(4)}\cup D_3^{(4)}$。由推论2、命题1和命题3可得