一种新的多项式表示法及其在密码中的应用

论文提出一种新的多项式表示法———数值表示法,将多项式的乘法运算转化为数值运算,具有语意明确、运算准确和易于计算机实现的特点。新的数值表示法在求解布尔函数多项式表达式上的应用简洁快速而准确(只进行异或和与操作,代码只有5行)。用这种方法求出的DES的S盒的布尔函数表达式与现有文献结果相符,并第一次准确求出AES的S盒的布尔函数表达式。     

分辨矩阵在逻辑优化中的应用

真值表的化简对于逻辑电路的分析与设计具有及其重要的意义.对真值表的化简问题进行研究,提出了一种利用分辨矩阵从真值表中获取最小布尔表达式的粒分辨矩阵方法,实现其在逻辑优化中的应用.首先,将真值表视为逻辑信息系统,将真值表的化简问题转化为逻辑信息系统的最简规则发现问题.然后,在传统分辨矩阵的基础上,利用等价关系模型构造粒分辨矩阵,找出可以组织成最小布尔表达式的信息粒,利用信息粒的析取合取运算获得逻辑信息系统的最小布尔表达式.为进一步加快算法的收敛速度,引入启发式信息的概念,给出了组织信息粒的判定法则,避免在最小布尔表达式的获取中出现冗余逻辑项,使得布尔逻辑表达式最简,同时提高最小布尔表达式的获取效率,解决大规模逻辑电路的优化问题.最后,给出了详细的算法,并通过实例和理论证明说明了该方法的正确性和有效性.     

基于generalized dominator的BDD布尔表达式优化分解

BDD是布尔函数的一种图形表示方式,可以直观地反映出布尔函数的逻辑结构,利用BDD可以实现对布尔函数的分解和优化。针对BDD的数据结构和一种以generalizeddominators为基础的布尔表达式的优化方法进行研究,并且着重对其中的一种方法:连接的BDD分解方法(ConjunctiveBDDDecomposition)进行了详细的分析。     

平方可积函数解析分解的构造性证明

在H_∞控制理论及应用其理论进行设计中,经常用到结论:在虚轴上定义的平方可积函数分别与在开左、右半平面解析且一致平方可积函数的相互对应关系.但由于此结果的证明较多地用到不同学科的数学结论,故很难找到其详尽的证明.应用构造性方法,找出了它们间相互对应的数学表达式,并详细证明了这个表达式的准确性,证明了这种关系是一一对应的.     

基于generalized dominator的BDD布尔表达式优化分解

BDD是布尔函数的一种图形表示方式．可以直观地反映出布尔函数的逻辑结构，利用BDD可以实现对布尔函数的分解和优化。针对BDD的数据结构和一种以generalized dominators为基础的布尔表达式的优化方法进行研究，并且着重时其中的一种方法：连接的BDD分解方法（Conjunctive BDI）Decomposition）进行了详细的分析。     

三类布尔函数的相关函数研究

布尔函数的相关函数能刻画其扩散特征和线性结构特征,所以研究相关函数的性质对于布尔函数理论具有重要作用。为此,根据自相关和互相关函数的定义,分析通过迹表示的二次布尔函数f(x)=Tr_1~n(x~(2~i+1)+x(2~′+1))的自相关函数值,给出互相关函数平方的一个表达式C_(f,g)~2(α)=(?)(-1)~(D_(f,g)(a)+D_(f,g)(a+ω)),利用该表达式给出任意三次布尔函数的自相关函数平方和的上界,并借助该上界进一步研究两类迹表示的三次布尔函数的绝对值指标上界问题。     

布尔函数的代数免疫与扩散阶的关系

本文利用布尔函数全局雪崩准则得到平方和指标与代数免疫的联系,通过Walsh谱与自相关函数的关系式得到布尔函数满足扩散时自相关值的分布,由此推出了变元数、代数免疫、扩散阶和代数次数之间的不等式,利用计算机搜索得到变元数在4~30之间时这四个指标的简洁表达式。最后得到了扩散阶与线性结构、正规性的关系。     

布尔函数的复杂系数及其应用

本文利用线性复杂度相关理论，给出了布尔函数复杂系数的定义：得出任何布尔函数的线性复杂度均等于这个函数的复杂系数；给出了一种快速求解布尔函数多项式表示的算法；研究了Bent函数的线性复杂度特点，利用布尔函数的复杂系数，得出布尔函数为Bent函数的一个必要条件。     

基于改进关系积的最小属性约简算法

属性约简是粗糙集理论的核心内容之一。针对现有关系积理论不能求解不一致决策表中最小属性约简的缺陷,提出一种基于知识联合划分的改进关系积和关系积约简概念,分析了关系积约简、正区域和负区域之间的性质,提出一种基于改进关系积的最小属性约筒算法。理论分析和实例计算结果表明,该算法具有可行性,能求取一致或不一致决策表中所有最小属性约简。     

布尔函数零化子次数的一个错误证明的更正

指出了张文英等人关于零点集包含一个k维子空间的n元布尔函数一定存在[n-k]次零化子的证明,存在明显错误。利用线性空间笛卡儿积的思想,给出了关于上述结论的简洁、严密的逻辑证明。     

