计算机应用 ›› 2013, Vol. 33 ›› Issue (01): 12-14.DOI: 10.3724/SP.J.1087.2013.00012

• 第九届中国信息和通信安全学术会议(CCICS 2012)论文 • 上一篇    下一篇

计算p^n-周期二元序列的最小错线性复杂度新算法

牛志华,郭丹峰   

  1. 上海大学 计算机工程与科学学院,上海 200444
  • 收稿日期:2012-08-27 出版日期:2013-01-01 发布日期:2013-01-09
  • 通讯作者: 牛志华
  • 作者简介:牛志华(1976-),女,山西左权人,副教授,博士,CCF会员,主要研究方向:密码学;郭丹峰(1988-),女,河南洛阳人,硕士研究生,主要研究方向:密码学。
  • 基金资助:

    上海市重点学科建设项目(J50103);国家自然科学基金资助项目(40975015, 41275041);上海市教委创新基金资助项目(10YZ13)

New algorithm for computing minerror linear complexity of p^n-periodic binary sequences

NIU Zhihua,GUO Danfeng   

  1. School of Computer Engineering and Science, Shanghai University, Shanghai 200444, China
  • Received:2012-08-27 Online:2013-01-01 Published:2013-01-09
  • Contact: NIU Zhihua

摘要: 传统的计算序列k-错线性复杂度的算法,每一步都要计算和存储序列改变的代价,基于节省计算量和存储空间的考虑,提出了一种计算周期为pn的二元序列的最小错线性复杂度的新算法,其中p为素数,2为模p2的一个本原根。新算法省去了序列代价的存储和计算,主要研究在k为最小错,即使得序列线性复杂度第一次下降的k值时,序列线性复杂度的计算方法,给出了理论证明,并用穷举法与传统算法对序列的计算结果进行了比对。结果完全一致且比传统算法节省了一半以上的存储空间和计算时间,是一种有效的研究特殊周期序列稳定性的计算方法。

关键词: 流密码, 周期序列, 线性复杂度, k-错线性复杂度

Abstract: The cost of a sequence must be calculated and stored in each step by using a classical k-error linear complexity algorithm. If only considering the first drop of its linear complexity namely the minerror linear complexity, a lot of calculation and memory space could be saved. A new algorithm for computing the minerror linear complexity of pn-periodic binary sequences was proposed in this paper. Here p is an odd prime, and 2 is a primitive root (module p2). The new algorithm eliminated the storage and computation of the cost of a sequence, focused on the method of calculation of the linear complexity when k was the minerror which made the first drop of its linear complexity. Besides, theoretical proof was given. Although the new algorithm saved more than half of the storage space and computation time, the results were totally same as the classical algorithm. It is an effective algorithm on the research of sequence's stability.

Key words: stream cipher, periodic sequence, linear complexity, k-error linear complexity

中图分类号: