其实，一直就想写这篇博客的，因为上次在写RSA程序，我看了网上的资料都不够简洁，有的提到了方法，但是代码却不够简便，例如欧几里得扩展算法的矩阵形式，以及商的倒序求逆，方法众多，但是代码实现却感觉有点复杂。况且我也看了前人的博客，需要开辟空间对商进行存储。这次我就把我目前感觉最简单的求模逆方法分享给大家~有错误请大家多多指出！

问题：

求e关于模p的逆元d，即要求出整数d，使e * d mod p = 1 （或 ed+px=1），这里要求e与p互素。

方法：

这里是引用初等数论（严士健 第三版）第27页的辗转相除法的表格形式的辗转相除法。

首先我们先要引入概念：
对于二元一次不定方程的求解：
即 ax+by=1的求解方法，

ax+by=1,(a,b)=1
a=bq₁ + r ₁ , 0<r₁ <b,
b=r₁q₂ + r ₂ , 0<r₂ <r₁ ,
……
r_n-2 =r_n-1 q_n + r_n , 0<r_n <r_n-1 ,
r_n-1 =r_n q_n+1 .

因为（a,b）=1,故r_n =1
于是有 a[(-1)^n-1Q_n ]+b[(-1)ⁿP_n ]=1
P₀ =1 , P₁ =q₁ ,P_k =q_k P_k-1 +P_k-1 ,
Q₀ =0 , Q₁ =1,Q_k =q_k Q_k-1 +Q_k-1 ,
k=2,…,n.

由于我时间不是很多，我就不举具体例子了，直接上代码，代码思想就是我所列举的辗转相除法思想，具体证明过程有兴趣的朋友可以参考：《初等数论》(第三版）作者：闵嗣鹤 严士健
第一章ξ3定理1的证明过程 以及 第二章ξ1定理2的证明过程

代码：

我们先判断互质，互质的判断方法我所知道的有三种，纳筛法，miller-素性检验，暴力求解，miller-素性检验和纳筛法由于我的实验报告被我清理文件的时候删了，我就用我同学的暴力求解法

//判断n是否为素数，此处使用最暴力的方法，将n取余小于n的所有值
void searchprime(int n)
{
	   int i;
	   for(i=2;i<=n-1;i++)
	   {
		   if(n%i==0)
			   break;
	   }//将小于n的数依次除n，若可以整除，则不是素数，退出循环
       if(i<n-1)
		  printf("%d不是素数\n",n);
	   else
		  printf("%d是素数\n",n);
}

然后我们进行求逆操作

//模逆运算，用模逆算法，此处编写程序时候u,v为实际计算过程中v的各个值
int mod_invese(int d,int n)//求d模n的逆，n 为正整数
{
    int a,b,q,r,u=0,v=1,t;//a为被除数，b为除数，q为商
    a=n;
    b=(d>=0)?(d%n):-(d%n);//规定正负数mod（n）都取正；
    while(b!=0)
	{
        q=(int)a/b;
        r=a-b*q;
        a=b;
        b=r;
        t=v;
        v=u-q*v;
        u=t;//把每次没有进行运算的v的值给u
	}//辗转相除，直到余数b=0，跳出循环
    if(a!=1) return 0;
    return((u<0)?u+n:u);//返回的值都是mod(n)后的值，使得最后的值是正数；
}