#|扩展Euclid算法/欧几里得算法，RSA算法求解d 学习笔记|网络安全技术及应用

扩展Euclid算法(欧几里得算法) /?ju:klid/ ：找出两个整数x，y满足：xa+yb=1
为了使x和y存在，a和b的最大公约数必须是1（即a和b互为素数）。
例子：找出x和y，使得51x+100y=1

u	x	y	q
100	0	1
51	1	0	100/51=1
49	0-1*1= -1	1-0*1= 1	51/49=1
2	1-(-1)*1=2	0-1*1=-1	49/2=24
1	-1-2*24=-49	1-(-1)*24=25	2/1=2
0	100	-51

注解：
第一二行：x，y值是固定的模板，只能这样写；第一行中的u值是100和51中较大的那个。
第一个q 是100除以51取商，值是1。第三个u值是100除以51取余，值是49。
第三行第二个数 = 第一行的x - 第一行的y×1 = 0-1×1
————这里乘的1就是上一行的q值，剩下的0、1是第一行的x，y。
第三行第三个数=1-0*1————1、0是第二行的x，y
51除以49商1余2：第四行第二个数=1-（-1) ×1，第三个数：0-1×1——这里乘的1就是上一行的q值，黄色标注的1,0是第二行的x，y值。
总结：
X的值 = 前两行的x 减去（前一行的x 乘以前一行的q）
Y的值 = 前两行的y 减去（前一行的y 乘以前一行的q）
所以，51X(-49)+100X25=1
最后一行是为了检验有没有算对
将此算法应用到 RSA算法求解d中：例子：找出d和(-k),满足3d+40(-k)=1
【#|扩展Euclid算法/欧几里得算法，RSA算法求解d】