c实现的求两个数的乘法逆元

定义：设a对b的乘法逆元是x则可以记为a*x=1 mod b，即a和x的积除以b的余数是1；
 
乘法逆元常用算法是欧几里德算法：
 
//算法求d关于模f的乘法逆元d-1 ，即 d* d-1 mod f = 1
 
　　1 。(X1，X2，X3) := (1，0，f)； (Y1，Y2，Y3) := (0，1，d)
　　2。 if (Y3=0) then return d-1 = null //无逆元
　　3。 if (Y3=1) then return d-1 = Y2 //Y2为逆元
　　4。 Q := X3 div Y3 //整除
　　5。 (T1，T2，T3) := (X1 - Q*Y1，X2 - Q*Y2，X3 - Q*Y3)
　　6 。(X1，X2，X3) := (Y1，Y2，Y3)
　　7。 (Y1，Y2，Y3) := (T1，T2，T3)
8。 goto 2
 
常用于加密算法中，如仿射算法。
 
采用扩展欧几里德算法
 
首先,欧几里德算法又称辗转相除法,用于求最大公约数,算法如下:
int Gcd(int a, int b)
{
    if(b == 0)
        return a;
    return Gcd(b, a % b);
}
 
求一个数对另一个数的乘法逆元算法如下：
Typedef unsigned short int uint16；
uint16 mulinv(uint16 b，uint16 a)      //求一个整数b对a的乘法逆元
{
    int x1,x2,x3;
    int y1,y2,y3;
    int t1,t2,t3;
    x1=1;
    x2=0;
    x3=a;
    y1=0;
    y2=1;
    y3=b;
    int k;
    for(t3=x3%y3;t3!=0;t3=x3%y3){
        k=x3/y3;
        t2=x2-k*y2;
        t1=x1-k*y1;
        x1=y1;
        x2=y2;
        x3=y3;
        y1=t1;
        y2=t2;
        y3=t3;
    } 
    if(y2<0)
        y2+=a;
    if(y3==1)
        retu