计算有限域GF(q)上2p^n-周期序列的k-错线性复杂度及其错误序列的算法  

Algorithm for Computing the k-error Linear Complexity and the Corresponding Error Sequence of 2p^n-periodic Sequences over GF(q)

作　　者：牛志华[1,2] 孔得宇 NIU Zhihua;KONG Deyu(School of Computer Engineering and Science, Shanghai University, Shanghai 200444, China;Shanghai Institute for Advanced Communication and Data Science, Shanghai University, Shanghai 200444, China)

机构地区：[1]上海大学计算机工程与科学学院,上海200444 [2]上海大学先进研究院,上海200444

出　　处：《电子与信息学报》2018年第7期1723-1730,共8页Journal of Electronics & Information Technology

基　　金：上海市自然科学基金(16ZR1411200;17ZR1409800);国家自然科学基金(61772022;61572309;61462077)~~

摘　　要：序列的k-错线性复杂度是序列线性复杂度稳定性的重要评价指标。在求得一个序列k-错线性复杂度的同时,也需要求出是哪些位置的改变导致了序列线性复杂度的下降。该文提出一个在GF(q)上计算2p^n-周期序列s的k-错线性复杂度以及对应的错误序列e的算法,这里p和q是素数,且q是一个模2p的本原根。该文设计了一个追踪代价向量的trace函数,算法通过trace函数追踪最小的代价向量来求出对应的错误序列e,算法得到的序列e使得(s+e)的线性复杂度达到k-错线性复杂度的值。The k -error linear complexity of a sequence is a fundamental concept for assessing the stability of the linear complexity. After computing the k -error linear complexity of a sequence, those bits that make the linear complexity reduced also need to be computed. For 2pn -periodic sequence over GF（q）, where p and q are odd primes and q is a primitive root modulo p2, an algorithm is presented, which not only computes the k-error linear complexity of a sequence s but also gets the corresponding error sequence e. A function is designed to trace the vector cost called ＂trace function＂, so the error sequence e can be computed by calling the ＂trace function＂, and the linear complexity of （s ＋ e） reaches the k-error linear complexity of the sequence s.

关 键 词：密码学 周期序列 线性复杂度 K-错线性复杂度 错误序列 

分 类 号：TN918.1[电子电信—通信与信息系统]