扩展欧几里德算法c

‘壹’ 倒水问题解题方法

问题：假设你有一个3升的容器和一个5升的容器（以及充足的水源），如何精确地取出4升水来？（为了下文叙述的方便，我们不妨把3升的容器和5升的容器分别记做容器A和容器B）。这里提供一种解法：

即求解 3xmod5=43xmod5=4，使用 扩展欧几里得算法及其应用 一文的算法我们可轻易解得 x=3x=3。首先根据扩展欧几里得算法，问题有解。x=3x=3 时，对应的解决方案见上文。

接着看 7 升 13 升得 5 升，也即 7xmod13=57xmod13=5，7,137,13 互质，首先判断有解，即存在这样一个解决方案。这个方案是怎样的呢？

第一步，首先来看贝祖等式时的情况，也即 7xmod13=17xmod13=1时，此时解得 x=2x=2，也即 2 个 A 倒入 B，A余一升（得1升）

第二步，7xmod13=57xmod13=5，此时 x=(2×5)%13=10x=(2×5)%13=10，也即对第一步的行为执行五次，如下：

将装满 7 升水的 A 倒入 B ⇒ A（0升），B（7升）

将装满7升水的 A 倒入 B，直到 B 加满为止 ⇒ A（1升），B（13升）

将 B 清空，⇒ A （1升），B（0升）

将 A 中的一升水倒入 B，⇒ A（0升），B（1升）（1,2,3,4 步为一个单元）

将 A 加满倒入 B，⇒ A（0升），B（8升）

再次将 A 加满倒入 B，直到 B 满为止，⇒ A（2升），B（13升）

将 B 清空，⇒ A（2升），B（0升）

将 A 中的 2 升水倒入 B，⇒ A（0升），B（2升）

直到 A（5升），B（0升）；

我们进一步将问题抽象，用容积分别为 aa 和 bb 的水杯量出体积为 cc 的水，实际上相当于求解方程 a⋅xmodb=ca⋅xmodb=c。如果 a,ba,b 互质，问题保证有解。

如果 c==gcd(a,b)c==gcd(a,b) 或者 c==k⋅gcd(a,b)c==k⋅gcd(a,b)，用扩展欧几里得算法便可求解 xx，然后得最终的量水方案。如果 cc 不能被 gcd(a,b)gcd(a,b) 整除，方程无解，也即问题无解，比如9升15升的容器得10升的水，1010 不能被 gcd(9,15)=3gcd(9,15)=3 整除。

‘贰’ 如何用C语言实现RSA算法

上学期交的作业，已通过老师在运行时间上的测试
#include <stdio.h>
#include <stdlib.h>

unsigned long prime1,prime2,ee;

unsigned long *kzojld(unsigned long p,unsigned long q) //扩展欧几里得算法求模逆
{
unsigned long i=0,a=1,b=0,c=0,d=1,temp,mid,ni[2];
mid=p;
while(mid!=1)
{
while(p>q)
{p=p-q; mid=p;i++;}
a=c*(-1)*i+a;b=d*(-1)*i+b;
temp=a;a=c;c=temp;
temp=b;b=d;d=temp;
temp=p;p=q;q=temp;
i=0;
}
ni[0]=c;ni[1]=d;
return(ni);
}

unsigned long momi(unsigned long a,unsigned long b,unsigned long p) //模幂算法
{
unsigned long c;
c=1;
if(a>p) a=a%p;
if(b>p) b=b%(p-1);
while(b!=0)
{
while(b%2==0)
{
b=b/2;
a=(a*a)%p;
}
b=b-1;
c=(a*c)%p;
}
return(c);
}

void RSAjiami() //RSA加密函数
{
unsigned long c1,c2;
unsigned long m,n,c;
n=prime1*prime2;
system("cls");
printf("Please input the message：\n");
scanf("%lu",&m);getchar();
c=momi(m,ee,n);
printf("The cipher is：%lu",c);
return;
}

void RSAjiemi() //RSA解密函数
{
unsigned long m1,m2,e,d,*ni;
unsigned long c,n,m,o;
o=(prime1-1)*(prime2-1);
n=prime1*prime2;
system("cls");
printf("Please input the cipher：\n");
scanf("%lu",&c);getchar();
ni=kzojld(ee,o);
d=ni[0];
m=momi(c,d,n);
printf("The original message is：%lu",m);
return;
}

void main()
{ unsigned long m;
char cho;
printf("Please input the two prime you want to use:\n");
printf("P=");scanf("%lu",&prime1);getchar();
printf("Q=");scanf("%lu",&prime2);getchar();
printf("E=");scanf("%lu",&ee);getchar();
if(prime1<prime2)
{m=prime1;prime1=prime2;prime2=m;}
while(1)
{
system("cls");
printf("\t*******RSA密码系统*******\n");
printf("Please select what do you want to do:\n");
printf("1.Encrpt.\n");
printf("2.Decrpt.\n");
printf("3.Exit.\n");
printf("Your choice:");
scanf("%c",&cho);getchar();
switch(cho)
{ case '1':RSAjiami();break;
case '2':RSAjiemi();break;
case '3':exit(0);
default:printf("Error input.\n");break;
}
getchar();
}
}

‘叁’ 拓展欧几里得算法(Extended Euclidean)

作为一只码农每当学习个新知识尤其是数学知识时。我觉得最好得搞清楚它是为了解决一个什么问题。欧几里得算法是为了求两个数的最大公约数 Greatest Common Divisor 后文都以 gcd 简称，而拓展欧几里得算法则可以帮助我们求出倒数的模 如果对这个写法不太熟悉，我们换一种表示就是——已知两个正整数a和n，我们想求一个数e使得a与e的乘积除以n的余数为1。而在大名鼎鼎的RSA算法中就有这样一步需要求倒数的模，并且还多加了一个限制条件即a与n互质。

拓展欧几里得(简称EEA) 人如其名是基于欧几里得算法(EA) 的，那么我们来回顾下小学所学怎么求两个数m,n的最小公约数 如果这个公式还没勾起你的回忆，那么我们来一段计算过程吧。这里我们求39和69的最大公约数

实话说，小时候学只是机械式地记得这个操作。但当看到EA的表达式后发现写作 能够更好地理解它的本质。

一句话为了概括EEA就是求两个数 和 使得

在具体讲怎么求 , 之前我想先介绍为什么它能让我们求得倒数的模。如前面提到的A，B两数互质的情况下我们有 而我们要求的是 所以对等式两边对A取余

下面我们来讲讲怎么一步一步地来求 , 。改写前面求39和69公约数的式子并令

归纳总结，为了求 我们需要 和

所以我们有

其中初始的 这点我们可以当 时 来验证

‘肆’ 用c语言编写扩展欧几里德算法用来求乘法逆元ab=1 mod(n) 要求我输入b，n，求出a。请编译运行通过，谢谢啦

这是一个错误的算法啊