擴展歐幾里德演算法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。請編譯運行通過，謝謝啦

這是一個錯誤的演算法啊