最近研究RSA算法，发现在这个算法里，实现过程中的核心就是求出密钥D，求密钥的公式：
E*D ≡ 1 mod r ，现在已知了E和r，求E即是一个求模的逆元问题。
注：≡是数论中表示同余的符号。公式中，≡符号的左边必须和符号右边同余，也就是两边模运算结果相同。显而易见，不管r取什么值（r是N的欧拉函数值，N是大素数p与q的乘积），符号右边1 mod r 的结果都等于1；符号的左边d与e的乘积做模运算后的结果也必须等于1，即满足 (E*D)/mod r = 1 。
问题：
求A关于模N的逆元B，即要找出整数B，使A * B mod N = 1 （或A * B = x * N + 1），这里要求A与N互素。
方法：
辗转相除法（外向的香水算法）
-该算法原用于求两个数的最大公约数，经过变形可用于求模逆元
首先对余数进行辗转相除：
N = A * a0 + r0
A = r0 * a1 + r1
r0 = r1 * a2 + r2
r1 = r2 * a3 + r3
…
rn-2 = rn-1 * an + rn
rn-1 = rn * an+1 + 0
对上面的商数逆向排列（不含余数为0的商数）：
其中：
b-1 = 1
b0 = an
bi = an-1 * bi-1 + bi-2
如果n为奇数（即商个数为偶数），则bn即为所求的逆元B；
如果n为偶数（即商个数为奇数），则N-bn即为所求的逆元B。
实践一下
求61关于模105的逆。先对余数辗转相除：
105 = 61 * 1 + 44
61 = 44 * 1 + 17
44 = 17 * 2 + 10
17 = 10 * 1 + 7
10 = 7 * 1 + 3
7 = 3 * 2 + 1
3 = 1 * 3 + 0
将商数逆序排列：
由于商的个数为偶数，因此31即为61关于模105的逆元。(31 * 61 = 105 * 18 + 1)
求31关于模105的逆，先对余数辗转相除：
105 = 31 * 3 + 12
31 = 12 * 2 + 7
12 = 7 * 1 + 5
7 = 5 * 1 + 2
5 = 2 * 2 + 1
2 = 1 * 2 + 0
将商数逆序排列：
由于商的个数为奇数，因此105-44=61即为31关于105的逆元。
辗转相除法求模逆元代的码实现 辗转相除法求判断互质 /***************************************************************************************************************** * 辗转相除法， 又名外向的香水算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较小数除较大数， *再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是 *求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数 ——百度百科 *****************************************************************************************************************///Python//这段代码是使用辗转相除法求最大公约数，判断条件为：如果直到n=1才除尽，说明m、n互质，即最大公约数为1#求最大公约数，若最大公约数是1，且m,n>1,m与n不等，则说明m,n互质 def comm_div(m, n): #m>n temp = m % n while(temp != 0): m = n n = temp temp = m % n if n == 1: #说明互质，返回True return True // C语言#include <stdio.h>#include <stdlib.h>int pan_duan_hu_zhi(int* a, int* b){int m,n,temp;m = *a;n = *b;temp = m % n;while(temp != 0){m = n;n = temp;temp = m % n;}return n;}int main(){ int a, b; int Flag = 0; //char ch,*arr,wei='a';printf("请输入a、b值，用空格间隔开n");scanf("%d%d", &a, &b); //从键盘获取a、b值 // 数据整理保证 m > n if(a<b) { Flag = a; a = b; b = Flag; Flag = 0; } Flag = pan_duan_hu_zhi(&a, &b); if(Flag == 1) printf("%d和%d互质n",a,b); else printf("%d和%d的最大公约数为%d",a,b,Flag); getchar(); return 0;} 辗转相除法求模的逆 //Python 代码#用辗转相除法求质数e关于欧拉公式F的逆元def _e_product(e, F): a_list = [] m = F n = e temp = m % n while (temp != 0): a = (m - temp) / n a_list.append(a) m = n n = temp temp = m % n print("a_list:", a_list) a_list.reverse() #逆序 print("a_list_reverse:", a_list) b_list = [] b_list.append(1) b_list.append(a_list[0]) print("(最初插入的两个1及a_list[0])b_list:", b_list) for i in range(len(a_list)-1): b = b_list[-1] * a_list[i+1] + b_list[-2] b_list.append(b) print("b_list", b_list) #a_list存放的是商数，如果商数个数是偶数 b_list[-1]即为所求逆元 #若为奇数，F-b_list[-1]为所求的逆元 if len(a_list) % 2 == 0: #偶数 return b_list[-1] else: return F - b_list[-1] // C代码// 代码写得比较烂，打印信息也不去了，多多包涵>_<#include <stdio.h>#include <stdlib.h>#include <memory.h>//要使用memset是要包含此头文件int _E_Product (int* e, int* F){int i, a, m, n, temp,j,k,D,f;int *p_quotient, *q_remainer, *p_quotient_reverse, *b_list;p_quotient = (int*)malloc(512*(sizeof(int*))); // 存放每轮计算得到的商q_remainer = (int*)malloc(512*(sizeof(int*))); // 存放每轮计算得到的余数p_quotient_reverse = (int*)malloc(512*(sizeof(int*))); // 存放逆序排列后的商b_list = (int*)malloc(512*(sizeof(int*))); // 存放bn的数组memset(p_quotient,0,512); // 擦净内存memset(q_remainer,0,512);memset(p_quotient_reverse,0,512);memset(b_list,0,512); f = *F;// 保存F值，以备后续使用m = *F;n = *e;temp = m % n;printf("m = %d; n = %d; temp = %d n",m,n,temp);i = 0;while(temp != 0){q_remainer[i] = temp;a = (m-temp)/n;p_quotient[i] = a;i++;m = n;n = temp;temp = m % n;}for(j=0;j<i;j++){printf("第%d轮商为%dn",(j+1),p_quotient[j]);printf("第%d轮余数为%dn",(j+1),q_remainer[j]);}//商逆序排列k = i-1; for(j=0;j<i;j++) { p_quotient_reverse[j] = p_quotient[k--]; } printf("逆序后的商序列为：n"); for(j=0;j<i;j++) { printf("%dn",p_quotient_reverse[j]); } //计算bn //插入最初的b0 = 1，及b1 = an 即 b1 = p_quotient_reverse[0] b_list[0] = 1; b_list[1] = p_quotient_reverse[0]; printf("b_list[%d]为：%dn",1,b_list[1]); //迭代计算 for(j=0;p_quotient_reverse[j+1] != 0;j++) { b_list[j+2] = b_list[j+1] * p_quotient_reverse[j+1] + b_list[j]; printf("b_list[%d]为：%dn",(j+2),b_list[j+2]); } printf("b_list完整序列值：n"); for(j=0;j<i+1;j++) { printf("%dn",b_list[j]); } // 判断商的个数决定密钥为bn(偶数个)还是 F-bn（奇数个） if(i%2 == 0) { printf("偶数n"); printf("%dn",j-1); printf("%dn",b_list[j-1]); D = b_list[j-1]; } else { printf("奇数n"); printf("%dn",j-1); printf("%dn",b_list[j-1]); printf("%dn",f); D = f - b_list[j-1]; }free(p_quotient);free(q_remainer);free(p_quotient_reverse);printf("%dn",D);printf("返回密钥...n"); return D;}int main(){ int p, q, e, d, n, fai_n; printf("请输入p、q、e值，用空格间隔开n");scanf("%d%d%d", &p, &q, &e); //从键盘获取p、q、e值n = p*q;printf("N = %dn",n);fai_n = (p-1)*(q-1); //Φ(n)printf("φ(n) = %dn",fai_n);getchar();printf("计算密钥...n");d = _E_Product(&e,&fai_n);printf("密钥计算完成...n");printf("密钥D = %dn",d);getchar();} 后记
由维基百科描述：
计算e对于φ(n)的模反元素d,所谓"模反元素"就是指有一个整数d，可以使得ed被φ(n)除的余数为1。
ed ≡ 1 (mod φ(n))
这个式子等价于
ed - 1 = kφ(n)
那么选定e后，是否可以利用凑数法去凑出来等式：ed - 1 = kφ(n) 的解？找到k，即
for k from 0 increase，judge [(kφ(n) + 1) % e ] == 0 是否成立，当它成立的时候，就找到了k，然后通过
（kφ(n)+1）% e 得到模逆元d，这个与通过辗转相除法求模逆元好理解的多。
但是对于选定了e之后，等式ed - 1 = kφ(n) 的k解是否是唯一的？ 若是不是唯一的，这个方法就出现了漏洞，他仅仅是找到第一个使式子成立的k就结束了。但是反过来讲，若k不唯一，那么d也将是不唯一的，这样会出现对于一个公钥e，私钥d是不唯一的？？？虽然我没有仔细去研究RSA算法的证明，但我觉得对于一个既定公钥e，与之对应的私钥d必定要是唯一的~~~欢迎补充证明 >_<
n = p*q;fai_n = (p-1)*(q-1); //Φ(n)for (k = 0; (k*fai_n + 1) % e != 0; k++);if ((k*fai_n + 1) % e == 0)d = (k*fai_n + 1) / e;
算数基本定理：任何大于1的整数都可以分解成素数乘积的形式，并且，如果不计分解式中素数的次序，该分解式是唯一的[微软中国1]。
由算数基本定理可知，整数分解为素数乘积的形式唯一，那么可以不用使用辗转相除法求密钥D了！！！