离散傅里叶变换在序列线性复杂度快速算法中的应用

利用广义离散傅里叶变换对GF（2）上周期为n2∧υ(gcd(n,2)=1)序列进行了研究，给出了求其周期为n2∧υ序列线性复杂度的快速算法，并得到了关于F[D]上多项式的Hasse导数一些新结果。     

pn-周期二元序列的线性复杂度与k-错线性复杂度

密码学意义上强的序列不仅应该具有足够高的线性复杂度,而且当少量比特发生变化时不会引起线性复杂度的急剧下降,即具有足够高的k-错线性复杂度．基于x^pn-1在GF(2)上的分解式非常明确和简单的事实,研究了周期为pⁿ的二元序列线性复杂度和k-错线性复杂度之间的关系,给出了k-错线性复杂度严格小于线性复杂度的一个充分必要条件,给出了使得LC(S+E)＜LC(S)成立的用错误多项式E^N(x)表达的一个充分条件,给出了使得LC_k(S)＜LC(S)成立的最小的k值(即最小错误minerror(S))的一个上界,这里p为奇素数,z是模p的本原根．     

特殊周期序列K-错线性复杂度的快速算法

给出一个特殊周期序列GF（3）上周期为3pm的序列的K-错线性复杂度的快速算法,并讨论了它的正确性.其中p为素数,而且3是模p2的本原根.     

求GF(3)上周期为3npm序列线性复杂度的快速算法

提出和证明了求周期为3npm的GF(3)上序列的线性复杂度和极小多项式的一个快速算法,这里p为素数,且3是模p2的本原根.该算法推广了求周期为pm的二元周期序列的线性复杂度的一个快速算法.     

关于周期序列的线性复杂度

提出了在特征为p的有限域上,周期为N=nm^v(p为素数,且gcd(n,p)=1的序列的线性复杂度可由（1－^nN)的不同约分解中因子的次数及在s^N(x)以序列的前N个数字作为系数而构成的多项式）中的重数来确定,讨论了Hasse导数与序列的线性复杂度的关系,在此基础之上,给出了Games-Chan算法的另外一种推导。     

确定周期为pn的q元序列k-错复杂度曲线的一个快速算法

k-错复杂度是指改变序列一个周期段中k个或少于k个符号后所得到的序列的最小线性复杂度,k-错复杂度曲线即为该序列的k-错复杂度序列,该指标完全反映了当序列改变的比特数目不断增加时线性复杂度的变化情况．文中给出了一个确定周期为pⁿ的q元周期序列k-错复杂度曲线的算法,这里p,q为奇素数,并且q是模p的一个本原根．该算法分别推广了肖-魏-林等人计算q元pⁿ周期序列线性复杂度和魏-董-肖计算q元pⁿ周期序列k-错复杂度的算法．采用文中的算法计算q元pⁿ周期序列的k-错复杂度曲线至多需要Θ(2ⁿ⁺¹)步运算.     

广义Stamp-Martin算法

给出了求ＧＦ（ｐ）上（ｐ：素数）周期为Ｎ＝ｐ＾ｎ的ｐ元序列的ｋ－错线性复杂度的快速算法。根据Ｇｅｎｅｒａｌｉｚｅｄ Ｇａｍｅｓ－Ｃｈａｎ算法,得到了算法中求ｂ（ｊ）的一个新的方法,把求ＧＦ（２）上周期为２＾ｎ的２元序列ｋ－错线性复杂度的快速算法推广到ＧＦ（ｐ）（ｐ：素数）上周期为ｐ＾ｎ的ｐ元序列上。     

线性划分问题的一个改进算法

给定一个由n个非负数构成的序列X={x1, x2, …, xn}及正整数k≤n, 线性划分问题要求将该序列划分为不大于k段子序列,使得最小化各段子序列元素之和为最大值。目前已知该问题的最好算法是时间复杂度为O(kn2)和空间复杂度为O(kn)的动态规划算法。利用非负数序列的性质,给出一个快速改进算法,其时间复杂度为O(knlogn),空间复杂度为O(n)。     

q上qpn周期序列的线性复杂度与k错线性复杂度

研究了有限域WTHXFWTBXq上qmpn周期序列的k错线性复杂度, 给出了使其k错线性复杂度严格小于其线性复杂度的最小k值的上下界, 其中p为奇素数,q为模p2的原根, n为正整数,m为非负整数。     

Fq上q^mp^n-周期序列的线性复杂度与k-错线性复杂度

研究了有限域Fq上q^mp^n-周期序列的k-错线性复杂度,给出了使其k-错线性复杂度严格小于其线性复杂度的最小k值的上下界,其中p为奇素数,q为模p2的原根,n为正整数,m为非负整数。     

GF（3）上周期为3^nP^m序列的k错线性复杂度

周期序列的k错线性复杂度（k-Lc）被定义为改变周期序列中至多k（0≤k≤N）位后,得到所有序列线性复杂度中最小线性复杂度。m（s）表示一个序列的k-LC严格小于线性复杂度的最小k值。讨论了上周期为3^nP^m序列的k错线性复杂度,这里p是奇素数,并且3是一个模P^2的本原根,进一步讨论了序列线性复杂度和m（s）之间的关系。     

确定周期序列k—错线性复杂度的一个快速算法

给出GF（q)上确定周期为p^n的序列k-错线性复杂度的一个快速算法,这里p和q是素数,并且q是一个模p^2的本原根,算法推广了由肖,魏,林和Imamura提出了算法。     

一类大集合p元低相关序列集的线性复杂度研究

构造具有大线性复杂度和大集合容量的p元低相关序列集对码分多址(CDMA)通信系统具有重要的意义。采用Klapper的方法,利用d-型函数,构造了一类具有大集合容量的p元低相关序列集S(r)。该序列集的集合容量为p2n,序列的周期为pn-1,相关函数的最大边峰值为4p(n)/(2)-1。利用Key的方法,证明了当p=3或p=5该序列集的最小和最大线性复杂度分别为2(n)/(2)-2n和3(n)/(2)-1×2(n)/(2)-2n;而当p>5时,证明了其线性复杂度的最大和最小值分别大于3(n)/(4)-1×2(n)/(4)-2n和2(n)/(4)-2n。该序列集能极大地提高CDMA通信系统的安全性。     

快速Mersenne变换的新算法及在卷积中的应用

设p是素数,q=2^p-1是一个Mersenne素数,N=2^p＋1．证明了复数域上离散傅里叶变换（DFT）的Moshe和Hertz算法对有限域Fq2上的Mersenne变换（Mersenne变换简记为MT,其逆变换记为IMT）有类似的算法,即证明可通过计算一个N点复整数序列的MT,同时得出一个N点整数序列的MT和另一个N点整数序列的MT的IMT．故得到一个计算整数序列卷积的新算法,可有效减少计算量,能用于信号分析中的某些卷积计算．