Computing the k-error joint linear complexity of 
binary periodic multisequences

doi:10.1016/S1005-8885(13)60114-4

中国邮电高校学报(英文) ›› 2013, Vol. 20 ›› Issue (6): 96-101.doi: 10.1016/S1005-8885(13)60114-4

Computing the k-error joint linear complexity of binary periodic multisequences

李富林

School of Mathematics, Hefei University of Technology, Hefei 230009, China

收稿日期:2013-05-14 修回日期:2013-11-03 出版日期:2013-12-31 发布日期:2013-12-27
通讯作者: 李富林 E-mail:lflsxx66@163.com
基金资助:
This work was supported by the National Natural Science Foundation of China (61370089), the Fundamental Research Funds for the Central Universities (2012HGBZ0622).

Computing the k-error joint linear complexity of binary periodic multisequences

School of Mathematics, Hefei University of Technology, Hefei 230009, China

Received:2013-05-14 Revised:2013-11-03 Online:2013-12-31 Published:2013-12-27
Supported by:
This work was supported by the National Natural Science Foundation of China (61370089), the Fundamental Research Funds for the Central Universities (2012HGBZ0622).

摘要/Abstract

摘要： Complexity measures for multisequences over finite fields, such as the joint linear complexity and the k-error joint linear complexity, play an important role in cryptology. In this paper we study a fast algorithm, presented by Venkateswarlu A, to computer the k-error joint linear complexity of a binary periodic multisequence. In this paper, the aim is mainly to complement the theoretical derivation and proof of the existing algorithm. Moreover, our algorithm reduces computation.

关键词: cryptology, multisequence, algorithm, joint linear complexity, k-error joint linear complexity

Abstract: Complexity measures for multisequences over finite fields, such as the joint linear complexity and the k-error joint linear complexity, play an important role in cryptology. In this paper we study a fast algorithm, presented by Venkateswarlu A, to computer the k-error joint linear complexity of a binary periodic multisequence. In this paper, the aim is mainly to complement the theoretical derivation and proof of the existing algorithm. Moreover, our algorithm reduces computation.

Key words: cryptology, multisequence, algorithm, joint linear complexity, k-error joint linear complexity

中图分类号:

TN918.1

参考文献

1. Niederreiter H. Periodic sequences with the large k-error linear complexity. IEEE Transactions on Information Theory, 2003, 49(2): 501-505

2. Xing C P, Ding Y. Multisequences with large linear and k-error linear complexity from Hermitian function field. IEEE Transactions on Information Theory, 2009, 55(8): 3858-3863

3. Niederreiter H, Venkateswalu A. Periodic multisequences with large error linear complexity. Designs, Codes and Cryptography, 2008, 49(1/2/3): 33-45

4. Stamp M, Martin C F. An algorithm for the k-error linear complexity of binary sequences with period 2ⁿ. IEEE Transactions on Information Theory, 1993, 39(4): 1389-1401

5. Meidl W. How many bits have to be changed to decrease the linear complexity? Designs, Codes and Cryptography, 2004, 33(2): 109-122

6. Zhou J Q. On the k-error linear complexity of sequences with period over GF(q) . Designs, Codes and Cryptography, 2001, 58(3): 279-296

7. Wei S M, Xiao G Z, Chen Z. A fast algorithm for determining the linear complexity of a binary sequence with period . Science in China, 2001, 44(6): 453-460

8. Wei S M, Chen Z, Xiao G Z. A fast algorithm for the k-error linear complexity of a binary sequence. Proceedings of the 2001 International Conferences on Info-tech and Info-net (ICII’01): Vol 5, Oct 29-Nov 1, 2001, Beijing, China. Piscataway, NJ, USA: IEEE, 2001: 152-157

9. Feng G L, Tzeng K K. A generalization of the Berlekamp-Massey algorithm for multisequence shift-register synthesis with applications to decoding cyclic codes. IEEE Transactions on Information Theory, 1991, 37(5): 1274-1287

10. Wang L P, Zhu Y F, Pei D Y. On the lattice basis reduction multisequence synthesis algorithm. IEEE Transactions on Information Theory, 2004, 50(11): 2905-2910

11. Venkateswalu A. Studied on error linear complexity measures for multisequences. Ph. D Thesis. Singapore: Department of Mathematics, National University of Singapore, 2007

12. Meidl W, Niederreiter H, Venkateswarlu A. Error linear complexity mearsures for multisequences. Journal of Complexity, 2007, 23(2): 169-192

13. Lidl R, Niederreiter H. Finite fields. Reading, MA, USA: Addison-Wesley, 1993

[1]	谢佳高军涛岳曌李雪莲. Autocorrelation of two Legendre-Sidelnikov sequences[J]. Acta Metallurgica Sinica(English letters), 2014, 21(5): 83-88.
[2]	贾艳艳胡予濮赵勇斌高军涛. Correlation power analysis of DECIMv2[J]. Acta Metallurgica Sinica(English letters), 2011, 18(5): 118-123.
[3]	王艳, HU Yu-pu, LI Shun-bo, YANG Yang. Linear complexity of sequences produced by single cycle T-function[J]. Acta Metallurgica Sinica(English letters), 2011, 18(4): 123-128.
[4]	许丽卿陈豪. Some results on the algebraic immunity of Boolean functions[J]. Acta Metallurgica Sinica(English letters), 2011, 18(2): 102-105.
[5]	柯品惠张胜元. Constructions of vector output Boolean functions with high generalized nonlinearity[J]. Acta Metallurgica Sinica(English letters), 2008, 15(2): 77-81.
[6]	陈秀波;杜建忠;温巧燕;朱甫臣. Teleportation of an unknown two-particle entangled state via an asymmetric three-particle entanglement state[J]. Acta Metallurgica Sinica(English letters), 2008, 15(1): 102-105.

Computing the k-error joint linear complexity of binary periodic multisequences

Computing the k-error joint linear complexity of binary periodic multisequences

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价