基于Python的大素数生成方法原理分析与实现

1

作者 黄绍龙 《计算机应用文摘》 2025年第15期218-220,共3页

文章介绍了Miller-Rabin素性检测算法的原理,并基于Python语言实现了大素数的生成。对于随机生成的指定位数大整数,先采用小素数进行初步筛选,未被筛除的数再通过Miller-Rabin素性检测算法进行进一步判定。该方法在生成大素数方面具有... 文章介绍了Miller-Rabin素性检测算法的原理,并基于Python语言实现了大素数的生成。对于随机生成的指定位数大整数,先采用小素数进行初步筛选,未被筛除的数再通过Miller-Rabin素性检测算法进行进一步判定。该方法在生成大素数方面具有较高的效率。 展开更多

关键词 大素数 费马小定理 概率算法 随机化算法 Miller-Rabin素性检测

在线阅读 下载PDF 职称材料

Miller-Rabin算法研究与优化实现 被引量：9

2

作者 秦晓东 辛运帏 卢桂章 《计算机工程》 CAS CSCD 北大核心 2002年第10期55-57,共3页

Miller-Rabin算法是目前主流的基于概率的素数测试算法，在构建密码安全体系中占有重要的地位。通过比较各种素数测试算法和对Miller-Rabin算法进行的仔细研究，证明在计算机中构建密码安全体系时，Miller-Rain算法是完成素数测试的最... Miller-Rabin算法是目前主流的基于概率的素数测试算法，在构建密码安全体系中占有重要的地位。通过比较各种素数测试算法和对Miller-Rabin算法进行的仔细研究，证明在计算机中构建密码安全体系时，Miller-Rain算法是完成素数测试的最佳选择。通过对Miller-Rabin算法底层运算的优化，可以取得较以往实现更好的性能。 展开更多

关键词 Miller-Rabin算法 优化 素数 时间复杂度 误判概率 密码学 信息安全 计算机

在线阅读 下载PDF 职称材料

雅克比和素性判别方法的软件实现 被引量：1

3

作者 何德彪 陈建华 胡志金 《计算机工程与设计》 CSCD 北大核心 2007年第16期3818-3821,共4页

给出了一种确定性素性判别方法——雅克比和素性判别方法的软件实现,并对其中最关键的多项运算给出了一种快速算法。同时,通过对另一种确定性素性判别方法——AKS算法的存储复杂度的分析,指出AKS算法在PC机上实现的各种困难。最后给出... 给出了一种确定性素性判别方法——雅克比和素性判别方法的软件实现,并对其中最关键的多项运算给出了一种快速算法。同时,通过对另一种确定性素性判别方法——AKS算法的存储复杂度的分析,指出AKS算法在PC机上实现的各种困难。最后给出了雅克比和素性判别算法在奔腾IV 1.8 G上的实现结果。 展开更多

关键词 素数 素性判别 雅克比和素性判别 AKS算法

在线阅读 下载PDF 职称材料

一种大素数快速生成算法设计与实现 被引量：5

4

作者 雷文 邱玲 张弘 《四川理工学院学报（自然科学版）》 CAS 2011年第3期313-316,共4页

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

关键词 Rabin-Miller测试 大素数 生成算法 公钥密码

在线阅读 下载PDF 职称材料

RSA中大素数生成算法优化及电路实现 被引量：2

5

作者 郑朝霞 吴旭峰 +1 位作者 季媛媛 刘尹 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2017年第6期1-4,20,共5页

为了减少大素数生成时间并加快RSA(Rivest,Shamir&Adleman)公钥密码算法的加解密速度,并行化实现了小素数试除和Miller-Rabin素性测试两大关键步骤,使其在进行素性测试的同时能进行小素数试除,从而大幅减少了小素数试除单独运算消... 为了减少大素数生成时间并加快RSA(Rivest,Shamir&Adleman)公钥密码算法的加解密速度,并行化实现了小素数试除和Miller-Rabin素性测试两大关键步骤,使其在进行素性测试的同时能进行小素数试除,从而大幅减少了小素数试除单独运算消耗的时间.为了加速Miller-Rabin素性测试须要反复调用的模乘运算单元,采用一种基于字的高基Montgomery算法及多级流水结构,设计了一种可配置的高速模乘运算电路.经FPGA(现场可编程门阵列)测试,在100 MHz频率下,生成的512bit大素数的平均耗时约为75ms,生成的1 024bit密钥对的平均耗时约为166ms,耗时只有参照结果的54.2%左右. 展开更多

关键词 RSA算法 大素数生成 小素数试除 Miller-Rabin测试 MONTGOMERY算法 多级流水结构

原文传递

基于RSA算法的文件加密系统设计 被引量：1

6

作者 姜楠 金英善 +2 位作者 崔晓锋 刘波 李禾 《大连民族学院学报》 CAS 2013年第5期535-538,共4页

