请教RSA算法中的大素数选取问题
答案:2 悬赏:30
解决时间 2021-01-14 10:20
- 提问者网友：泪痣哥哥
- 2021-01-13 18:20
请教RSA算法中的大素数选取问题
最佳答案
- 二级知识专家网友：像个废品
- 2021-01-13 19:56
寻找用什么办法得到素数的问题一直是业界关注的，建议你看看eurocrypt的会议资料，有很多。有一本书叫做Handbook of Applied Cryptography，在http://www.cacr.math.uwaterloo.ca/hac/ 可以免费下载。对于楼下的几点错误应指出的是，在RSA算法中，本身不存在所谓的RSA算法中的素性检测算法。Prime generator本身就是一个比较复杂的问题。用于生成大素数的软件有很多，而且有很多是开放源代码的，比如maple，如果想自己实现，可供参考。能通过素性检测的数不都是素数，但是素数一定能通过素性检测。我的研究生论文是研究Large RSA moduli的，有问题随时问
The big primes in RSA algorithm should be of same length, and co-prime. You can write a code which generates primes from 2,3,5,7.... until the bits you specified.
For example, you want to generate a prime which is of length 15 bits, just generate a prime which is larger than 2^15.
the pseudocode will be as followed:
int prime[MAX_INT],flag;
prime[0] = 2;
prime[1] = 3;
prime[2] = 5;
count = 3;
i = 7;
while ( i < 2^b) {
flag = 0;
for (j = 0, j
else {flag = 0;break;}
};
if (flag==1) {prime[count]=i;count++};
i++;
}
sorry for not being able to type Chinese, any questions, do not hesitate to ask me.
The big primes in RSA algorithm should be of same length, and co-prime. You can write a code which generates primes from 2,3,5,7.... until the bits you specified.
For example, you want to generate a prime which is of length 15 bits, just generate a prime which is larger than 2^15.
the pseudocode will be as followed:
int prime[MAX_INT],flag;
prime[0] = 2;
prime[1] = 3;
prime[2] = 5;
count = 3;
i = 7;
while ( i < 2^b) {
flag = 0;
for (j = 0, j
else {flag = 0;break;}
};
if (flag==1) {prime[count]=i;count++};
i++;
}
sorry for not being able to type Chinese, any questions, do not hesitate to ask me.
全部回答
- 1楼网友：英雄的欲望
- 2021-01-13 21:09
代码很复杂
基本思路:
因为512/1024位已经远大于C中的预设整数范围,必须使用高精度的方法,即用整型数组来表示一个大数的每一位数字,如果用面向对象来设计,可以写一个大整数的类,类中定义大整数的+,-,*,/,取模,等运算
然后随机生成一个512/1024位的大整数,使用RSA算法中的专门素性检测算法来测试该数是否为素数(不是那种通常的判断是否一个数是否含约数的方法来判断素数,那样会慢死的)
通过素性检测的数就可以了
建议弄懂RSA算法中素性检测算法以及了解高精度编程后再写代码
基本思路:
因为512/1024位已经远大于C中的预设整数范围,必须使用高精度的方法,即用整型数组来表示一个大数的每一位数字,如果用面向对象来设计,可以写一个大整数的类,类中定义大整数的+,-,*,/,取模,等运算
然后随机生成一个512/1024位的大整数,使用RSA算法中的专门素性检测算法来测试该数是否为素数(不是那种通常的判断是否一个数是否含约数的方法来判断素数,那样会慢死的)
通过素性检测的数就可以了
建议弄懂RSA算法中素性检测算法以及了解高精度编程后再写代码
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息！
大家都在看
推荐信息