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

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

一种代数正规形快速变换的零化子算法

利用布尔函数代数正规形的性质提出一种代数正规形快速变换和计算方法,该方法具有最小的存储空间和很高的计算效率．以此为基础,提出两种计算布尔函数零化子的有效算法：第1种算法可以求出所有n元布尔函数的代数免疫阶数和最低次零化子的代数正规形表达式;第2种算法能够求出任意一个n元平衡布尔函数代数免疫阶数和所有不超过d次的零化子．同已有基于求解线性同余方程组的零化子求解算法相比,该方法可操作性强,能够更加有效地用于评估布尔函数抵抗代数攻击的强度．     

求解域元素分量表达式的两种新方法

提出有限域上线性变换迹函数的计算方法,在此基础上给出计算域元素分量表达式的一种新方法;通过计算标准基的对偶基,提出求解域元素分量表达式又一种新的有效方法．两种方法都以迹函数的形式给出域元素分量的表达式,所需数据量仅为n,计算复杂度仅为O(n),相对于已有方法的指数复杂度,这是一个很大的提高．给出Rijndael S盒分量函数间等价关系的一种证明方法,用一个GF(2⁸)上的八阶矩阵完全刻划这种等价关系,比已有文献用56个GF(2)上八阶矩阵刻划等价关系的构造式间接证明方法更为直接和简单．     

Mod 2n加法和减法的代数正规型

文献[1]给出了从n元布尔函数f的代数正规型得到f（X＋Y mod 2^n）和f（X＊Y mod 2^n）的公式,其中Y是常数。基于mod 2^n加法进位比特的性质,给出了求X＋Y mod 2^n或X-Y mod2^n的n个分量函数的代数正规型的方法。其总的计算复杂度分别为O（2^n）（或O（3n））。远远低于经典的用真值表计算布尔函数代数正规型的算法[2]。使用文献[2]的算法仅得到X＋Ymod 2^n（或X-Y mod 2^n）最高位的计算复杂度就达O（2^n＊22 n）。     

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

布尔函数零化子的构造及其在流密码中的应用

代数攻击的基本思想是建立密钥比特和输出比特之间的方程,然后通过解超定的低次方程组来恢复密钥。在代数攻击中,可以通过布尔函数的零化子建立低次方程,从而使算法的复杂度降低。文章首先给出了两种布尔函数零化子的构造方法,然后将构造2分别应用于LILI-128和Toyocrypt中,得到低次零化子,通过此低次零化子建立低次方程进行攻击。与已知的攻击方法相比较,攻击的复杂度大大降低。     

对称Loewner方程组极小范数最小二乘解的快速算法

对于工程计算中常常遇到的一类线性方程组的求解,通过构造特殊分块矩阵并研究其逆矩阵的三角分解,给出了求秩为n的m×n阶对称Loewner矩阵为系数阵的线性方程组,及极小范数最小二乘解的快速算法,该算法的计算复杂度为O(mn) O(n2),而一般方法的计算复杂度为O(mn2) O(n3).     

基于RSA函数的实用电子拍卖方案

给出了一个基于RSA函数的密封电子拍卖方案，任何投标者不能否认所投的标书，未中标价不会被泄露，可以实现投标者的身份匿名．该方案执行开标算法至多需要[log2 p]轮交互，至多[2log2 t log2 p]次模乘法运算，其中p是标价的范围，t是RSA公钥．计算量与投标者的数量无关，其典型实现在最坏的情况下只需119次模乘法运算，远高于现有拍卖方案的效率。     

Square-6攻击的修正方案

Square-6攻击曾被认为是对6圈AES算法Rijndael最为有效的攻击之一,通过猜测4个首圈子密钥构造只含一个活动字节的Λ集,在此基础上实施Square-5攻击,时间复杂度为2⁷². 文中指出Square-6攻击并不能构造出Λ集,从而攻击是不成功的;利用部分和技术给出不依赖于首圈子密钥的修正的Square-6攻击方法,其时间复杂度为2⁵⁰.     

固定序Bellman-Ford算法的一个改进

通过对固定序Bellman?Ford算法进行修正,获得了一种求解边数不大于k的最短路问题的新算法．相对于原始算法,修正后的算法通过改变点的标号过程,使得在第k次迭代后每一条路径的边数均不超过k．新算法被证明是正确的,它的计算复杂性为O（ km）．实验表明,在大规模情形下,相对于修正的先进先出算法,该算法具有显著的竞争优势．     