介绍了素数的定义、Solovay-Strassen素性测试算法、Miller-Rabin素性测试算法和RSA算法的基本原理,以及RSA算法在自然科学领域中的应用。进行了素数生成算法,RSA算法的安全性分析。设计了基于RSA算法的文件加密系统流程图,利用计算机... 介绍了素数的定义、Solovay-Strassen素性测试算法、Miller-Rabin素性测试算法和RSA算法的基本原理,以及RSA算法在自然科学领域中的应用。进行了素数生成算法,RSA算法的安全性分析。设计了基于RSA算法的文件加密系统流程图,利用计算机语言编程实现了文件加密和解密的实验系统。该系统简单易于实现,可以用于网络安全实验教学中,以促进学生对密码学中抽象理论的理解。 展开更多

关键词 RSA算法 系统实现 算法分析 素性检测

在线阅读 下载PDF 职称材料

搜寻广义Fermat素数 被引量：5

7

作者 皮新明 《数学杂志》 CSCD 1998年第3期276-280,共5页

设ｂ为偶数，本文讨论了广义Ｆｅｒｍａｔ数为素数的必要条件和充分条件，提出了搜寻广义Ｆｅｒｍａｔ素数的一种效率很高的算法并在微机上实现，得出了的全部广义Ｆａｒｍａｔ素数，其中最大的是。

关键词 素数 概素数 素性检验 广义费马数

在线阅读 下载PDF 职称材料

AKS算法及关于它的一种改进算法的实现分析 被引量：3

8

作者 朱文余 《四川大学学报（自然科学版）》 CAS CSCD 北大核心 2005年第3期459-466,共8页

2002年,Agrawal、Kayal和Saxena成功地解决了多项式时间判别素数这一著名的世界难题.他们给出了一个算法(简称AKS算法),该算法对输入整数是素数还是合数进行判断,它是一个确定的多项式时间算法.后来许多科学家对该算法进行了改进,其中... 2002年,Agrawal、Kayal和Saxena成功地解决了多项式时间判别素数这一著名的世界难题.他们给出了一个算法(简称AKS算法),该算法对输入整数是素数还是合数进行判断,它是一个确定的多项式时间算法.后来许多科学家对该算法进行了改进,其中一个比较好的改进是由Bernstein给出的(简称Bernstein算法).作者详细分析了这两种算法,利用C语言实现了这两种算法,并进行了比较,找出了真正需要用到AKS算法和Bernstein算法来判断其为素数和合数的最小数,并估计出所需要的运行时间. 展开更多

关键词 素数 合数 素数判定 多项式时间算法

在线阅读 下载PDF 职称材料

生成大素数的一个方法 被引量：1

9

作者 戴经国 张韶华 +1 位作者 易叶青 张春元 《科学技术与工程》 2007年第14期3510-3511,共2页

初步探讨了如何快速生成一个大素数p,使得p-1有大的素因子q的方法,其中q满足q>(p-1)/log2(p-1)。

关键词 素性检验 大素数生成 公钥密码系统

在线阅读 下载PDF 职称材料

《数根丛草》研究 被引量：2

10

作者 张祖贵 《自然科学史研究》 CSCD 1992年第2期127-138,共12页

本文研究了清末数学家方士(钅荣)的《数根丛草》。在李善兰素数论的基础上,方士(钅荣)在1896年完成的《数根丛草》中提出了20种判别素数的方法,不少具有独创性,其中最重要的是威尔逊(Wilson)定理,他和德国数学家亥尔维茨(A. Hurwitz)同... 本文研究了清末数学家方士(钅荣)的《数根丛草》。在李善兰素数论的基础上,方士(钅荣)在1896年完成的《数根丛草》中提出了20种判别素数的方法,不少具有独创性,其中最重要的是威尔逊(Wilson)定理,他和德国数学家亥尔维茨(A. Hurwitz)同一年将该定理应用于素数判别,并且早于记载在迪克逊(L. E. Dickson)《数论史》中的一些西方数学家。《数根丛草》还改进了依据素数定义的判别方法和李善兰《考数根法》中的方法。 展开更多

关键词 清代 数根 素数 判别

在线阅读 下载PDF 职称材料

b≤2000,m≤10的广义Fermat素数 被引量：1

11

作者 皮新明 《数学杂志》 CSCD 北大核心 2002年第1期91-93,共3页

设 b为偶数 ,本文基于作者的原有结果 ,进一步改进了算法 ,对于 b≤ 2 0 0 0 ,m≤ 1 0给出了所有广义 Fermat素数 F (b,m) =b2 m+1 ,其中最大的是 1 632 1 0 2 4+1 ,有 32

关键词 素数 广义FERMAT数 概素数 素性检验 算法

在线阅读 下载PDF 职称材料

一种快速的强素数生成方法 被引量：7

12

作者 游新娥 田华娟 《通信技术》 2009年第2期323-325,共3页

