扩展欧几里得算法

        给予二整数 a 与 b, 必存在有整数 x 与 y 使得  ax + by = gcd(a,b)  。

       有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。

1、算法原理

        给定整数a、b，若gcd(a,b)=1。则存在c，满足ac=1 mod b，c即为a模b的乘法逆元。

       利用扩展的欧几里得算法求得满足条件的c：先做辗转相除，当a、b互素时，最后一步得到的余数为1，再从1出发，对前面得到的所有除法算式进行变形，将余数用除数和被除数表示，最终便可将1表示为a与b的一种线性组合，即

       从而x就是a模b的乘法逆元。因此寻找乘法逆元的过程就是求x和y的过程。 

       这里我们先看一下人工计算的过程：

       具体实现时使用三组变量：x1，x2，x3；y1，y2，y3；t1，t2，t3。初始化时，给x1，x2，x3别赋值1、0、a，则有

1 × a + 0 × b = a

       类似地，给y1，y2，y3分别赋值0、1、b，有

0 × a + 1 × b = b

       接下来开始迭代，保证在每次迭代中，有

a × t1 + b × t2 = t3

成立。为此只需在每一步中为 ti 分别赋值  (i=1,2,3) ，其中q为x3除以y3的商。

       当最后t3迭代至计算结果为1时，相应的 t1 就是 a模b的乘法速元，而 t2 是b模a的乘法逆元。

2、代码部分

#include <stdio.h>
int main(int argc, char *argv[])
{
	int temp,q,t1,t2,t3;
	int a,b,swap=0;
	int x1,x2,x3,y1,y2,y3;
	printf("Input two integers: ");
	scanf("%d",&a);
	scanf("%d",&b);
	if (a<b) {   //保证a>b
		swap = 1;
		temp = a;
		a = b;
		b = temp;		
	}
	x1=1;	x2=0;	x3=a;    // 初始
	y1=0;	y2=1;	y3=b;
	while (y3!=0)
	{
		q=x3/y3; //商
		t1=x1-q*y1;	t2=x2-q*y2;	t3=x3-q*y3;
		x1=y1;		x2=y2;		x3=y3;
		y1=t1;		y2=t2;		y3=t3;
		printf("\nt1,t2,t3\t%d\t%d\t%d ;",t1,t2,t3);	
	}
	printf("\n");
	if(x3 == 1)   // 这里使用x3，组后一轮循环中，x3保存了上一步中值为1的t3
	{
		if(swap==1)
		{
			printf("\ninverse of %d mod %d is:%d",b,a,x2);
			printf("\ninverse of %d mod %d is:%d",a,b,x1);		
		}
		else{
			printf("\ninverse of %d mod %d is:%d",a,b,x2);
			printf("\ninverse of %d mod %d is:%d",b,a,x1);	
		}			
	}
	else  printf("no inverse");
	printf("\n\n\n");
	return 0;
}

注释：

       关于判断条件是  x3==1，而不是 t3==1 的问题，while循环中本质使用的是辗转相除法，对于 ti 的赋值表达式，先看t3，t3=x3-q*y3 ，q=x3/y3 ，我理解的是 t3 就是 x3除以y3的余数，加上开始时,给 x3=a，y3=b ，所以对t3的迭代可以看成对 （a,b）做辗转相除法。

      再看 t1 和 t2，为了保持线性关系ax + by = gcd(a,b)，相应的x和y的值也需要变化，这就是 t1 和 t2 的作用。

模逆运算（C语言）

简介

使用扩展欧几里得算法

代码实现

#include <stdio.h>

int main()
{
    int temp,q,t1,t2,t3,i=1;
    int a,b,swap=0;
    int x1,x2,x3,y1,y2,y3;
    /**欢迎**/
    printf("--------欢迎使用模逆运算-----------\n");
    printf("请输入两个整数，以空格分开\n");
    scanf("%d",&a);
    scanf("%d",&b);
    if(a<b){  //交换a，b
        swap = 1;
        temp = a;
        a = b;
        b = temp;
    }
    x1=1;x2=0,x3=a;
    y1=0;y2=1,y3=b;
    while(y3 != 0){
        q = x3/y3;
        t1=x1-q*y1;t2=x2-q*y2;t3=x3-q*y3;
        x1=y1;x2=y2;x3=y3;
        y1=t1;y2=t2;y3=t3;
        printf("第%d次迭代，t1=%d,t2=%d,t3=%d\n",i,t1,t2,t3);  //打印迭代的值
        i++;
    }
    if(x3 == 1){
        if(swap == 1){
            printf("模逆运算：%d mod %d 为：%d\n",b,a,x2);
            printf("模逆运算：%d mod %d 为：%d\n",a,b,x1);
        } else{
            printf("模逆运算：%d mod %d 为：%d\n",a,b,x2);
            printf("模逆运算：%d mod %d 为：%d\n",b,a,x1);
        }
    } else{
        printf("无法进行模逆运算！");
    }
    return 0;
}

博主是初学初等数论（整除+同余+原根），本意是想整理一些较难理解的定理、算法，加深记忆也方便日后查找；如果有错，欢迎指正。
我整理成一个系列：初等数论，方便检索。

同余方程：$ax\equiv b(modm)$

• 模逆运算：若$(a,m)=1,$那么由上一章信息安全数学基础–同余方程–同余方程的解证明的“同余方程$ax+b\equiv 0(modm)$的解个数为$(a,m)$”得，同余方程$ax\equiv b(modm)$的解个数为$(a,m)$。
  $ax\equiv b\to x\equiv a^{-1}b(modm)$
  进行模逆运算，求$a^{-1}(modm)$,即求方程$ax\equiv 1(modm)$的解,$\to ax=1+km\to ax-km=1\leftrightarrow ax+my=1$，运用欧几里得算法/辗转相除法 求$x$。

• 模指数运算：若$(a,m)=1,$那么由欧拉定理知$a^{\phi (m)}\equiv 1(modm)$,那么$ax\equiv b\to x\equiv a^{-1}b\to x\equiv a^{\phi (m)-1}b(modm)$
  进行模指数运算，求$a^n(modm)$
  $$\begin{gathered} n=n_k\cdot 2^k+n_{k-1}\cdot 2^{k-1}+\dots \dots +n_1\cdot 2^1+n_0\cdot 2^0 \\ {a}^n=a^{n_k\cdot 2^k+n_{k-1}\cdot 2^{k-1}+\dots \dots +n_1\cdot 2^1+n_0\cdot 2^0} \\ =(a^{n_k}{)}^2\cdot a^{n_{k-1}}{)}^2\dots \dots a^{n_1}{)}^2\cdot a^{n_0} \end{gathered}$$