歐幾裡得算法和擴充的歐幾裡得算法C++遞歸實作

關于歐幾裡得算法的流程不再贅述，不清楚的可以搜得到。本篇主要通過C++代碼利用遞歸的思想實作，參考書籍是《密碼編碼與資訊安全:C++實踐》。

1、歐幾裡得算法實作

歐幾裡得算法比較簡單，主要用于求兩個數(多項式)的最大公因數(式)，直接上代碼。

#include <iostream>
using namespace std;
int Euclidean(int a, int b){
	if(b==0){
		return a;
	}else{
		return Euclidean(b, a%b);
	}
}
           

2、擴充的歐幾裡得算法實作

擴充的歐幾裡得算法主要用于求模逆運算。我第一次實作擴充的歐幾裡得算法是通過輾轉相除，然後再回溯求出了 a a a和 b b b的系數。感覺可以像普通歐幾裡得算法一樣可以遞歸程式設計，但是總是沒想出來。後來借助參考書實作了。主要思想是要寫出此時的遞推關系式。

2.1遞推關系式的說明

擴充歐幾裡得算法本質上是要求得

a × s + b × t = g c d a\times s+b\times t=gcd a×s+b×t=gcd

這個式子。按照遞歸的思想，我們應該這麼考慮：要利用遞歸得到 a a a和 b b b的式子，結合輾轉相除的原理，我們肯定是先得到 b b b和 a ( m o d b ) a\pmod b a(modb)的關系式。假設已經有了

s ′ × b + t ′ × ( a ( m o d b ) ) = g c d s'\times b+t'\times (a\pmod b)=gcd s′×b+t′×(a(modb))=gcd

如何得到我們需要的式子？

做一個簡單的變形就出來了：我們知道 a ( m o d b ) = a − ⌊ a / b ⌋ ∗ b a\pmod b=a-\lfloor a/b\rfloor *b a(modb)=a−⌊a/b⌋∗b，代進上式，有

s ′ × b + t ′ × ( a ( m o d b ) ) = s ′ × b + t ′ × ( a − ⌊ a / b ⌋ ∗ b ) = t ′ × a + ( s ′ − t ′ × ⌊ a / b ⌋ ) × b = g c d s'\times b+t'\times (a\pmod b)=s'\times b+t'\times (a-\lfloor a/b\rfloor *b)\\ =t'\times a+(s'-t'\times \lfloor a/b\rfloor)\times b =gcd s′×b+t′×(a(modb))=s′×b+t′×(a−⌊a/b⌋∗b)=t′×a+(s′−t′×⌊a/b⌋)×b=gcd

是以遞歸就是根據這個式子編出的。具體代碼如下：

#include <iostream>
using namespace std;
struct ExtEuc
{
	int gcd;
	int s;
	int t;
};
//the most important is the "recursion formula"，especially in Extends_Eclidean
ExtEuc Extends_Eclidean(int a, int b){
	ExtEuc obj, obj1;
	if(b == 0){
		obj1.gcd = a;
		obj1.s = 1;
		obj1.t = 0;
		return obj1;
	}
	obj1 = Extends_Eclidean(b, a%b);
	//attention!!
	obj.gcd = obj1.gcd;
	obj.s = obj1.t;
	obj.t = obj1.s - (a/b)*obj1.t;
	return obj;
}
           

3、整體代碼如下

#include <iostream>
using namespace std;
struct ExtEuc
{
	int gcd;
	int s;
	int t;
};

//the most important is the "recursion formula"，espeacially in Extends_Eclidean
int Euclidean(int a, int b){
	if(b==0){
		return a;
	}else{
		return Euclidean(b, a-(a/b)*b);
	}
}

ExtEuc Extends_Eclidean(int a, int b){
	ExtEuc obj, obj1;
	if(b == 0){
		obj1.gcd = a;
		obj1.s = 1;
		obj1.t = 0;
		return obj1;
	}

	obj1 = Extends_Eclidean(b, a%b);
	//attention!!
	obj.gcd = obj1.gcd;
	obj.s = obj1.t;
	obj.t = obj1.s - (a/b)*obj1.t;
	return obj;
	
}

int main(int argc, char const *argv[])
{
	/* code */
	ExtEuc f = Extends_Eclidean(2,3);
	cout<<f.s<<"*2+"<<f.t<<"*3="<<f.gcd<<"  "<<endl;
	return 0;
}
           

[1] 王靜文, 吳曉藝. 密碼編碼與資訊安全:C++實踐[M]. 清華大學出版社, 2015.