布尔函数的代数攻击

基于代数攻击,提出了一种已知部分真值表还原整个布尔函数的方法。对于n元d次布尔函数, 该方法的空间复杂度和数据复杂度均为O(N),计算复杂度为O(N3),其中N=1+C1n+C2n+…+Cdn。由复杂度可知,所求密码函数的代数次数越低,该方法的有效性越高。攻击方法表明密码设计中应该谨慎使用代数次数较低的布尔函数。     

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

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

曲面的GC~k拼接条件

在一定的基本假设下，若Ｓ（ｈ１）≠Ｓ（ｈ２）≠Ｓ（ｈ３），得到了存在一个ｐ次多项式ｆ，使曲面Ｓ（ｆ）分别与Ｓ（ｇｉ）在Ｓ（ｇｉ，ｈｉ）（ｉ＝１，２，３）处ＧＣｋ光滑拼接的充要条件为存在ｐ－ｍ次多项式ｗ１，ｐ－ｎ次多项式ｗ２，ｐ－ｌ次多项式ｗ３，以及多项式ａｉ（ｉ＝１，２，３）使得ｗ１ｇ１－ｗ２ｇ２＝ａ２ｈｋ＋１２－ａ１ｈｋ＋１１∈〈ｈｋ＋１１，ｈｋ＋１２〉ｗ２ｇ２－ｗ３ｇ３＝ａ３ｈｋ＋１３－ａ２ｈｋ＋１２∈〈ｈｋ＋１２，ｈｋ＋１３〉｛从而将ＧＣｋ拼接问题的复杂运算化简成了一个简单的线性方程组。     

一类新的二次广义Bent函数

Bent函数广泛应用于密码学、编码等领域.利用线性化置换多项式构造了GF（pn）上一类新的二次广义Bent函数kΣi=0Trn1（cixpei＋1）＋σ·Tr1n/2（cm/2xpn/2＋1）,其中,ci∈GF（pe）,n=me,k=「 m/2」-1,σ≡m＋ 1mod 2,并给出了这类函数为广义Bent函数的两个充要条件.针对m=pvhr和m =2pvhr这两种情形,p和h是满足一定条件的奇素数,给出了GF（pn）上二次广义Bent函数kΣi=0Trn1（cixpei＋1）＋σ·Tr1n/2（cm/2xpn/2＋1）的个数.     

大规模有限阵列结构快速算法

提出了一种简单有效的计算大型二维阵列雷达散射截面的新方法．利用分域全域基(SED)构建基函数,采用前后向迭代过程(FBM)解矩阵方程,并利用离散傅里叶变换(DFT)在谱域降低了矩阵向量积计算量．与广泛应用的多层快速多极子(MLFMM)方法相比,对于阵列未知量个数为N的问题,此方法在保证结果准确的前提下,使总的计算量和内存要求均由O(NlogN)降为O(N),可用于快速分析大规模的任意形状单元有限阵列．     

全光网中波长转换器分配算法的研究

介绍了光网络中波长转换器的作用,推导、分析了网络的阻塞率,在此基础上提出了一种波长转换器配置算法,并对该算法进行了模拟。模拟结果表明本算法得出的配置方式与最佳配置得到的网络阻塞率非常接近,而本算法的时间复杂度仅为O（3H＋w^2/2）。     

用解线性方程组方法求三对角矩阵的逆及其应用

根据三对角矩阵的特点,给出一种利用解线性方程组的方法求三对角矩阵的逆矩阵的算法.该算法有两个优点.第一,运算量小. 在整个计算过程中,只需进行O(3/2n2)次乘除运算.第二,节省内存. 除原始数据外,只定义3个一维数组,而不需任何二维数组.数值实验表明,它具有较高的精度.此算法特别适用于求解一大批具有相同的系数矩阵,而具有各自不同的非齐次项的线性代数方程组.     

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

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

星图应用哈米尔顿拉丁方的并行路由算法

提出了一种星图的信息路由算法.在星图中,从一个源节点到一个目的节点传递k个数据包,令第i个数据包将沿着第i条路径传输(1≤i≤k).对所有的数据包,要保证每个数据包的路径与其余数据包的路径不相交.为了构造这样的路由,提出了应用哈米尔顿循环拉丁方的星图信息路由算法,并给出该算法的时间复杂度是O(n2).