数域筛法分解re±s型大整数时多项式的选取

数域筛法是目前最有效的大整数分解算法,多项式的选取是该算法中的一个重要环节,它关系到整个算法的运算速度和所耗时间.对数域筛法分解re±s型大整数时的多项式选取问题进行了研究,这里r、s分别为绝对值较小的整数.通过理论分析和数值计算,给出了选取多项式的一个新的原则-多项式次数在不同情况下的取值范围.     

针对小规模整数的MPQS算法

数域筛法是目前最有效的大整数分解算法,其中候选关系的光滑性判断需要对大量规模不大的余因子做分解,MPQS作为110-digits以下最快的分解算法得到广泛的应用。但现有的MPQS软件包针对96 bit以下的整数优化不足,未充分挖掘整数规模对MPQS性能的影响。针对小规模整数的MPQS算法提出新多项式系数选取和循环拷贝筛两种优化方法,新的系数方案配合参数选取和中间结果规模控制可以尽量避免使用多精度函数;循环拷贝筛法根据筛法定理与周期函数的周期性,利用循环拷贝替代小素因子的筛法,解决了小素因子筛法成本过高和部分因子基筛法筛选效果差的问题。在神威蓝光国产CPU平台上进行的实验测试表明,两种优化方法可使MPQS性能提高30%以上。     

关于RSA的一个注记

RSA是当前应用最广泛的公钥密码系统,它的安全性依赖于大整数分解的困难性.对RSA大整数N=pq,若存在整数t=uv,使|pv-qu|~2<4m,其中m=「N· uv~(1/2)」+1.给出了一个基于一元二次多项式的能有效分解N的算法,并用算例验证了其有效性.进而,为了保证RSA的安全性,根据连分数理论,给出了选取安全的RSA大整数的一个新的准则.     

采用牛顿插值的多项式因式分解算法的设计与实现

基于Kronecker所提供的一元多项式因式分解的构造算法、一元整系数多项式在整数环上因式分解理论,利用牛顿向前差分插值算法代替拉格朗日插值算法,把有理域上一元高次多项式因式分解化为在整数环上的因式分解,得到了整数环上的一元多项式因式分解的构造性算法,给出了具体实现过程。     

一种基于RSA的改进安全算法

针对传统RSA算法的安全性问题,在研究传统RSA算法加密的基础上,对标准RSA密码算法的自身结构和素数选取两方面,做出了相应的改进,提出了一种RSA改进算法。具体的过程如下：将大整数分解成5个素数p、q、r、s、t的乘积,分解的过程是先取大整数中的两个因子p和q,接着在p,q的基础上,使r=p×1.033,s=q×1.026,t=p×1.029,分别确定r,s,t因子,再对生成的素数因子,进行ASCII码转换,转换后的ASCII码再与其前一个ASCII码,进行同或加密。将其与传统的RSA算法相对比,进行安全性分析,结果表明： RSA改进算法相比于传统的RSA算法,在安全方面上有了一些提高。     

一种新的大整数乘法算法

为解决超出计算机系统基本整数类型表达能力的整数(大整数)算术运算问题,以基础算法--大整数乘法为研究对象,根据大整数的表示形式与多项式表示形式上的相似性,结合大整数乘法进位与取模的特点,给出了一种关于大整数乘法的多项式算法.其方法与别的方法最大的不同是,虽然是求两个大整数乘法,但整个算法没有使用乘法,只是用加法运算而已...     

基于多项式的大整数相乘算法

为解决超出计算机系统基本整数类型表达能力的整数(大整数)计算问题,以基础算法--大整数乘法为研究对象,根据大整数的表示形式与多项式表示形式上的一致性,结合大整数乘法进位与取模的特点,给出了一种关于大整数乘法的多项式算法.与现有的大整数位乘法进行了比较,证明该算法将大数相乘问题的复杂度降低到位乘法的1/3,并通过程序验证了该算法的性能,其结果与对于它们时间复杂度的分析基本一致.     

大整数取模的快速运算

大整数取模运算是密码学应用的一种基本运算,尤其是在基于因子分解假设的公钥密码学中占有极其重要的地位。提出的m位和n位两个大整数快速取模算法,是利用分治法思想,将n位的大整数分解为n个独立十进制整数的组合,通过八次大整数乘法建立一个预处理表,能够有效地将大整数取模的计算复杂度降为[O(n(m-n))],经大量实验数据验证该算法的合理性和高效性。     

AKS算法对现代密码学的影响

最近,印度的三个计算机科学家ManindraAgrawal、NeerajKayal和NitinSaxena提出了一个称为AKS的算法。笔者使用这个算法证明了可在多项式时间内对一个整数是否为素数进行确定性的判定,从而解决了一个古老的数学问题。这个结果对于数论和计算复杂性理论的研究与发展具有重要意义。由于现代密码学正是建立在整数分解理论和计算复杂性理论的基础之上,因此这个算法对现代密码学的影响引起了人们的关注。该文将就此进行阐述。     

基于Miller-Rabin素性检测的多项式分解算法

