超椭圆曲线上Montgomery 标量乘的快速计算公式

超椭圆曲线密码体制与椭圆曲线密码体制相比,具有安全性高、密钥短的特点.标量乘计算是这两个密码体制中最为核心和重要的计算,其中,Montgomery 阶梯算法是计算标量乘的一种重要算法,且因为其可以抵抗简单的边带信道攻击,而被广泛研究和应用.近几年,椭圆曲线上的Montgomery 阶梯算法和相应的点运算公式一直在不断改进,但是在超椭圆曲线上,直接设计快速运算公式来提高Montgomery 阶梯算法的速度,却一直没有太大的进展.Lange 曾经探讨过这种快速公式存在的可能性,但却并没有得到一个实用、有效的计算公式.在特征为2 的域上,通过改进超椭圆曲线上的除子类加法公式来提高超椭圆曲线上的Montgomery 阶梯标量乘计算,提出了一种新的思路来改进多种坐标系下的加法公式.分析和仿真结果表明,在特征为2 的域上,新的运算公式的运行速度比之前的标准公式均有所提高.在某类常用曲线上,新的公式比之前的公式快了4%~8.3%.这说明,直接设计快速除子运算公式来提高Montgomery 阶梯算法的速度是可行的.同时,使用新的公式实现的Montgomery 阶梯算法可以抵抗简单边带信道攻击.     

计算生物学中的9叶星树问题

本文讨论翻转距离星树问题,证明实例中有向符号序列个数为9时,翻转距离星树问题问题是NP-难解问题,并给出了一个该问题的多项式时间近似算法.     

欧氏平面上NP-hard优化问题多项式时间近似方案设计技术

一、引言 欧氏空间中的组合优化问题均带有深远应用背景.这类问题的求解算法研究在计算机科学中占有重要位置.TSP问题、STEINER树问题、k-median 问题是三个经典的NP-Hard类组合优化问题[1～3],它们在欧氏平面上的求解算法广泛应用于网络可靠控制、集成电路设计、网络布局等领域.特别对TSP问题,虽然科学家们投入了大量的工作,但近三十年来没有取得实质性进展,而Arora等在1996-1998年应用相同的技术相继给出了上述问题在欧氏空间中的近似方案,使人们对该类问题的认识前进了一大步.     

翻转距离星树问题的计算复杂度和近似算法

讨论基于基因组翻转距离的星型进化树问题的算法和复杂性.首先证明星树问题是NP-难解的,再证明该问题不存在绝对近似求解算法,最后给出一个求解星树问题的常数近似算法,近似性能比为2.     

k-Median近似计算复杂度与局部搜索近似算法分析

k-Median问题的近似算法研究一直是计算机科学工作者关注的焦点,现有研究结果大多是关于欧式空间和Metric空间的,一般距离空间k-Median的结果多年来一直未见.考虑一般距离空间k-Median问题,设d_max/d_min表示k-Median实例中与客户点邻接的最长边长比最短边长的最大者.首先证明d_max/d_min≤ω+ε的k-Median问题不存在近似度小于1+ω-1/e的多项式时间近似算法,除非,由此推出Metric k-Median问题不可近似到1+2/e,除非NP(∈)DTME(N^{O(log logn)}).然后给出k-Median问题的一个局部搜索算法,分析表明,若有d_max/d_min≤ω,则算法的近似度为1+ω-1/2.该结果亦适用于Metric k-Median,ω≤5时,局部搜索算法求解Metric k-Median的近似度为3,好于现有结果3+2/P.通过计算机实验,进一步研究了k-Median局部搜索求解算法的实际计算效果和该算法的改进方法.     

合取范式3可满足问题的局部搜索近似算法

合取范式最大可满足问题是理论计算机科学的核心问题.局部搜索被许多求解实践证明是解答合取范式最大可满足问题十分有效的方法,但未见关于局部搜索算法解答该问题性能分析的结果.文中讨论最大3可满足问题(Max-(3)-Sat)的局部搜索算法并分析算法性能.证明Max-(3)-Sat问题的一位跳变局部搜索算法的近似性能比为4/3;证明一位跳变局部搜索后跟有条件全体跳变算法,解答Max-(3)-Sat问题的近似性能比为5/4.设计一位跳变加全体跳变的新局部搜索算法,证明新算法解答Max-(3)-Sat问题的近似性能比为8/7.将8/7-近似局部搜索算法推广为解答Max-(k)-Sat问题的局部搜索算法,证明算法的近似性能比为(2k+2)/(2k+1),k≥4.设计解答Max-(k)-Sat问题的两位跳变局部搜索算法,证明两位跳变局部搜索算法的近似性能比为1+1/(2k+1+k(k-1)/(n-k)),k≥4.局部搜索算法经多次运行可进一步提高求解性能.文中结果显示,局部搜索算法在合取范式最大可满足问题求解实践中表现出高性能,有其必然性.     

短块移动排序的14/11近似算法

块移动是基因重组的一种重要形式.短块移动是将排列中的元素最多移动到偏离原来两个位置的块移动.Heath和Vergara最先给出短块移动排序近似度为4/3的多项式时间算法.本文设计了近似性能比为14/11的短块移动排序新算法.首先讨论了具有伞形结构排列图的子排列的排序方法,并将这种子排列称为‘伞’,设计了特殊子排列伞短块移动排序的多项式时间精确算法.然后给出关联伞子排列短块移动排序的贪心算法.讨论了5种特殊子排列的短块移动排序方法,证明了它们短块移动距离的新下界,从而证明此贪心算法的近似性能比为14/11,这是目前解答短块移动排序问题近似性能比最小的多项式近似算法.     

带权集合覆盖问题的一种随机近似算法

给出了集合覆盖问题的一种随机近似算法。给定E={e1,e2,…,en}的子集的集合S和S中每个子集的权值,带权的集合覆盖问题是从S中选择费用和最小的子集使得其并集覆盖E。对E中每一个未被覆盖的元素,以某一精心设计的概率分布选择包含该元素的子集,直到E中所有元素均被覆盖,算法结束。该算法求出的覆盖的费用的期望值不超过B.opt,其中opt为最优覆盖的费用,B=maxe∈E{|L(e)|},L(e)={s|e∈s,s∈S}。算法时间复杂度为O(n),其中n为E的元素数目。     

有向基因组移位排序问题的O(n2)快速算法

有向基因组移位排序问题在计算生物学研究中占有重要位置．以前最好的算法时间复杂度为O(n^2logn)．该文给出一个有向基因组移位排序的新多项式算法，将移位排序的时间复杂度改进为O(n^2)．算法改进的关键在于找到一种寻找有效合理移位的新方法，通过在最小子排列中删除无关顶点确定一个合理移位是否有效，从而将寻找一个有效移位的时间复杂度改进为O(n)，总时间复杂度由此降为O(n^2)．     

基于最小聚类划分的K-means聚类(1+ε)近似算法

k-means聚类算法是解决聚类问题的一个常用方法.近年来,国外许多学者对该问题的近似常数算法和(1 ε)近似算法进行了研究.利用Kumar等人随机取样技术对于基于最小聚类划分k-means提出一个(1 ε)随机近似算法.该算法利用随机取样技术从集合中求出部分取样点,再对随机取样点进行组合找出每个聚类的部分点,将该部分点的质心点作为相应子聚类簇的质心点.通过多次运行该算法可以以较高概率求出k-means聚类的1 ε近似值.