-
-
[求助]RSA算法中寻找互质数的计算
-
发表于:
2009-7-15 09:40
5093
-
RSA定理
若P和Q是两个相异质数，另有正整数R和M，其中M的值与( P - 1 )( Q - 1 )的值互质，并使得( RM ) mod ( P - 1 )( Q - 1 ) = 1。有正整数A，且A < PQ，设C = AR mod PQ，B = CM mod PQ则有：A = B
参考上面定理，用Java完成了一个简易程序如附件中所示
该程序能够通过测试，但是是在一些问题被我规避的情况下，其中包括:
1. 两个1024位的大素数的生成(这个可以用BigInteger.probablePrime(1024, new Random())完成)
2. 还有M值的寻找(即互质数生成)，由于M与(P-1)*(Q-1)互质，故只需要找出一个M，其与(P-1)*(Q-1)的最大公约数为1，但是这一步我找不到一个有效的算法来实现
3. 即上面代码段中标记为HERE的部分，求解R的过程，看过一些参考资料说可以用 辗转相除法算，但是并不了解该过程，就用枚举代替了
想请问大家，有没有比较好的方法可以解决2，3中的问题，谢谢了
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