通过将Miller-Rabin素性检测的思想拓展到多项式域，随机二分搜索可应用到多项式分解中。并以此为基础，分别针对有限域和代数数域改进了两种概率性算法。第一种算法在有限域上每次分解模素数的多项式的失败概率最多为1/4；第二种算法在代数数域上每次分解模素理想P的多项式的失败概率最多为1/2，当代数数域为偶数次扩展或者P|( p)满足 p为素数且4|p-1的形式时，失败概率至多为3/8。和原有算法相比较降低了失败概率。这两种算法都在分解之前进行了素性判断，这一特性可用于生成不可归约多项式。在讨论代数数域情况时，给出了完整的多项式运算的时间复杂证明，弥补了代数数域内多项式计算理论模型上的空白。     

Matlab环境下素数筛选算法的分析及比较

利用Matlab对矩阵科学运算的支持,在Matlab环境下对埃拉托斯特尼筛法、Dirichlet定理衍生的素数筛法、辛答拉姆筛法和基于奇合数分解式的素数筛法进行算法实现和初步优化,并测试其性能,研究发现在计算大数范围的素数表时,算法之间的性能差异明显.通过对这些算法的比较和评价,分析各个算法的优缺点.研究结果表明,对于不同环境要求和不同的待解问题需要选取合适的素数筛选算法,因此,文中结论具有一定的指导意义和实际参考价值.     

一种快速分解大整数的小因子的优化分解树OFT算法

分解大整数的小因子是解决IFP，DLP问题的诸多攻击方法中的重要运算模块．本文在目前分解大整数小因子算法的基础上，提出的优化分解树(Optimized Factorization Tree)算法，利用树型数据结构和相应的构造算法与回溯算法，配合以作者提出的分解表截支方法和优化分组策略，可以将分解大整数小因子的速度提高50％以上．该算法还可以为大整数素性判别做高效过滤，快速识别大部分合数．     

提升的M通道小波变换在图像压缩中的应用

针对M通道小波变换对信号分频范围更细这一特点,利用基于空间域的小波提升方案,实现了M通道小波变换的提升分解。这种提升分解是不唯一的,可以利用这种分解的不唯一性,使变换具有所需的性质。为此给出了一种M通道快速提升小波变换的算法。该方法只要有分解算法,立即可以得到合成算法,而且将运算结果取为最接近的整数,就可实现整数到整数的小波变换。实验结果表明了该方法对图像压缩的有效性。     

两类整数分解算法的分析与改进

给出了整数分解的两种算法,试除法和Pollard算法.根据素数分布的规律,通过减少试除次数提高了试除法运算效率,使得其性能显著提高;对Pollard算法进行分析后,变换随机序列产生式并重启算法使算法运行更稳定有效.给出了这两类改进算法的运行时间对比表,结果表明,改进的试除法在分解32位内小整数效果更佳而改进的Pollard算法在分解32位以上大整数有明显的优化.     

对基于不同难题的公钥加密体制的分析及安全性比较

介绍了基于大整数分解问题,普通素数域上离散对数问题和椭圆曲线点群上的离散对数问题的公钥密码系统给出了它们的实现方案以及常用的攻击算法和算法复杂度。并对这三种密码系统的性能进行分析和比较,指出各自优劣和今后的发展前景。     

大整数的素性测试软件

本文讨论了利用分圆域中分圆整数的Jacobi和进行大整数素性测试的原理与算法,给出了基于Adleman和Pomerance所发现后由Cohen和Lenstra改进的一种确定性方法而开发研制的素性测试软件。该软件已在IBM 486计算机上调试通过。其运行结果表明,本软件可以根据待测试整数的大小,选取适当的参数,对大整数进行快速素性测试。     

基于三维整数小波变换的图像压缩算法TDPIWT

介绍了整数小波变换的应用背景、特点及提升方法.着重分析了三维整数小波变换的分解过程,对其纵深方向的分解方法作了改进,讨论了选取最优整数小波变换的方法.并提出了一种基于三维整数小波变换的图像压缩新算法TDPIWT,该算法适用于压缩医学序列图像.     

RSA密码分析中分解大整数的判定算法

RSA的安全性是依据大整数分解的困难性而设计的。在RSA的密码分析中,根据RSA公钥加密体制中的公开密钥n为2个大素数乘积的特性,针对形如n=pq(其中,p、q为大素数)的大整数n分解,提出一种分解n的判定算法,并对n的素因子特征与该算法的有效性关系进行分析。经过数学证明和相应算法设计证实,该算法的复杂度低于O(plogn)。     

对基地不同难题的公钥加密体制的分析及安全性比较

介绍了基于大整数分解问题，普通素数域上离散对散数问题和椭圆曲线点群上的离散对数问题的公钥密码系统，给出了它们的实现方案以及常用的攻击算法和算法复杂度。并对这三种密码系统的性能进行了分析和比较，指出各种优劣和今后的发展前景。     

整数提升小波多相矩阵分解系数的快速提取算法

整数提升小波多相矩阵分解系数不唯一,选取方法多样,计算量大。首先采用滤波器迭代次数选取算法,按照输入的信噪比(SNR)比例求出优化迭代次数;然后以非线性迭代比较算法为判定准则,结合求出的优化迭代次数,得到满足参数要求的优化分解系数。迭代次数是依据待测数据求得的,因此优化分解系数对该数据取得较好的处理效果,满足多相矩阵分解系数选取的要求。迭代比较算法满足收敛特性,通过比较滤波器的冲击和阶跃响应是否满足设定的误差限,可减少迭代运算次数,快速准确地选取优化小波系数。通过实验分析可知,该快速提取算法能有效满足数据处理的要求,减少待测数据处理的计算量,提高数据处理的效率。