一种改进的小矩阵连乘算法

首先引入了矩阵的连乘优先因子,接着采用连乘优先因子最小的贪心选择策略,提出了最小连乘因子优先算法。它确定125的连乘次序不一定是最优次序,但在确定连乘次序方面比动态规划法花费的时间和空间少。最后通过实例对比测试,表明该算法在计算小矩阵连乘时,总体效率优于动态规划法。     

布尔矩阵乘的分布式异构并行优化

布尔多项式求解是当今密码代数分析中的关键步骤,F4算法是布尔多项式求解的高效算法。分析了Lachartre为F4矩阵专门设计的高斯消去算法,针对其中布尔矩阵乘这一耗时的计算步骤,设计并实现了分布式异构(CPU+MIC)并行算法。布尔矩阵相对于普通矩阵主要体现在矩阵元素取值区间不一样上,由于布尔矩阵元素(0,1)导致矩阵乘操作的特殊性,普通矩阵乘的优化方法不能很好地满足布尔矩阵乘的需求。分别从布尔矩阵的存储、OpenMP多线程组织、访存、任务划分和调度等方面进行了性能优化,实现了布尔矩阵乘的分布式异构并行算法。通过随机生成布尔矩阵测试,优化后的分布式异构并行程序相较于分布式同构并行程序达到了2.45的加速比,体现了良好的性能提升。     

实验数据的最小二乘拟合算法与分析

曲线拟合的优度,以及正交多项式最佳阶数的选择是程序研制过程中一个很关键的问题,用正交多项式最小二乘法进行曲线拟合是一种处理实验数据的重要手段。通过严格的数学推导,选择正交多项式,采用最小二乘逼近作为拟合实验数据的方法,利用F检验。确定实验数据拟合优度及最佳阶数,用编制的程序来拟合实验数据。得到了较好的结果。     

基于稳健算法的直线拟合

直线是图像分析中非常重要的描述符号。对工业控制中的现象进行图像处理时常常会用到直线拟合,虽然已有的拟合方法较多,但都存在一些缺陷限制着它们的使用范围。针对图象处理中利用经典最小二乘法拟合直线出现的问题,提出了有效的稳健型最小二乘法和最小一乘法的新型解法,实验证明了该方法的有效性及高精度性。     

Larger lower bounds on the OBDD complexity of integer multiplication

Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations and ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Recently, the question whether the OBDD complexity of the most significant bit of integer multiplication is exponential has been answered affirmatively. In this paper a larger general lower bound is presented using a simpler proof. Furthermore, we prove a larger lower bound for the variable order assumed to be one of the best ones for the most significant bit. Moreover, the best known lower bound on the OBDD complexity for the so-called graph of integer multiplication is improved.     

对称布尔函数的算术相关函数

算术相关函数是最近提出的一种研究布尔函数密码学性质的方法,该方法通过定义多元2-adic数上的加法和乘法运算,构建一种新的环结构,实现对经典相关函数的带进位计算的模拟。首先介绍了算术相关函数的定义,并针对具有良好密码学性质的对称布尔函数讨论了其算术相关函数的性质和取值,最后利用对称布尔函数的实值对称性证明了对称布尔函数的算术自相关函数也是一个与向量的重量有关的实值对称函数,至多是n+1值的。     

B样条乘积计算的区间跳跃算法及应用

利用B样条基函数节点区间的对应关系,首先给出了B样条基函数间的转换矩阵的计算方法,进而给出了计算B样条乘积的区间跳跃算法。该算法仅需计算部分节点区间上的转换矩阵,因此称其为区间跳跃算法。这一方法解决了分段多项式与B样条曲线乘积的计算问题,可应用到B样条曲线的升阶、曲面间光滑拼接等问题中。通过算例验证了该方法计算简捷、易于实现。     

Minimum time control of large‐scale boolean control networks with constraints

The minimum time control that steers a large‐scale Boolean control network with constraints from an initial state to a given state is investigated. This problem is studied under the partition of the large‐scale Boolean control networks. Based on that, the problem is converted to finding the minimum time control for each subnetwork. Hence, the minimum time control for small size Boolean control networks with constraints is considered firstly. Then, a method to solve the problem for large‐scale Boolean control networks with constraints is presented. Finally, a numerical example on T‐cell receptor kinetics is given to show the effectiveness of the main results.     

一种新的加法型快速大数模乘算法

通过对目前常用的几类模乘方法的综合研究，充分吸取估商型模乘算法的估商思想，借助Montgomery型模乘算法中模2n易计算特性，采用窗口分段处理方式，给出了一种新的利用模N进行预计算的方法，进而提出了一种新的加法型模乘AB mod N快速实现算法。模N为1 024-bit、窗宽为6时，新算法平均仅需693次1 024-bit加法便可完成一次AB mod N模乘运算，与当前加法型模乘算法相比，较大幅度地降低了计算复杂度。     

基于矢量积的二维封闭图形轮廓信息提取方法

视图轮廓信息在图形处理中有着重要的作用。该文提出基于矢量积提取二维封闭图形轮廓的方法,不再需要计算角度就可快速选择交叉点处的下一条路径,提高了图形生成效率。