求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的序列线性复杂度, 最后给出一个具体例子．     

基于极值索引的数据排序算法

提出一种新的数据排序算法,将数学极值的求解原理与数据排序结合,把极小值的概念扩展到记录的序列中,并按数据的排列规律,建立了极小记录索引,通过索引快速搜索待排序列中的记录,对待排序列快速的排序。该算法的最大时间复杂度T(n)为O(nlogn)和空间复杂度O(n),在提高排序效率的同时,保证了排序结果中的相同大小记录之间相对位置的稳定。     

进位返加与异或运算异或差值的概率分布

详细分析了进位返加运算的进位序列, 通过对Fn2空间的划分,解决了计算进位返加运算进位序列的概率分布问题. 提出了一种计算进位返加与F2上异或运算“异或差值”概率分布的有效算法, 该算法的计算复杂度为O((n－1)/2). 解决了用模2加运算整体逼近进位返加运算时产生误差的概率分布,同时也反映了这2个运算的接近程度.     

基于右移k ary消减的递归最大公因子算法

对于输入B和C,利用Sorenson的右移k ary消减（right shift k ary reduction）思想提出一种算法用于寻找整数x和y,使得x和y满足Bx－Cy在二进制表示下低比特位部分为0,利用该算法能够大规模降低循环次数,再结合模算法,提出递归最大公因子算法。递归最大公因子算法复杂度虽然对Knuth Schnhage算法的复杂度上没有提高,仍然是O(nlog2nloglogn),但是该算法相比于Knuth Schnhage算法实现简单,正确性分析和复杂度分析都比较容易。     

M(o)bius立方体上一个新圈的构造算法

研究了求n维Mobius立方体中Hamilton路的过程，给出了求n维Mobius立方体中长度为l的圈的算法（n≥2，4≤l≤2^n)。该算法的时间复杂度为O（l)，从而改进了樊建席等给出的时间复杂度O（NlogN)的算法。     

一种求所有最长增量子序列的算法

对计算最长增量子序列(longest increasing subsequence, LIS)的CM (Cover-Making) 算法进行详细地分析,提出一个基于CM算法的新算法,可以求出一个序列的所有最长增量子序列。 它的时间复杂度是O((m+1)k+(n-k)log k), 空间复杂度是O(n+km)。     

最值吸收算法解决矩阵连乘次序问题

通过分析矩阵序列乘法的特点,找到了一种新的算法一最小维数边界吸收算法,并将此算法分别与穷举搜索算法、动态规划算法的时间复杂度及空间复杂度进行分析比较．可以看出,动态规划算法的时间复杂度为O（n^3）,空间复杂度为O（n^2）,而本算法的时间复杂度和空间复杂度均为O（n）,并且不需要额外的空间开销．     

分块递归序列比对算法

利用分块递归的思想,结合检查点计算方法,提出一种线性空间复杂度序列比对算法,对于给定长为m和n的2条序列,空间需求约5(m+n)+Lsmin(m-1,n-1)+C2~5(m+n)+Ls(m+n-2)+C2,而时间需求一般情况下约1.5mn~3mn,在待比对序列相似度较高时约1.5mn~2mn,并通过同源物种全基因组序列比对实验证明,如果归一化编辑距离小于0.25,那么该算法比Hirschberg算法快10%以上.     

一种基于搜索空间分解的报文分类算法

报文分类算法的关键问题是查找准确且快速,最简单的分类算法就是线性查找,该算法的时间复杂度和空间复杂度均为O(N),线性查找的思想简单、易于实现、空间复杂度好,可以和其它算法混合使用,进而提高算法的分类速度。快速的分类算法采用很复杂的数据结构,牺牲空间来换取时间,甚至过分要求分类的快速性,忽略了空间性。文章根据这一问题进行展开,详细分析了经典的报文分类hicuts算法,分析其时间复杂度和空间复杂度的关系,并提出一种不过分降低分类速度的前提下,有效降低空间复杂度和预处理时间的改进方法。     

KM1M2生成器输出序列的特性分析

文章从代数角度讨论了KM1M2生成器输出序列的密码学特性，得到了其输出序列具有较长的周期，较高的线性复杂度，尖锐的自相关特性和弱的互相关特性，并具有相关免疫性等结果。     

二元周期序列的k-错线性复杂度研究

线性复杂度和k-错线性复杂度是度量密钥流序列的密码强度的重要指标.通过研究周期为2n的二元序列的线性复杂度,该文提出将k-错线性复杂度的计算转化为求Hamming重量最小的错误序列.基于Games-Chan算法,讨论了线性复杂度为2n-m的2n-周期二元序列的k-错线性复杂度分布情况.当(m,k)=(5,4),(6,4...     

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

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

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.     

Layered heuristic algorithm for multiple restriction routes

A layered algorithm by bidirectional searching is proposed in this paper to solve the problem that it is difficult and time consuming to reach an optimal solution of the route search with multiple parameter restrictions for good quality of service. Firstly, a set of reachable paths to each intermediate node from the source node and the sink node based on adjacent matrix transformation are calculated respectively. Then a temporal optimal path is selected by adopting the proposed heuristic method according to a non-linear cost function. When the total number of the accumulated nodes by bidirectional searching reaches n-2, the paths from two directions to an intermediate node should be combined and several paths via different nodes from the source node to the sink node can be obtained, then an optimal path in the whole set of paths can be taken as the output route. Some simulation examples are included to show the effectiveness and efficiency of the proposed method. In addition, the proposed algorithm can be implemented with parallel computation and thus, the new algorithm has better performance in time complexity than other algorithms. Mathematical analysis indicates that the maximum complexity in time, based on parallel computation, is the same as the polynomial complexity of O(kn2-3kn+k), and some simulation results are shown to support this analysis.     

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

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

关于(0,2,3)型插值多项式的逼近阶研究

设f(x) ∈C_(2π),Qn(f,x)是以x_(kn)=(2πk)/n(k=0,1,…,n-11)为基点的(0,2,3)型插值多项式,n=2m+1。Tm(f,x)是以{X_(kn)}_(k=0)~(n-1)为基点的(0)型插值多项式。因为u_n(x)∈C_(2π),使得 lim[f(x)-Q_n(f,x)-u_n(x)(f(x)-T_m(f,x))]=0 n→∞ (关于0≤x≤2π一致地成立)。本文进一步得到了逼近阶估计: |f(x)-Q_n(f,x)-u_n(x)(f(x)-T_m(f,x))| ≤C[ω(f,(1_nn)/n)+1/n_(k=1)~nΣω(f,1/k)]     

基于均值查找的快速中值滤波算法

针对传统中值滤波算法时间复杂度高、运行速度慢,难以满足大型图像数据实时处理的问题,提出了一种快速中值滤波算法,将确定中值元素的过程由排序运算转换为基于均值对集合的二分查找,算法不依赖于滤波窗口的形状以及相邻窗口的相关信息,有效提高了中值滤波的执行效率,使传统中值滤波算法的时间复杂度由O(nln n)下降至O(n).实验中,该算法应用于大型图像序列的滤波处理,其运算速度提高到传统中值滤波算法的3倍以上,并且算法运行时间仅随滤波窗口大小线性增长,可以满足大尺度滤波窗口对大型图像数据实时处理的需求,具有显著的实际应用价值.