针对非线性最大长度移位寄存器反馈函数难以构造问题,本文提出了一种基于母函数构造非线性最大长度移位寄存器反馈函数方法.首先,我们阐述了母函数模3分类法,证明了各类母函数新的特征状态集,提取了母函数的特征式;其次,根据特征式对母函数的筛分特性合成了非线性m子序列移位寄存器反馈函数;最后,分析了该移位寄存器生成的伪随机序列,对其自相关值和线性复杂度进行了大量搜索.结果一致表明该序列不仅具有良好的周期特性、平衡特性、游程特性,还具有尖锐的自相关特性和理想的线性复杂度.
Abstract
To solve the problem of constructing feedback functions of non-linear maximal length shift registers (NMLSR),the method to construct the feedback functions for NMLSR was proposed based on root function.First of all,we expatiated the classification method of the root functions modulo 3,proveded the characteristic state sets of the root functions and extracted the eigenfunctions of the root functions.Secondly,we synthesized the feedback function for the nonlinear m subsequence shift register according to the filter of the eigenfunctions on the root functions.Finally,we conducted a great number of calculations and analyses for new type sequences generated from the nonlinear m subsequence shift registers.The results show unanimously that the nonlinear m subsequences dose not only possess better period property,balance property and run-path property,but also the sharp autocorrelation property and the ideal linear complexity.
关键词
非线性 /
反馈函数 /
合成 /
筛分 /
模3 /
特征式 /
伪随机序列
{{custom_keyword}} /
Key words
nonlinear /
feedback function /
synthesize /
filter /
modulo 3 /
eigenfunction /
pseudo-random sequence
{{custom_keyword}} /
中图分类号：
TN801
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Mansouri Shohreh Sharif,Dubrova Elena.An improved hardware implementation of the grain stream cipher [A].Proceedings of the 13th Euromicro Conference on Digital System Design:Architectures,Methods and Tools [C].2010.433-440.
[2] Lan Jingjing,Goh Wang Ling,Kong Zhi Hui,Yeo Kiat Seng.A random number generator for low power cryptographic application [A].Proceedings of the 2010 International SoC Design Conference [C].2010.328-331.
[3] Lvhong,et al.Design and Implementation of A Maximal Length Nonlinear Pseudorandom Sequence [A].Proceedings of the 2009 International Conference on Computer and Communications Security [C].2009,12,64-67.
[4] Kang Minsu.FPGA implementation of Gaussian-distributed pseudo-random number generator [A].Proceeding of the 6th International Conference on Digital Content,Multimedia Technology and Its Applications [C].2010.11-13.
[5] Poorghanad Alireza,Sadr Ali,Kashanipour Alireza.Generating high quality pseudo random number using evolutionary methods [A].Proceedings of the 2008 International Conference on Computational Intelligence and Security [C].2008.331-335.
[6] Chang Shih Yu,Wu Hsiao-Chun,Pang Ai-Chun.Theoretical exploration of pattern attributes for maximum-length shift-register sequences [A].Proceedings of the 2009 ACM International Wireless Communications and Mobile Computing Conference [C].2009.1116-1120.
[7] 吕虹,段颖妮,管必聪.一种非线性最大长度伪随机序列发生器的设计[J].电子器件,2008,31(3):898-900.
[8] 肖国镇,梁传甲,王育民.伪随机序列及其应用[M].北京:国防工业出版社,1985.124-145.
[9] 常祖领,柯品惠,温巧燕.高非线性度多输出布尔函数的构造[J].电子学报,2008,36 (1):141-145. CHANG Zu-ling,KE Pin-hui,et al.Constructions of multi-output boolean functions with high nonlinearity[J].Acta Electronica Sinica,2008,36(1):141-145.(in Chinese)
[10] 刁哲军,陈嘉兴,刘志华.一种具有大线性复杂度伪随机序列的构造[J].电子学报,2008,36(10):1961-1965. DIAO Zhe-jun,CHEN Jia-xing,LIU Zhi-hua.A new design for pseudorandom sequences with large linear span[J].Acta Electronica Sinica,2008,36(10):1961-1965.(in Chinese)
[11] Chang,P Gaal,S W Golomb,G Gong,T Helleseth,P V Kumar.On a conjectured ideal autocorrelation sequence and a related triple error correcting cyclic code[J].IEEE Trans Inform Theory,2000,46(2):680-687.
[12] Marchi A,Liverani A,Del Giudice A.Polynomial pseudo-random number generator via cyclic phase [J].Mathematics and Computers in Simulation,2009,79(11):3328-3338.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金 (No.61071001)
{{custom_fund}}
PDF(1151 KB)
