k-error linear complexity of q-ary sequence of period p2

Chenhuang WU; Chunxiang XU; Xiaoni DU

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

您当前的位置：

首页 >

文章列表页 >

k-error linear complexity of q-ary sequence of period p²

Papers | 更新时间：2024-06-05

- k-error linear complexity of q-ary sequence of period p²
- Journal on Communications Vol. 40, Issue 12, Pages: 21-28(2019)
- 作者机构：
  
  1. 电子科技大学计算机科学与工程学院，四川成都 611731
  2. 莆田学院应用数学福建省高校重点实验室，福建莆田 351100
  3. 西北师范大学数学与统计学院，甘肃兰州730070
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(61772292);The National Natural Science Foundation of China(61772022);The National Natural Science Foundation of China(61872060);Projects of International Cooperation and Exchanges NSFC(61911530130);The Natural Science Foundation of Fujian Province(2018J01425)
- DOI：10.11959/j.issn.1000-436x.2019230
  CLC： TP309
- Online First：2019-12，
  
  Published：25 December 2019
- 稿件说明：
移动端阅览
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：

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 .

Views

1846

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

2-adic complexity of SLCE sequence

The 2-adic complexity and the 1-error 2-adic complexity of single cycle T-functions

Optimal combined distinguisher of stream cipher with multiple independent distinguishing characters

Number of sequences with given linear complexity profiles

On the algebraic structure of Klimov-Shamir T-function

Related Author

Yan WANG

Shunbo LI

Gaina XUE

Wei YOU

Wen-feng QI

Hai-ying GAO

Chen-hui JIN

LIU Xun-shou

Related Institution

School of Science,Xi’ an University of Architecture and Technology,Xi’ an

National Digital Switching System Engineering ＆ Technological Research Center

Fourth Institute,PLA Information Engineering University

State Key Laboratory of Mathematical Engineering and Advanced Computing, PLA Information Engineering University

Electronic Technology Institute,PLA Information Engineering University

AI问答

⁰