最近研究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值，用空格间隔开 "); 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互质 ",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 ",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轮商为%d ",(j+1),p_quotient[j]); printf("第%d轮余数为%d ",(j+1),q_remainer[j]); } //商逆序排列 k = i-1; for(j=0;j<i;j++) { p_quotient_reverse[j] = p_quotient[k--]; } printf("逆序后的商序列为： "); for(j=0;j<i;j++) { printf("%d ",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]为：%d ",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]为：%d ",(j+2),b_list[j+2]); } printf("b_list完整序列值： "); for(j=0;j<i+1;j++) { printf("%d ",b_list[j]); } // 判断商的个数决定密钥为bn(偶数个)还是 F-bn（奇数个） if(i%2 == 0) { printf("偶数 "); printf("%d ",j-1); printf("%d ",b_list[j-1]); D = b_list[j-1]; } else { printf("奇数 "); printf("%d ",j-1); printf("%d ",b_list[j-1]); printf("%d ",f); D = f - b_list[j-1]; } free(p_quotient); free(q_remainer); free(p_quotient_reverse); printf("%d ",D); printf("返回密钥... "); return D; } int main() { int p, q, e, d, n, fai_n; printf("请输入p、q、e值，用空格间隔开 "); scanf("%d%d%d", &p, &q, &e); //从键盘获取p、q、e值 n = p*q; printf("N = %d ",n); fai_n = (p-1)*(q-1); //Φ(n) printf("φ(n) = %d ",fai_n); getchar(); printf("计算密钥... "); d = _E_Product(&e,&fai_n); printf("密钥计算完成... "); printf("密钥D = %d ",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了！！！