Miller-Rabin素数检测优化算法研究与实现

针对素数值越大,检测时间越长,效率越低等问题,在研究了Miller-Rabin算法基础之上,通过加入预处理过程,对原算法进行了细致地优化,减少了原算法中幂模运算的次数,从而大大提高了对于素数的检测速度。

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

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

论Miller-Rabin算法预处理的局限性

信息安全领域中极为重要的公钥密码体制的关键在于生成两个大素数,目前虽已有多项式运行时间的确定性素性检测算法AKS算法,可惜运行时间还达不到实用要求,故还是快速实用的概率性素性检测算法Miller-Rabin算法为主流,但其有一点一直被忽略——Miller-Rabin算法直接控制的其实是误判率而不是出错率,而后者才是真正需要降低的。对此做了详细分析,同时考察一些利用素数分布特性的预处理措施在降低出错率方面的效果,并分析了这一类优化的效果极限,否定了其必要性,相比之下,针对算法底层的优化更为直接有效。

Rabin密码算法的快速实现研究

首先分析了利用MRC方法改进Rabin密码的解密算法,然后结合素性测试的优化策略和运算数与V i-sual C++6.0的特性,提出一种基于递归技术的快速素性测试方法。

素数测试在RSA公开密钥密码算法中的分析研究

论述了 RSA公开密钥密码技术及 RSA安全性分析 ,介绍了 Solovay-Strassen素数测试算法以及 Miller-Rabin素数测试算法 ,进一步论述了产生充分大的素数是切实可行的 .

秘密同态技术研究及其算法实现

在数据库加密系统中,秘密同态技术(privacyhomomorphism)能够对一些敏感的、重要的数据直接在密文的状况下进行操作,从而有效地保护这些数据。该文从实际工作出发,阐明了秘密同态技术的概念、算法、实现及其实现过程中的一些关键点。

智能卡中RSA密钥生成的比较与研究

研究了密钥生成的一般方法,即确定性素数判定和概率性素数判定方法,给出了利用Rabin M iller测试生成密钥对的算法实现。针对在智能IC卡中生成RSA密钥时所面临的实际问题,给出了最优的方案选择。测试结果表明,与目前国外同类RSA智能IC卡相比,其生成RSA密钥的时间较短。

可信赖的高效素数生成和检验算法

该文回顾研究了素数检验的历史,分析不同的算法利弊。在实际运用中提出一种可靠的高效运算的素数生成和检验算法。

有效解决RSA共模攻击的素数生成方案

RSA公钥密码体制是一种被广泛使用的公钥密码体制。为了求取RSA加密体制的加解密密钥,首先需要获得两个大素数。因此,大素数的选取及使用是保证RSA安全性的一个重要环节,不当的素数选取及使用将会使其很容易遭受攻击,共模攻击即为较常见的一种。针对这一问题,论文提出一种新的素数生成方案,保证为每一用户生成不同的大素数,消除RSA体制在使用中遭受共模攻击的可能,提高体制的安全性。

RSA公钥密码体制素数生成的研究

大素数的选取是构造ＲＳＡ密钥的关键，大素数的产生及测试是ＲＳＡ公钥系统中的一个重要研究课题．介绍了产生素数的一般方法，即确定性素数产生方法和概率性素数产生方法，并给出了利用Ｍｉｌｌｅｒ Ｒａｂｉｎ测试和Ｌｕｃａｓ定理生成强伪素数的算法实现．

RSA系列算法在工程中的应用研究

网络安全产品中,大都需要使用密码算法。公开密钥算法主要有RSA和ECC等。本文根据工程应用的实际情况,对RSA系列算法进行了深入研究,分析了不同子算法的优劣,从中选出了适合工程应用的子算法,并结合我们的项目需求提出了一些对算法的改进。

一种大素数快速生成算法设计与实现

针对RSA中对安全大素数的要求,基于对Rabin-Miller测试改进,通过引入预测试方法,设计实现了一个快速大素数产生算法。实验结果显示,算法具有良好的大素数产生效率,分析结果表明其产生的素数具有很高的可信度,具有较强的实际应用意义。

一种快速的素数生成和检验算法

就运算复杂度、报错率、实际运行效率等方面,对已有的素数检验算法进行了分析和比较.同时分析素数生成的相关算法,优化了ISO/IEC的生成算法并得到一个新的素数生成算法.

寻找是强伪素数的Carmicheal数

令N=q1q2q3,q1<q2<q3是三因子的Carmicheal数,定义C3,1-及C3,2-数,它们分别指qi=5 mod 8,i=1,2,3及qi≡5 mod 8,i=1,2,q3≡9 mod 16时的情况,它们有着较高的成为强伪素数的概率.本文首先给出成为这些数的充分必要条件然后给出算法,最后经过上机计算得到1024以内的有58个对于前5个素数基的C3,1-强伪素数,其中有一个是对于前8个素数基的强伪素数;以及27个对前4个素数基的C3,2-强伪素数,只有一个是对于前4个基的强伪素数.

AKS素性测定算法的一个改进版本在PC上的实现

AKS算法从理论上成功解决了在多项式时间内进行确定性素性测定的著名难题,但它并不实用,从而得到一系列的改进。为深入分析现有AKS改进算法的实际应用效率,利用Delphi-Pascal语言在微机Pentium IV/1.8G上实现了AKS算法的一个Bernstein改进版本(简称AKS-Bernstein第二算法),并分析比较了AKS算法现有几个版本的实际耗时。对于原先需要几十甚至几千个小时才能完成一次素性测定的数据,利用AKS-Bernstein第二算法进行测试仅需几十秒,从而指出该算法比其他版本有很大改进。此外,通过分析AKS-Bernstein第二算法仍然存在的一些不足,指出该算法在素性测定的实际运用上还有待进一步完善。

RSA公开密钥密码体制的密钥生成研究

介绍了密钥生成的一般方法，即确定性素数产生和概率性素数产生方法，并给出了利用 Ｍｉｌｌｅｒ Ｒａｂｉｎ测试和 Ｐｏｃｋｌｉｎｇｔｏｎ

RSA加密中大素数的生成方法及其改进

RSA加密算法的安全性是基于两个大素数的乘积用目前的计算机水平无法分解这一前提,生成两个满足长度要求的大素数,能够保证RSA加密数据的安全可靠。文章在对RSA算法基本原理及加、解密过程进行介绍的基础上,比较了几种常见检测素数的方法,并对个别算法进行了改进。综合它们的优缺点提出了一种新的生成安全大素数的方法及计算机实现相应算法的步骤。

RSA公开密钥密码体制的密钥生成研究

研究了密钥生成的一般方法 ,即确定性素数产生和概率性素数产生方法 ,并给出了利用 Miller

RSA公钥密码体制中安全大素数的生成

RSA算法是基于数论的公钥密码体制,是公钥密码体制中最优秀的加密算法。由于RSA算法中大素数的生成对RSA加密算法的安全性有直接的影响,其寻找大素数的实现难度大,运算时间长。文中在研究了密钥生成的一般算法的基础上,即确定性素数产生和概率性素数产生方法,给出了利用Montgomery算法优化的Miller-Rabin算法和Pocklington定理算法实现,构造了大素数的生成算法,以提高RSA算法的安全性和运行速度。

小素数筛值法生成素数实现RSA加密算法

描述了概率性素数产生方法,并给出了基于小素数筛值法生成素数的具体算法。应用Rabin-Miller测试和中国余数定理,编写出了生成强伪素数的核心算法的源程序。分析和试验表明,本文算法是切实可行的,而且大大提高了RSA算法中解密过程的实现速度。