一类长度为2p2 的二元序列的2-Adic 复杂度研究*

柯品惠, 卢栎羽, 陈智雄

1. 福建师范大学 数学与统计学院, 福州350117

2. 福建省应用数学中心(福建师范大学), 福州350117

3. 莆田学院 应用数学福建省高校重点实验室, 莆田351100

1 引言

伪随机序列在通信和密码学等领域具有广泛的应用[1]. 理论上, 每个二元序列都可以由线性反馈移位寄存器(LFSR) 或带进位反馈移位寄存器(FSCR) 产生. Berlekam-Massey 算法(BMA)[2]和有理逼近算法(RAA)[3]是目前较为有效的两种攻击算法, 如果已知一定长度的二元序列, 那么可利用上述两种算法来恢复完整的二元序列. 线性复杂度和2-adic 复杂度是抵御BMA 和RAA 攻击的两个重要安全准则. 由BMA 和RAA 攻击方式可知, 序列的线性复杂度和2-adic 复杂度都不应小于该序列周期的一半.目前, 许多分圆序列和广义分圆序列已被证明具有较高的线性复杂度[4–7]. 然而, 对于序列的2-adic 复杂度, 仅有少数几类序列的2-adic 复杂度是已知的. 因此, 分析已有序列的2-adic 复杂度以及设计具有高2-adic 复杂度的伪随机序列成为近年研究的热点.

迄今为止, 计算二元序列的2-adic 复杂度主要有三种方法. 第一种方法是Xiong 等[8]提出的计算序列的循环矩阵的行列式和两个整数的最大公约数. 在文献[8] 中, Xiong 等证明了所有具有理想自相关值的序列都具有最大的2-adic 复杂度. 之后, Xiao 等[9]利用相同的方法证明了两类广义分圆二元序列的2-adic 复杂度可达到最大值. 第二种方法是Hu[10]提出的利用序列的自相关分布来分析二元序列的2-adic 复杂度. 基于文献[10] 的研究方法, Sun 等分别给出了文献[11] 和文献[12] 中两类二元序列的2-adic 复杂度的下界, 并且得到了文献[13] 中Ding-Helleseth-Lam 序列的2-adic 复杂度的上下界. 最近,Hofer 和Winterhof[14]用文献[10] 的方法证明了二素数生成器(two-prime generater) 的2-adic 复杂度接近于它的周期. 最后一种方法是直接计算序列的2-adic 复杂度. 例如, Zhang 等[15]利用有限域Fq和Z2N −1上的“高斯周期”和“二次高斯和”确定了Ding-Helleseth-Martinsen 序列的2-adic 复杂度. Yang等[16]推广了文献[13] 中给出的结果, 并确定了一类二元序列的2-adic 复杂度的精确值.

最近, Zhang 等[17]构造了一类长度为2p2的二元广义分圆序列, 证明了此类二元序列具有较大的线性复杂度. 基于文献[8] 给出的方法, 本文研究了此类二元广义分圆序列的2-adic 复杂度. 我们证明了此类序列的2-adic 复杂度不小于其周期的一半, 并且该序列的2-adic 复杂度在一些情形下也可以达到最大值.

本文其余部分组织如下. 第2 节, 给出本文所需要的相关概念与知识, 以及一些必要的结果. 第3 节,首先, 利用中国剩余定理和Zp上的“高斯周期” 得到了Z2p2上的“高斯周期”; 然后, 证明了一类长度为2p2的二元序列的2-adic 复杂度在一些情形下可以达到最大值. 第4 节对本文工作进行总结.

2 基础知识

令p为奇素数. 设2 为模p2的本原根, 当k ≥1 时, 则2 也是模pk的本原根[18]. 由于2+pk为奇数, 则2+pk为模2pk的本原根[19]. 设g=2+p2, 则g是模p,2p,p2和2p2的公共本原根.

定义

上述引理1—4的证明, 请参见文献[20].

引理5 令p为奇素数, 则有gcd(p,2p2−1)=1.

证明: 由费马小定理, 可得2p ≡2 modp. 于是, 有2p2≡(2p)p ≡2p ≡2 modp, 即2p2−1≡1 modp. 所以gcd(p,2p2−1)=1.

引理6 (i) 令p为奇素数, 则有gcd(p −1,2p2−1) = 1; (ii) 令p为奇素数且p ̸≡1 mod 3, 则有gcd(p −1,2p2+1)=1.

证明: (i) 设r为2p2−1 的素因子, ordr2 为2 模r的乘法阶, 则有2p2≡1 modr和ordr2|p2. 又p为奇素数且ordr2̸= 1. 因此, ordr2 =p或ordr2 =p2. 此外, 因为r为素数, 故ordr2|(r −1). 于是,r −1 是p的偶数倍, 2p2−1 的每个因子必须具有2kp+1 的形式. 因此, gcd(p −1,2p2−1)=1.

