柯品惠, 卢栎羽, 陈智雄

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] 中两类二元序……