一个计算指数周期序列的所有跃点的算法

doi:10.3969/j.issn.0253-2778.2018.02.003

中国科学技术大学学报 ›› 2018, Vol. 48 ›› Issue (2): 105-110.DOI: 10.3969/j.issn.0253-2778.2018.02.003

一个计算指数周期序列的所有跃点的算法

唐淼，王菊香

1.安徽农业大学应用数学系, 安徽合肥 230036；2.安徽建筑大学数理学院, 安徽合肥 230601

收稿日期:2016-08-24 修回日期:2017-11-22 出版日期:2018-02-28 发布日期:2018-02-28
通讯作者: 唐淼
作者简介:唐淼(通讯作者),男,1981年生,硕士/副教授. 研究方向:编码与密码. E-mail: tangmiao@ahau.edu.cn
基金资助:
安徽省高校自然科学研究项目重点项目(KJ2017A136) , 安徽省高校优秀青年人才支持计划重点项目(gxyqZD2016032), 安徽省教育厅自然科学基金一般项目(KJ2015JD18)资助.

An algorithm for computing all the critical points of exponent periodic sequences

TANG Miao, WANG Juxiang

1. Department of Applied Mathematics, Anhui Agricultural University, Hefei 230036, China;
2. School of Mathematics and Physics, Anhui Jianzhu University, Hefei 230601, China）

Received:2016-08-24 Revised:2017-11-22 Online:2018-02-28 Published:2018-02-28

摘要/Abstract

摘要： 周期序列的k错线性复杂度是衡量流密码系统安全性能的一个重要指标，k错线性复杂度的值随着k值的增加呈下降趋势，其中发生严格下降的点称为跃点.这里关注有限域GF(pm)上的pn周期序列，p是任意素数，讨论了该类序列的k错线性复杂度的性质，同时给出了一个算法：对于任意给定的序列，计算出其包含的所有跃点.

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

Abstract: The k-error linear complexity of periodic sequences is an important security indice of stream cipher systems. The k-error linear complexity decreases as the number of errors k increases, that the critical points are those where a decrease occurs in the k-error linear complexity. The pn periodic sequences over the finite field GF(pm) were focused upon， where p is a prime. Some properties of the k-error linear complexity were discussed, and an algorithm was presented for computing all the critical points for a given sequence.

Key words: stream cipher, periodic sequence;k-error linear complexity, critical point

中图分类号:

唐淼，王菊香. 一个计算指数周期序列的所有跃点的算法[J]. 中国科学技术大学学报, 2018, 48(2): 105-110.

TANG Miao, WANG Juxiang. An algorithm for computing all the critical points of exponent periodic sequences[J]. Journal of University of Science and Technology of China, 2018, 48(2): 105-110.

参考文献

［1］
GAMES R A, CHAN A H. A fast algorithm for determining the linear complexity of a binary sequence with period 2n[J]. IEEE Transactions on Information Theory, 1983, 29(1): 144-146.
[2] DING C S, XIAO G Z, SHANW J. The Stability Theory of Stream Ciphers[M]. Berlin: Springer-Verlag, 1991: Chapter 5.
[3] STAMP M, MARTIN C F. An algorithm for the k-error linear complexity of binary sequences with period 2n[J]. IEEE Transactions on Information Theory, 1993, 39(4): 1398-1401.
[4] KAIDA T, UEHARA S, IMAMURA K. An algorithm for the k-error linear complexity of sequences over GF(pm) with period pn, p a prime[J]. Information and Computation, 1999, 151(2): 134-147.
[5] LAUDER A G B, PATERSON K G. Computing the error linear complexity spectrum of a binary sequence of period 2n[J]. IEEE Transactions on Information Theory, 2003, 49(1): 273-280.
[6] KAIDA T.On the generalized Lauder-Paterson algorithm and profiles of the k-error linear complexity for exponent periodic sequences[C]// Sequences and Their Applications - SETA 2004. Heidelberg: Springer, 2005, LNCS 3486: 166-178.
[7] KURSOSAWA K, SATO F,SAKATA T, et al. A relationship between linear complexity and k-error linear complexity[J]. IEEE Transactions on Information Theory, 2000, 46(2): 694-698.
[8] 赵耀东, 戚文峰. 二元周期序列的k错误线性复杂度[J]. 电子学报, 2005, 33(1): 12-16.
ZHAO Yaodong, QI Wenfeng. On the k-error linear complexity of binary period sequences[J]. Acta Electronica Sinica, 2005, 33(1): 12-16.
[9] MEIDL W, NIEDERREITER H. On the expected value of the linear complexity and k-error linear complexity of periodic sequences[J]. IEEE Transactions on Information Theory, 2002, 48(11): 2817-2825.
[10] MEIDL W, VENKATESWARLU A. Remarks on the k-error linear complexity of pn-periodic sequences[J]. Designs, Codes and Cryptography, 2007, 42(2): 181-193.
[11] 朱凤翔, 戚文峰.Fp上pn-周期序列的1-错线性复杂度[J]. 电子与信息学报, 2007, 29(9): 2222-2225.
ZHU Fengxiang, QI Wenfeng. 1-error linear complexity of pn-periodic sequences over Fp[J]. Journal of Electronics & Information Technology, 2007, 29(9): 2222-2225.
[12] 李鹤龄, 戚文峰.Fp上pn-周期序列的k-错线性复杂度[J]. 通信学报, 2010, 31(6): 19-24.
LI Heling, QI Wenfeng. k-error sequences of pn-periodic sequences over Fp[J]. Journal on Communications, 2010, 31(6): 19-24.
[13] CHANG Z L, KE P H. On the error linear complexity spectrum of binary sequences with period of power of two[J]. Chinese Journal of Electronics, 2015, 24(2): 366-372.
[14] TANG Miao. An algorithm for computing the error sequence of pn-periodic binary sequences[J]. Applicable Algebra in Engineering, Communication and Computing, 2014, 25(3): 197-212.
[15] 唐淼, 开晓山. 三元3n周期序列的k错线性复杂度的性质[J]. 中国科学技术大学学报, 2015, 45(2): 107-111, 116.
TANG Miao, KAI Xiaoshan. Some properties of the k-error linear complexity of ternary 3n-periodic sequences[J]. Journal of University of Science and Technology of China, 2015, 45(2): 107-111, 116.

一个计算指数周期序列的所有跃点的算法

An algorithm for computing all the critical points of exponent periodic sequences

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价