基于模2pm的欧拉商的二元序列的线性复杂度

杜小妮; 李丽; 张福军

doi:10.11999/JEIT190071

基于模2p^m的欧拉商的二元序列的线性复杂度

doi: 10.11999/JEIT190071

西北师范大学数学与统计学院兰州 730070

基金项目: 国家自然科学基金(61462077, 61562077, 61772022)，上海市自然科学基金(16ZR1411200)

详细信息

作者简介:
杜小妮：女，1972年生，教授，博士生导师，研究方向为密码学与信息安全

李丽：女，1991年生，硕士生，研究方向为密码学与信息安全

张福军：男，1995年生，硕士生，研究方向为密码学与信息安全

通讯作者:
李丽　ymxlili36@126.com

中图分类号: TN918.4
计量
- 文章访问数: 2405
- HTML全文浏览量: 984
- PDF下载量: 66
- 被引次数: 0
出版历程
- 收稿日期: 2019-01-24
- 修回日期: 2019-06-20
- 网络出版日期: 2019-07-09
- 刊出日期: 2019-12-01

Linear Complexity of Binary Sequences Derived from Euler Quotients Modulo 2p^m

College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China

Funds: The National Natural Science Foundation of China (61462077, 61562077, 61772022), The Shanghai Municipal Natural Science Foundation (16ZR1411200)

摘要

摘要: 基于欧拉商模奇素数幂构造的伪随机序列均具有良好的密码学性质。该文根据剩余类环理论，利用模$2{p^m}$($p$为奇素数，整数$m \ge 1$)的欧拉商构造了一类周期为$2{p^{m + 1}}$的二元序列，并在${2^{p - 1}}\not \equiv 1 ({od}\,{p^2})$的条件下借助有限域${F_2}$上确定多项式根的方法，给出了序列的线性复杂度。结果表明，序列的线性复杂度取值为$2({p^{m + 1}} - p)$或$2({p^{m + 1}} - 1)$不小于其周期的1/2，能够抵抗Berlekamp-Massey(B-M)算法的攻击，是密码学意义上性质良好的伪随机序列。
- 有限域 /
- 二元序列 /
- 欧拉商 /
- 线性复杂度 /
- 极小多项式
Abstract: Families of pseudorandom sequences derived from Euler quotients modulo odd prime power possess sound cryptographic properties. In this paper, according to the theory of residue class ring, a new classes of binary sequences with period $2{p^{m + 1}}$ is constructed using Euler quotients modulo $2{p^m},$ where $p$ is an odd prime and integer $m \ge 1.$ Under the condition of ${2^{p - 1}}\not \equiv 1 ({od}\,{p^2})$, the linear complexity of the sequence is examined with the method of determining the roots of polynomial over finite field ${F_2}$. The results show that the linear complexity of the sequence takes the value $2({p^{m + 1}} - p)$ or $2({p^{m + 1}} - 1)$, which is larger than half of its period and can resist the attack of Berlekamp-Massey (B-M) algorithm. It is a good sequence from the viewpoint of cryptography.
- Finite fields /
- Binary sequences /
- Euler quotients /
- Linear complexity /
- Minimal polynomial

HTML全文

参考文献(16)

DING Cunsheng, XIAO Guozhen, and SHAN Weijuan. The Stability Theory of Stream Ciphers[M]. Berlin, Heidelberg: Springer-Verlag, 1991: 251–321.

GOLOMB S W and GONG Guang. Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar[M]. Cambridge, UK: Cambridge University Press, 2005: 174–175.

SU Wei, YANG Yang, ZHOU Zhengchun, et al. New quaternary sequences of even length with optimal auto-correlation[J]. Science China Information Sciences, 2018, 61(2): 022308. doi: 10.1007/s11432-016-9087-2

DAI Zongduo, GONG Guang, and SONG H Y. A trace representation of binary Jacobi sequences[J]. Discrete Mathematics, 2009, 309(6): 1517–1527. doi: 10.1016/j.disc.2008.02.024

CHEN Zhixiong. Linear complexity of Legendre-polynomial quotients[J]. IET Information Security, 2018, 12(5): 414–418. doi: 10.1049/iet-ifs.2017.0307

李瑞芳, 柯品惠. 一类新的周期为2pq的二元广义分圆序列的线性复杂度[J]. 电子与信息学报, 2014, 36(3): 650–654. doi: 10.3724/SP.J.1146.2013.00751

LI Ruifang and KE Pinhui. The linear complexity of a new class of generalized cyclotomic sequences with period 2pq[J]. Journal of Electronics &Information Technology, 2014, 36(3): 650–654. doi: 10.3724/SP.J.1146.2013.00751

杜小妮, 王国辉, 魏万银. 周期为2p²的四阶二元广义分圆序列的线性复杂度[J]. 电子与信息学报, 2015, 37(10): 2490–2494.

DU Xiaoni, WANG Guohui, and WEI Wanyin. Linear complexity of binary generalized cyclotomic sequences of order four with period 2p²[J]. Journal of Electronics &Information Technology, 2015, 37(10): 2490–2494.

杜小妮, 赵丽萍, 王莲花. Z₄上周期为2p²的四元广义分圆序列的线性复杂度[J]. 电子与信息学报, 2018, 40(12): 2992–2997. doi: 10.11999/JEIT180189

DU Xiaoni, ZHAO Liping, and WANG Lianhua. Linear complexity of quaternary sequences over Z₄ derived from generalized cyclotomic classes modulo 2p²[J]. Journal of Electronics &Information Technology, 2018, 40(12): 2992–2997. doi: 10.11999/JEIT180189

EDEMSKIY V, LI Chunlei, ZENG Xiangyong, et al. The linear complexity of generalized cyclotomic binary sequences of period p ⁿ[J]. Designs, Codes and Cryptography, 2019, 87(5): 1183–1197. doi: 10.1007/s10623-018-0513-2

CHEN Zhixiong and DU Xiaoni. On the linear complexity of binary threshold sequences derived from Fermat quotients[J]. Designs, Codes and Cryptography, 2013, 67(3): 317–323. doi: 10.1007/s10623-012-9608-3

CHEN Zhixiong and WINTERHOF A. On the distribution of pseudorandom numbers and vectors derived from Euler-Fermat quotients[J]. International Journal of Number Theory, 2012, 8(3): 631–641. doi: 10.1142/S1793042112500352

DU Xiaoni, KLAPPER A, and CHEN Zhixiong. Linear complexity of pseudorandom sequences generated by Fermat quotients and their generalizations[J]. Information Processing Letters, 2012, 112(6): 233–237. doi: 10.1016/j.ipl.2011.11.017

DU Xiaoni, CHEN Zhixiong, and HU Lei. Linear complexity of binary sequences derived from Euler quotients with prime-power modulus[J]. Information Processing Letters, 2012, 112(14/15): 604–609. doi: 10.1016/j.ipl.2012.04.011

WU Chenhuang, CHEN Zhixiong, and DU Xiaoni. Binary threshold sequences derived from Carmichael quotients with even numbers modulus[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2012, E95.A(7): 1197–1199. doi: 10.1587/transfun.E95.A.1197

ZHANG Jingwei and ZHAO Changan. Linear complexity and trace presentation of sequences with period 2p²[C]. 2018 IEEE International Symposium on Information Theory, Vail, USA, 2018: 2206–2210. doi: 10.1109/ISIT.2018.8437917.

AGOH T, DILCHER K, and SKULA L. Fermat quotients for composite moduli[J]. Journal of Number Theory, 1997, 66(1): 29–50. doi: 10.1006/jnth.1997.2162

施引文献

资源附件(0)

访问统计