[问题] 想实作RSA,如何随机产生大质数？ yuci PTT批踢踢实业坊

楼主: yuci (vu03) 2016-01-19 00:31:40

最近想实作一次RSA，我使用C++开发，
预期是可以产生不限位数的金钥，
目前大数运算都已经实作好了
就只差不知道如何找（产生）质数
在网络上看到的都是比较小位数的找法
想请问有没有一些general rule可以产生大质数？谢谢

作者: a29813287 (ShyanWang) 2016-01-19 00:50:00

random大数以后再去做质数测试

作者: laladeer (laladeer) 2016-01-19 01:44:00

好像几个质数相乘减一可以变成质数？

作者: LPH66 (-6.2598534e+18f) 2016-01-19 02:09:00

实务上做法都是一楼讲的那样, 那因为测质数的方法里目前常见的是 Miller-Rabin 这种机率式测试法有机会(虽然可以任意小)让非质数通过要实作的话要稍微注意这一点, 控制一下通过的机率(喔, 我指的是大数的质数测试, 因为显然不可能用试除)

楼主: yuci (vu03) 2016-01-19 20:14:00

谢谢大家，我本来是想问有没有公式直接产生，看来只能用删

作者: janice001 (真理) 2016-01-23 12:00:00

补充一下二楼说的做法是强质数的做法，这样方法产生出来的质数被一些学者认为相对比较难破

继续阅读