实验三：求模逆算法

一、实验目的

理解、掌握求模逆算法的基本过程。

二、实验内容

1. 熟悉扩展欧几里德算法。
2. 利用扩展欧几里德算法求模逆，要求：任意输入两个整数a,m；输出a-1mod m;当模逆不存在时，输出出错提示。

三、求模逆算法基本原理

四、实验过程

        1、使用扩展欧几里得算法的关键代码

套用公式即可

        2、使用费马小定理的快速幂算法的关键代码

使用快速幂计算出即可

五、实验结果

分别输入 a和m计算出a模m的逆元

（左侧是欧几里得算法得到的结果，右侧是费马小定理计算出来的结果。）

费马小定理只能适用于m为质数的情况，适用范围比欧几里得算法小，是a和m互质的一种特殊情况。欧几里得算法只需要a和m互质就可以求出模逆。

扩展欧几里得算法

        给予二整数 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 的作用。

欧几里得算法说明

欧几里得（Euclid）算法是用来求两个整数的最大公约数。
详细数学描述参考：
http://www.360doc.com/content/19/0314/18/53810907_821492777.shtml

代码示例

# calculate the gcd(a,b) using euclid algorithm
def gcd_euclid(*p):

    (a,b) = p
    if isinstance(a,int) == False or isinstance(b,int) == False:
        print("Integer input error occured...")
        return False
    print((a,b))
    if b == 0:
        return a
    else:
        return gcd_euclid(b, divmod(a,b)[1])

运行效果

print(gcd_euclid(*(15,12)))

得到结果：

(15, 12)
(12, 3)
(3, 0)
3

print(gcd_euclid(*(15.1,12)))

得到结果：

Integer input error occured...
False

总结

1、用递归算法可以非常简洁的描述推导过程；
2、考虑到递归的返回参数问题，使用tupple，进行传参和解析；
3、python不支持三元计算符？：，只能用if else 来表示逻辑；
4、divmod（a,b）会返回一个tupple，要做处理，否则递归时参数有问题。
5、a>b