本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
算法(第4版)
知识点
- 公钥
- 私钥
- 欧拉定理
- 欧几里得算法
- 模反元素
- RSA加密
我们已经做了一些算法习题了，这次的文章就不讲新的算法了，而是讲算法的一个实际使用：欧几里得算法。
在算法练习(4):二分法查找中我们已经介绍了欧几里得算法，并使用欧几里得算法计算了两个整数的最大公约数。
RSA算法是计算机世界最重要的算法，它是计算机通信安全的基石,因为任何用到加解密的地方都会用到RSA算法。它的原理就是通过两个互质的数来分别作为公钥和私钥(暂时这么理解)加解密实现。
Java的实现如下：
//例子为算47 * x + 30 * y ==1 的解
public class Exercise
{
public static void main(String[] args)
{
int[] p = new int[2];
int a = 47;
int b = 30;
RSA(a,b,p);
System.out.print("p[0] is: " + p[0] + ";p[1] is：" + p[1]);//p1为私钥
}
public static int[] RSA(int a,int b,int[] p)//这里假设a > b
{
if(a%b == 1)
{
p[0] = 1;
p[1] = -(a - 1) / b;
return p;
}
else
{
RSA(b,a % b,p);
int t = p[0];
p[0] = p[1];
p[1] = t - (a / b) * p[1];
return p;
}
}
}
广告
我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。
