利用矩阵搜索求所有最长公共子序列的算法

利用动态规划法求出二维数组的情况下,使用矩阵搜索的方法求出所有分支,从而求出所有最长公共子序列的算法．该算法将通常认为的指数量级的时间复杂度降低到了max{O（cmn）,O（ck）}．随后对此算法的正确性以及效率做了证明．     

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

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

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

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

2n周期平衡二元序列的6-错线性复杂度

该文针对线性复杂度和k-错线性复杂度是度量密钥流序列的密码强度的重要指标.周期序列的k-错线性复杂度就是在其一个周期改变至多k比特后所得到的线性复杂度最小值.基于Games-Chan算法,讨论了线性复杂度小于2n的2n-周期二元序列的6-错线性复杂度分布情况,给出了对应6-错线性复杂度为2n-2,2n-3和2n-3+1...     

m子序列的特性研究

针对m序列线性复杂度不高,非线性度为零等问题,采用B-M算法对构造出的第一类m子序列进行了线性复杂度的研究,得出m子序列的线性复杂度和m序列相比大的多,逼近序列长度的一半的结论。利用Walsh频谱技术分析了m子序列的非线性度,仿真和计算结果表明m子序列的非线性度与m序列相比有了很大的改善,可以广泛用于流密码、信道编码、扩频通信等领域。     

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

提出和证明了求GF(p^m)上周期为kn的序列线性复杂度和极小多项式的一个快速算法, 其中p是素数, gcd(n, p^m-1)=1且p^m-1=kt, n,k与t均为正整数．该算法推广了陈豪提出的求GF(p^m)上周期为3n的序列线性复杂度的一个快速算法, 其中p是素数, gcd(n, p^m-1)=1且p-1=3t, n与t均为正整数．结合一些已知的快速算法, 可以快速计算GF(p^m)上周期为kn的序列线性复杂度, 最后给出一个具体例子．     

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）之间的关系。     

一种变步长趋势子序列搜索算法

为了克服基于点距离的时间序列相似性搜索物理概念模糊和速度慢的缺点,提出时间序列的分段趋势序列(PTS)概念,并在此基础上提出一种变步长趋势子序列搜索算法.该算法基于时间序列分段线性表示理论,通过相似阈值和子序列间的趋势距离计算跳跃步长,从跳跃步长后开始的子序列进行下一次匹配,从而对全序列实现跳跃式搜索.理论分析和仿真结果表明,该算法对基于趋势表示的子序列搜索在时间和空间上都具有更优的性能,适用于时间序列的动态特征分析.     

pn 周期序列3错线性复杂度原序列计数公式

k错线性复杂度作为密钥流序列稳定性的重要指标,对于衡量密钥流序列密码强度具有十分重要的意义,研究具有高k错线性复杂度的序列也一直是序列密码中的热点问题。该文在XWLI算法基础上,给出k错线性复杂度小于等于pn-1时pn周期二元序列的3错线性复杂度的原序列计数公式,并通过实例验证了该文理论的正确性和合理性,该文方法同样适用于研究pn 周期q元序列的计数。     

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的本原根．     

一种快速构造降次函数的新算法

基于密码函数分拆的思想提出了一种快速有效构造降次函数g的新算法．该算法通过每次选取不同变量进行分拆,在函数分解[k/2]次后建立方程组,最后通过求解此方程组得到满足条件的降次函数g．新算法可以求解代数次数至多为[k/2」的降次函数g,使得函数f*g的代数次数至多为[k/2]．该算法计算复杂度为O(2^k/2)^w+2,在k较大时,小于已有算法的计算复杂度O((2^k-1)^w)．结果表明,在很低的计算复杂度下,能快速构造出降次函数g．     

2n周期优秀二元序列生成及其特性分析简

The 2ⁿ-periodic binary sequence with high linear complexity and high k-error linear complexity is defined as an excellent sequence. We design a genetic algorithm for generating excellent sequences and studying their features. Choosing the N-periodic binary sequences, where N=8, 16, 32, k=N/4, we search the resulted sequences by the genetic algorithm with various parameters, and compute the linear complexity profiles of results sequences by using the Lauder-Paterson algorithm, to confirm that the obtained sequences are the real excellent sequences. By numerous experiments, we speculate that the k-error linear complexity of the N-periodic binary excellent sequence meets the formula LC_k(S)≤N-2k+1, when k=N/4、N/8 (we also do experiments on sequences with periods 64, 128 and 256). By the brute-force method we obtain that the proportion of the excellent sequence in all binary sequences of the same period is 1/4.     

基于矩阵运算的Ad hoc网络容量快速估计算法

采用定向天线的传输模式下,当信道带宽和端到端时延同时受到限制时,讨论了ad hoc网络容量的估计问题,提出了1种基于矩阵运算的网络容量快速估计算法,MCMFCA（写出全称）该算法与BFSA比较,前者的时间复杂度为0（N2/K）,后者的为0{[N/（K+1）]K},MCMFCA算法更能够跟踪网络拓扑的变化。     

一种新的静态波长路由算法及其统计修正

基于部分长路由优先的原则,提出了一种新的静态波长路由算法,并利用统计修正的方法进行了数值仿真,仿真结果表明与原有算法相比,新算法能以更高的概率获得更少的波长数,简单、快速,性能更优。     

标准模型下的格基数字签名方案

为了改进盆景树(Bonsai trees)格基签名方案的实现效率,提出了一个新的格基数字签名方案.在标准模型下,该方案的存在性不可伪造性是基于格上小整数解问题(SIS)的困难性.作为Bonsai trees签名的一个改进方案,改进方案的公钥长度由Bonsai trees签名的(2k+1)mnlogq比特缩减为(k+1)mnlogq比特,同时消息的签名长度也由原Bonsai trees签名的(k+1)mlogq比特缩减到(1+k/2)mlogq比特,能更好地实现签名方案的效率.     

减少反馈策略和联合编码策略下的多播资源分配

针对传统的多播策略中,系统吞吐量受限于多播组中最差用户的信道增益的问题,提出一种基于减少反馈策略和联合编码策略下的多播资源分配算法.采用分层编码与里所(RS)码的联合编码策略,进行数据的分层和补偿丢失的数据包.对传输的不同层的数据采用不同的反馈策略来降低上行反馈负载,并且将资源分配问题建模为最优化问题,为了减轻计算复杂度,又提出了次优化的能保证多播组服务质量的比例公平子载波分配算法与注水功率分配算法(WF-Q).为进一步降低复杂度,采用新的增加固定功率的分配算法(IFP-Q).仿真结果表明,提出的反馈策略明显减少了上行反馈负载,并且联合的编码策略能进一步提高系统性能.     

无人值守传感器网络的高性能分布式存储算法

为解决无人值守传感器网络的数据存储可靠性问题,提出了一种具有低通信成本和低访问成本的分布式存储算法．算法采用步数为cn的并行定向随机游走机制,将网络中的k个源数据包按照一定的接收概率分散存储到网络中所有的n个节点,在每个节点形成一个存储数据包．理论分析和实验结果表明,基于该算法的存储过程完成之后,即使有部分传感器节点损坏,Sink节点只要随机收集到k+ε,ε大于等于11个存储数据包,就能成功地计算出原来的k个源数据包．与具有代表性的基于LT码的算法相比,文中算法将存储每个源数据包的通信次数从约3nlnn降至约3n;将读取源数据包的节点访问次数从大于k+100降至约k+11．