针对传统的大素数生成方法需进行较复杂的模幂运算,从而导致运算速度较慢的缺陷,本文基于Miller-Rabin概率性素数检测法提出了一种大素数生成的优化方法,有效地提高了寻找大素数的速度。基于此优化方法,提出了一种新的强素数生成算法,... 针对传统的大素数生成方法需进行较复杂的模幂运算,从而导致运算速度较慢的缺陷,本文基于Miller-Rabin概率性素数检测法提出了一种大素数生成的优化方法,有效地提高了寻找大素数的速度。基于此优化方法,提出了一种新的强素数生成算法,该方法根据强素数的特征,用自顶向下的方法来生成强素数,算法简单、易实现,满足RSA算法安全性的需求。 展开更多

关键词 RSA算法 素数检测 强素数

原文传递

素数判定设计与实现 被引量：4

13

作者 谢日敏 《福建商业高等专科学校学报》 2007年第2期120-123,共4页

本文对素数判定测试算法进行分析,并结合Miller-Rabin测试算法,基于Miracl大数运算库,采用VC++.NET语言实现了Rabin素数测试算法。

关键词 素数定理 FERMAT定理 Rabin-Miller测试法

在线阅读 下载PDF 职称材料

某些形如(b^p+1)/(b+1)的素数

14

作者 皮新明 《数学杂志》 CSCD 1998年第S1期125-128,共4页

设ｂ为大于１的自然数，本文讨论了（ｂｐ＋１）／（ｂ＋１）的基本性质，提出了搜寻这种形式的素数的有效算法，对于３≤ｂ≤１２。

关键词 素数 概素数 素性检验 算法

在线阅读 下载PDF 职称材料

RSA软件实现中的算法研究

15

作者 吴春明 秦建 《农业网络信息》 2006年第8期41-42,46,共3页

RSA是一种被广为使用的公钥加密体制。本文对其软件实现中的相关问题进行了探讨,对素性检验、幂模运算等典型算法进行了总结,最后对RSA进行了展望。

关键词 RSA 素性检验 幂模运算 MONTGOMERY算法

在线阅读 下载PDF 职称材料

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

16

作者 王景中 周靖 《通信技术》 2015年第4期469-472,共4页

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

关键词 素性检测 Miller-Rabin算法 误判率与出错率 素数分布 预处理的局限性 算法底层优化

在线阅读 下载PDF 职称材料

一类强素数的确定与生成

17

作者 肖应雄 张韶华 《孝感学院学报》 2006年第6期59-61,共3页

给出了确定一类素数p是否为强素数的多项式时间算法,其计算量为O(log32p),并给出了生成这类强素数的算法。

关键词 素性检验 强素数 RSA公钥密码体制

在线阅读 下载PDF 职称材料

RSA算法的Java实现 被引量：2

18

作者 田文春 韦岗 《计算机工程与应用》 CSCD 北大核心 2001年第24期43-44,62,共3页

网络服务的丰富,尤其是电子商务的发展,需要强健的密码技术确保安全可靠地传递信息。由于密码技术的敏感性,各国对其都有严格的控制。密码算法的工程实现对商业和军事都有着重要的意义。文章研究了加密强度高的RSA算法工程上实现的关键... 网络服务的丰富,尤其是电子商务的发展,需要强健的密码技术确保安全可靠地传递信息。由于密码技术的敏感性,各国对其都有严格的控制。密码算法的工程实现对商业和军事都有着重要的意义。文章研究了加密强度高的RSA算法工程上实现的关键技术,包括随机数的产生及其随机性对算法安全性的影响,大整数的素性检测等。Java是一种应用广泛的跨平台网络编程语言,适合开发大型分布式系统,因而文中给出了RSA算法的一个Java实现,这对商业应用的开发有着重要的意义。 展开更多

关键词 RSA算法 素数 JAVA语言 密码学 信息安全 INTERNET 网络安全

在线阅读 下载PDF 职称材料

广义Fermat数素性判定问题的几个结论

19

作者 朱玉扬 《合肥学院学报（自然科学版）》 2004年第1期9-10,共2页

给出广义Fermat数F(b,n)=b^2~n+1当(b,3)=1的一(?)充要条件,并探讨F(b,n)素因子的某些规律。

关键词 广义FERMAT数 判定 素数 Pepin检验 素因子

在线阅读 下载PDF 职称材料

基于RSA公钥算法的一种素数检测方法 被引量：1

20

作者 张波 余启港 黄文学 《中南民族大学学报（自然科学版）》 CAS 2006年第4期104-105,共2页

介绍了几种常用的大素数的检测方法,提出了一种基于RSA公钥密码算法的新的素性检测方法,并证明了通过该方法判定素数出错的概率不超过50%,指出了费马素性检测方法是它的一种特例.

关键词 素性检测 RSA公钥算法 伪素数 概率

在线阅读 下载PDF 职称材料