周期为p2的q元序列的k–错线性复杂度

吴晨煌; 许春香; 杜小妮

doi:10.11959/j.issn.1000-436x.2019230

您当前的位置：

首页 >

文章列表页 >

周期为p²的q元序列的k–错线性复杂度

学术论文 | 更新时间：2024-06-05

- 周期为p²的q元序列的k–错线性复杂度
- k-error linear complexity of q-ary sequence of period p²
- 通信学报 2019年40卷第12期页码：21-28
- 作者机构：
  
  1. 电子科技大学计算机科学与工程学院，四川成都 611731
  2. 莆田学院应用数学福建省高校重点实验室，福建莆田 351100
  3. 西北师范大学数学与统计学院，甘肃兰州730070
- 作者简介：
  
  [ "吴晨煌（1981– ），男，福建莆田人，电子科技大学博士生，莆田学院副教授，主要研究方向为序列密码" ]
  [ "许春香（1965– ），女，湖南长沙人，博士，电子科技大学教授、博士生导师，主要研究方向为信息安全、密码学及其应用。" ]
  [ "杜小妮（1972– ），女，甘肃庆阳人，博士，西北师范大学数学与统计学院信息研究所副所长、博士生导师，主要研究方向为密码学、编码理论和信息安全。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61772292);国家自然科学基金资助项目(61772022);国家自然科学基金资助项目(61872060);国家自然科学基金国际（地区）合作交流项目NSFC-RFBR(61911530130);福建省自然科学基金资助项目(2018J01425)
- DOI：10.11959/j.issn.1000-436x.2019230
  中图分类号： TP309
- 网络首发：2019-12，
  
  纸质出版：2019-12-25
- 稿件说明：
移动端阅览
吴晨煌, 许春香, 杜小妮. 周期为p²的q元序列的k–错线性复杂度[J]. 通信学报, 2019,40(12):21-28.

Chenhuang WU, Chunxiang XU, Xiaoni DU. k-error linear complexity of q-ary sequence of period p²[J]. Journal on Communications, 2019, 40(12): 21-28.
吴晨煌, 许春香, 杜小妮. 周期为p²的q元序列的k–错线性复杂度[J]. 通信学报, 2019,40(12):21-28. DOI： 10.11959/j.issn.1000-436x.2019230.

Chenhuang WU, Chunxiang XU, Xiaoni DU. k-error linear complexity of q-ary sequence of period p²[J]. Journal on Communications, 2019, 40(12): 21-28. DOI： 10.11959/j.issn.1000-436x.2019230.

摘要

基于矩阵中元素统计的方法，给出了计算周期为p2的q元序列k–错线性复杂度的新方法，其中，p

q为奇素数且q为模p2的本原元。给出了一个一般性的结论及其证明，并通过列举2类周期为p2的q元序列及其实例来验证结论的正确性。该方法不需要迭代计算，通过程序实现并与现有算法进行效率比较，结果表明所给出的新算法在计算周期为p2的q元序列的k–错线性复杂度方面效率明显更高。

Abstract

Based on element statistics in a matrix

a new efficient computing method for computing the k-error linear complexity of q-ary sequence of period p2was proposed

where p

q were odd primes and q modulo p2was primitive.A general result and a concrete proof were showed.To verify the correctness of the result

two kinds of q-ary sequence of period p2were illustrated.Because the new method does not need iterative calculation and when it is implemented by program and compared with existing algorithms

the results show that the proposed new algorithm is significantly more efficient in calculating k-error linear complexity of q-ary sequence of period p2.

关键词

Keywords

references

RUPPEL R . Analysis and design of stream ciphers [J ] . Springer-Verlag , 1986 .

CUSICK T , DING C , RENVALL A . Stream ciphers and number theory [M ] . Amsterdam : North-Holland Publishing CompanyPress , 1998 .

STAMP M , MARTIN C . An algorithm for the k-error linear complexity of binary sequences with period 2 n [J ] . IEEE Transactions on Information Theory , 1993 , 39 ( 4 ): 1389 - 1401 .

DING C , . Lower bounds on the weight complexity of cascaded binary sequences [C ] // International Conference on Cryptology,Lecture Notes in Computer Science . 1991 , 453 : 39 - 43 .

DING C , XIAO G , SHAN W . The stability theory of stream ciphers [M ] . Springer Science ＆ Business Media , 1991 .

GOLOMB S , GONG G . Signal design for good correlation:for wireless communication,cryptography,and radar [M ] . Cambridge University Press , 2005 .

BERLEKAMP E . Algebraic coding theory [M ] . New York : McGraw-HillPress , 1968 .

MASSEY J . Shift register synthesis and BCH decoding [J ] . IEEE Transactions on Information Theory , 1969 , 15 ( 1 ): 122 - 127 .

GAMES R , CHAN A . A fast algorithm for determining the complexity of a binary sequence with period 2 n [J ] . IEEE Transactions on Information Theory , 1983 , 29 ( 1 ): 144 - 146 .

MEIDL W . On the stability of 2 n -periodic binary sequences [J ] . IEEE Transactions on Information Theory , 2005 , 51 ( 3 ): 1151 - 1155 .

魏仕民 , 白国强 , 肖国镇 . 确定周期为p n 的二元周期序列的线性复杂度的一个快速算法 [J ] . 通信学报 , 1999 , 20 ( 8 ): 36 - 40 .

WEI S M , BAI G Q , XIAO G Z . A fast algorithm for determining the linear complexity of a binary sequence with period p n [J ] . Journal on Communications , 1999 , 20 ( 8 ): 36 - 40 .

王磊 , 张玉清 , 肖国镇 . 确定周期为p n 的二元序列的k-错线性复杂度的一个算法 [J ] . 通信学报 , 2001 , 22 ( 4 ): 91 - 95 .

WANG L , ZHANG Y Q , XIAO G Z . An algorithm for determining the k-error linear complexity of a binary sequence with period p n [J ] . Journal on Communications , 2001 , 22 ( 4 ): 91 - 95 .

陈智雄 , 牛志华 , 吴晨煌 . 周期为素数平方的二元序列的 k-错线性复杂度 [J ] . 密码学报 , 2019 , 6 ( 5 ): 574 - 584 .

CHEN Z X , NIU Z H , WU C H . On the k-error linear complexity of prime-square periodic binary sequences [J ] . Journal of Cryptologic Research , 2019 , 6 ( 5 ): 574 - 584 .

XIAO G , WEI S , LAM K Y , et al . A fast algorithm for determining the linear complexity of a sequence with period p n over GF(q) [J ] . IEEE Transactions on Information Theory , 2000 , 46 ( 6 ): 2203 - 2206 .

魏仕民 , 董庆宽 , 肖国镇 . 确定周期序列k-错复杂度的一个快速算法 [J ] . 西安电子科技大学学报 , 2001 , 28 ( 4 ): 421 - 424 .

WEI S M , DONG Q K , XIAO G Z . An efficient algorithm for the k-error linear complexity of periodic sequences [J ] . Journal of Xidian University , 2001 , 28 ( 4 ): 421 - 424 .

白恩健 , 刘晓娟 , 肖国镇 . 确定周期为p n 的二元序列k-错复杂度曲线的快速算法 [J ] . 通信学报 , 2004 , 25 ( 10 ): 1 - 7 .

BAI E J , LIU X J , XIAO G Z . A fast algorithm for determining k-error linear complexity profile of a binary sequence with period p n [J ] . Journal on Communications , 2004 , 25 ( 10 ): 1 - 7 .

苏明 , 符方伟 . 随机周期序列 k-错线性复杂度的期望上界 [J ] . 通信学报 , 2005 , 26 ( 2 ): 60 - 65 .

SU M , FU F W . Upper bound of expected value of the k-error linear complexity of random periodic sequences [J ] . Journal on Communications , 2005 , 26 ( 2 ): 60 - 65 .

LIDL R , NIEDERREITER H . Finite fields [M ] . Addison-Wesley , 1983 .

CHEN Z , OSTAFE A , WINTERHOF A . Structure of pseudorandom numbers derived from Fermat quotients [C ] // International Workshop on the Arithmetic of Finite Fields . Springer , 2010 , 73 - 85 .

CHEN Z , DU X . On the linear complexity of binary threshold sequences derived from Fermat quotients [J ] . Designs,Codes and Cryptography , 2013 , 67 ( 3 ): 317 - 323 .

CHEN Z . Trace representation and linear complexity of binary sequences derived from Fermat quotients [J ] . Science China Information Sciences , 2014 , 57 ( 11 ): 1 - 10 .

PARK K , SONG H , KIM D , et al . Optimal families of perfect polyphase sequences from the array structure of fermat-quotient sequences [J ] . IEEE Transactions on Information Theory , 2016 , 62 ( 2 ): 1076 - 1086 .

杜小妮 , 李芝霞 , 万韫琦 , 等 . 基于费马商的 r 元序列的迹表示 [J ] . 电子学报 , 2017 , 45 ( 10 ): 2439 - 2442 .

DU X N , LI Z X , WAN Y Q , et al . Trace representation of r-ary sequences derived from Fermat quotient [J ] . Acta Electronicas Sinica , 2017 , 45 ( 10 ): 2439 - 2442 .

浏览量

1846

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

SLCE序列的2-adic复杂度

单圈T-函数的2-adic复杂度和1-错2-adic复杂度

基于多个独立区分特征的序列密码最优联合区分器

给定线性复杂度谱的序列的条数

Klimov-Shamir T-函数的代数结构