(ii) 设r为2p2+1 的素因子, 有2p2≡−1 modr, 则22p2≡1 modr. 令ordr2 为2 模r的乘法阶,由于2p2≡−1 modr, 则ordr2 = 2,2p或ordr2 = 2p2. 若ordr2 = 2, 则r= 3. 由假设可知,r= 3 不可能为p −1 的一个因子. 对于剩余的ordr2=2p或2p2的情形, 正如我们在(i) 中所述, 可以类似证明r不可能是p −1 的因子.

引理7 设p>3 为奇素数,

(i) 若p ≡−3 mod 8 且p ̸≡5 mod 24, 或者p ≡3 mod 8, 则gcd(p2+p+1,2p2−1)=1;

(ii) 若p ≡±3 mod 8, 则gcd(p2+p+1,2p2+1)=1 or 3.

注1 借助计算机,可以验证对不超过105的所有素数p,引理7 都是成立的. 具体地,对于所有素数p,1

3 主要结果

本节我们将首先回顾二元序列的2-adic 复杂度的有关概念. 然后, 利用中国剩余定理(Chinese Reminder Theorem, CRT) 和Zp上的“高斯周期” 得到了Z2p2上的“高斯周期”. 作为本文的主要结果, 我们将基于文献[8] 提出的计算方法分析式(1)中定义的序列的2-adic 复杂度.

由2-adic 复杂度的定义可知, 确定gcd(2N −1,S(2)) 是得到序列2-adic 复杂度的关键步骤. 在给定的条件下, Xiong 等[8]证明了该问题可以转化为计算给定序列相关的循环矩阵A的行列式, 并确定gcd(det(A),2N −1).

引理8[8]设s是周期为N的二元序列,A=(ak,j)N×N是Z 上的矩阵, 其中ak,j=s(k−j)modN.若det(A)̸=0, 则存在u(x),v(x)∈Z[x] 使得

由引理8,gcd(S(2),2N −1)是gcd(det(A),2N −1)的一个因子. 特别地,若gcd(det(A),2N −1)=1,则gcd(S(2),2N −1)=1. 此时序列s的2-adic 复杂度达到最大值log2(2N −1).

引理9[8]设s是周期为N的二元序列,A=(ak,j)N×N是Z 上的矩阵, 其中ak,j=s(k−j)modN,则

引理11[9]令符号定义如上, 则

当i=0,1 时, 我们需要确定ηi和βi的值. 由于p为奇素数, 由中国剩余定理可知, Z2p与Z∗2×Z∗p是同构的. 于是, 定义同构映射如下

因此,

进而,

因此,

进而,

类似地, 若p ≡±3 mod 8, 则β1=−γ0. 综上所述, 我们有以下引理.

引理12 令符号定义如上, 则有

这里S(·) 为式(1)定义的序列所对应的序列多项式.

证明: 我们将引理13 的证明分为以下几种情形.

综合上述情形, 得证.

引理14 沿用与前面相同的符号, 若p ≡±3 mod 8, 则有

证明: 由于该证明与引理13 的证明类似, 故省略.

定理1 设s是定义在式(1)中的周期为N=2p2(p>3) 的广义分圆二元序列. 若p ≡±1 mod 8, 则序列s的2-adic 复杂度为

若p ≡±3 mod 8 以及p ̸≡5 mod 24, 则序列s的2-adic 复杂度下界为

若p ≡5 mod 24, 则序列s的2-adic 复杂度下界为

此外, 若p ≡11 mod 24, 则序列s的2-adic 复杂度可以达到最大值.

证明: 根据p的取值, 下面分两种情况进行讨论.

情形1: 若p ≡±1 mod 8, 由引理8 和引理13, 可得

进而,

情形2: 若p ≡±3 mod 8, 由引理8 和引理14, 可得

由于p为素数且p>3, 可得2p2≡2 modp, 所以2p2+1≡3 modp. 于是gcd(p,2p2+1)=1.

若p ≡±3 mod 8 以及p ̸≡5 mod 24, 由引理5, 引理6 和引理7, 可知gcd(det(A),2p2−1) = 1. 因此,

若p ≡11 mod 24, 则由中国剩余定理可知,p ≡3 mod 8 和p ≡2 mod 3. 再由引理7(ii) 中的证明可知, 3 不可能是p2+p+1 的因子. 于是, 由引理6 和引理7, 可得gcd(det(A),2p2±1)=1. 因此,

4 结论

本文研究了一类具有高线性复杂度的二元广义分圆序列的2-adic 复杂度. 利用Xiong 等[8]给出的计算方法以及数论相关知识, 证明了在一些条件下, 此类序列的2-adic 复杂度可以达到最大. 我们的结果表明了此类序列的2-adic 复杂度不小于其周期的一半, 即此类序列同时具有高的2-adic 复杂度. 因此, 可以有效抵抗有理逼近算法的攻击.