歐幾裡得算法:數學計算法-中文百科頻道

算法簡介

歐幾裡得算法是用來求兩個正整數最大公約數的算法。古希臘數學家歐幾裡得在其著作《The Elements》中最早描述了這種算法,所以被命名為歐幾裡得算法。

擴展歐幾裡得算法可用于RSA加密等領域。

假如需要求 1997 和 615 兩個正整數的最大公約數,用歐幾裡得算法，是這樣進行的：

1997 / 615 = 3 (餘 152)

615 / 152 = 4(餘7)

152 / 7 = 21(餘5)

7 / 5 = 1 (餘2)

5 / 2 = 2 (餘1)

2 / 1 = 2 (餘0)

至此，最大公約數為1

以除數和餘數反複做除法運算，當餘數為 0 時，取當前算式除數為最大公約數，所以就得出了 1997 和 615 的最大公約數 1。

計算證明

其計算原理依賴于下面的定理：

定理：兩個整數的最大公約數等于其中較小的那個數和兩數相除餘數的最大公約數。最大公約數（Greatest Common Divisor）縮寫為GCD。

gcd(a,b) = gcd(b,a mod b) (不妨設a>b 且r=a mod b ,r不為0)

證法一

a可以表示成a = kb + r（a，b，k，r皆為正整數，且r

假設d是a,b的一個公約數，記作d|a,d|b，即a和b都可以被d整除。

而r = a - kb，兩邊同時除以d，r/d=a/d-kb/d，由等式右邊可知m=r/d為整數，因此d|r

因此d也是b,a mod b的公約數。

因(a,b)和(b,a mod b)的公約數相等，則其最大公約數也相等，得證。

證法二

假設c = gcd(a,b),則存在m,n，使a = mc, b = nc;

令r = a mod b，即存在k，使r = a-kb = mc - knc = (m-kn)c;

故gcd(b,a mod b) = gcd(b,r) = gcd(nc,(m-kn)c) = gcd(n,m-kn)c;

則c為b與a mod b的公約數;

假設d = gcd(n,m-kn), 則存在x,y, 使n = xd, m-kn = yd; 故m = yd+kn = yd+kxd = (y+kx)d;

故有a = mc = (y+kx)dc, b = nc = xdc; 可得 gcd(a,b) = gcd((y+kx)dc,xdc) = dc;

由于gcd(a,b) = c, 故d = 1;

即gcd(n,m-kn) = 1, 故可得gcd(b,a mod b) = c;

故得證gcd(a,b) = gcd(b,a mod b).

注意:兩種方法是有區别的。

算法原理

Lemma 1.3.1 若 a,b 且 a = bh + r，其中 h,r，則 gcd(a,b) = gcd(b,r)。

證明. 假設 d1 = gcd(a,b) 且 d2 = gcd(b,r)，我們證明 d1| d2 且 d2| d1，因而可利用 Proposition 1.1.3⑵ 以及 d1,d2 皆為正數得證 d1 = d2。

因 d1| a 且 d1| b 利用 Corollary 1.1.2 我們知 d1| a - bh = r. 因為 d1| b,d1| r 且 d2 = gcd(b,r) 故由 Proposition 1.2.5 知 d1| d2. 另一方面，因為 d2| b 且 d2| r 故 d2| bh + r = a. 因此可得 d2| d1。

Lemma 1.3.1 告訴我們當 a > b > 0 時，要求 a,b 的最大公因數我們可以先将 a 除以 b 所得餘數若為 r，則 a,b 的最大公因數等于 b 和 r 的最大公因數. 因為 r < b < a，所以當然把計算簡化了，接着我們就來看看輾轉相除法. 由于 gcd(a,b) = gcd(- a,b) 所以我們隻要考慮 a,b 都是正整數的情況。

Theorem 1.3.2 (The Euclidean Algorithm) 假設 a,b 且 a > b. 由除法原理我們知存在 h0,r0 使得

a = bh0 + r0，其中 r0 < b.

若 r0 > 0，則存在 h1,r1 使得

b = r0h1 + r1，其中 0r1 < r0.

若 r1 > 0，則存在 h2,r2 使得

r0 = r1h2 + r2，其中 0r2 < r1.

如此繼續下去直到 rn = 0 為止，若 n = 0 （即 r0 = 0），則 gcd(a,b) = b. 若 n1，則 gcd(a,b) = rn - 1。

證明. 首先注意若 r0 0，由于 r0 > r1 > r2 > ... 是嚴格遞減的，因為 r0 和 0 之間最多僅能插入 r0 - 1 個正整數，所以我們知道一定會有 nr0 使得 rn = 0。

若 r0 = 0，即 a = bh0，故知 b 為 a 之因數，得證 b 為 a,b 的最大公因數。若 r0 > 0，則由 Lemma 1.3.1 知

gcd(a,b) = gcd(b,r0) = gcd(r0,r1） = ... = gcd(rn - 1,rn) = gcd(rn - 1,0) = rn - 1。

現在我們來看用輾轉相除法求最大公因數的例子

Example 1.3.3 我們求 a = 481 和 b = 221 的最大公因數。首先由除法原理得 481 = 2 . 221 + 39，知 r0 = 39. 因此再考慮 b = 221 除以 r0 = 39 得 221 = 5 . 39 + 26，知 r1 = 26，再以 r0 = 39 除以 r1 = 26 得 39 = 1 . 26 + 13，知 r2 = 13。最後因為 r2 = 13整除r1 = 26 知 r3 = 0，故由 Theorem 1.3.2 知 gcd（481,221） = r2 = 13。

在利用輾轉相除法求最大公因數時，大家不必真的求到 rn = 0，例如在上例中可看出 r0 = 39 和 r1 = 26 的最大公因數是 13，利用 Lemma 1.3.1 馬上得知 gcd(a,b) = 13。

在上一節 Corollary 1.2.5 告訴我們若 gcd(a,b) = d，則存在 m,n 使得 d = ma + nb。當時我們沒有提到如何找到此 m,n，我們利用輾轉相除法來介紹一個找到 m,n 的方法，我們沿用 Theorem 1.3.2 的符号，看 r0 = 0 的情形，此時 d = gcd(a,b) = b 所以若令 m = 0,n = 1，則我們有 d = b = ma + nb. 當 r0 0 但 r1 = 0 時，我們知 d = gcd(a,b) = r0。故利用 a = bh0 + r0 知，若令 m = 1,n = - h0，則 d = r0 = ma + nb。同理若 r0 0,r1 0 但 r2 = 0，則知 d = gcd(a,b) = r1。故利用 a = bh0 + r0 以及 b = r0h1 + r1 知

r1 = b - r0h1 = b - (a - bh0)h1 = - h1a + （1 + h0h1）b。

因此若令 m = - h1 且 n = 1 + h0h1，則 d = r1 = ma + nb. 依照此法，當 r0,r1 和 r2 皆不為 0 時，由于 d = gcd(a,b) = rn - 1 故由 rn - 3 = rn - 2hn - 1 + rn - 1 知 d = rn - 3 - hn - 1rn - 2. 利用前面推導方式我們知存在 m1,m2,n1,n2 使得 rn - 3 = m1a + n1b 且 rn - 2 = m2a + n2b 故代入得

d = (m1a + n1b) - hn - 1(m2a + n2b) = (m1 - hn - 1m2）a + (n1 - hn - 1n2）b.

因此若令 m = m1 - hn - 1m2 且 n = n1 - hn - 1n2，則 d = ma + nb.

上面的說明看似好像當 r0 0 時對每一個 i {0,1,...,n - 2} 要先将 ri 寫成 ri = mia + nib，最後才可将 d = rn - 1 寫成 ma + nb 的形式，其實這隻是論證時的方便，在實際操作時我們其實是将每個 ri 寫成 mi'ri - 2 + ni'ri - 1 的形式慢慢逆推回 d = ma + nb. 請看以下的例子.

Example 1.3.4 我們試着利用 Example 1.3.3 所得結果找到 m,n 使得 13 = gcd（481,221） = 481m + 221n. 首先我們有 13 = r2 = 39 - 26 = r0 - r1. 而 r1 = 221 - 5 . 39 = b - 5r0，故得 13 = r0 - (b - 5r0) = 6r0 - b. 再由 r0 = 481 - 2 . 221 = a - 2b，得知 13 = 6(a - 2b) - b = 6a - 13b. 故得 m = 6 且 n = - 13 會滿足 13 = 481m + 221n。

要注意這裡找到的 m,n 并不會是唯一滿足 d = ma + nb 的一組解，雖然上面的推演過程好像會隻有一組解，不過隻能說是用上面的方法會得到一組解，并不能擔保可找到所有的解，比方說若令 m' = m + b,n' = n - a，則 m'a + n'b = (m + b)a + (n - a)b = ma + nb = d. 所以 m',n' 也會是另一組解，所以以後當要探讨唯一性時，若沒有充分的理由千萬不能說由前面的推導過程看出是唯一的就斷言是唯一，一般的作法是假設你有兩組解，再利用這兩組解所共同滿足的式子找到兩者之間的關系. 我們看看以下的作法。

Proposition 1.3.5 假設 a,b 且 d = gcd(a,b)。若 x = m0,y = n0 是 d = ax + by 的一組整數解，則對任意 t,x = m0 + bt/d,y = n0 - at/d 皆為 d = ax + by 的一組整數解，而且 d = ax + by 的所有整數解必為 x = m0 + bt/d,y = n0 - at/d 其中 t 這樣的形式。

證明. 假設 x = m,y = n 是 d = ax + by 的一組解，由于已假設 x = m0,y = n0 也是一組解，故得 am + bn = am0 + bn0. 也就是說 a(m - m0) = b(n0 - n). 由于 d = gcd(a,b），我們可以假設 a = a'd,b = b'd 其中 a',b' 且 gcd(a',b') = 1 （參見 Corollary 1.2.3）。因此得 a'(m - m0) = b'(n0 - n)。利用 b'| a'(m - m0),gcd(a',b') = 1 以及 Proposition 1.2.7⑴ 得 b'| m - m0. 也就是說存在 t 使得 m - m0 = b't. 故知 m = m0 + b't = m0 + bt/d. 将 m = m0 + bt/d 代回 am + bn = am0 + bn0 可得 n = n0 - at/d，因此得證 d = ax + by 的整數解都是 x = m0 + bt/d,y = n0 - at/d 其中 t 這樣的形式. 最後我們僅要确認對任意 t,x = m0 + bt/d,y = n0 - at/d 皆為 d = ax + by 的一組整數解，然而将 x = m0 + bt/d,y = n0 - at/d 代入 ax + by 得 a(m0 + bt/d)+ b(n0 - at/d)= am0 + bn0 = d，故得證本定理。

利用 Proposition 1.3.5 我們就可利用 Example 1.3.4 找到 13 = 481x + 221y 的一組整數解 x = 6,y = - 13 得到 x = 6 + 17t,y = - 13 - 37t 其中 t 是 13 = 481x + 221y 所有的整數解。

程序設計

輾轉相除法是利用以下性質來确定兩個正整數 a 和 b 的最大公因子的：

⒈ 若 r 是 a ÷ b 的餘數，且r不為0，則

gcd(a,b) = gcd(b,r)

⒉ a 和其倍數之最大公因子為 a。

另一種寫法是：

⒈ 令r為a/b所得餘數（0≤r

若 r= 0，算法結束；b 即為答案。

⒉ 互換：置 a←b，b←r，并返回第一步。

算法版本

Swift 語言版本

import Foundation

func gcd(a: Int, b: Int) -> Int {

var x = a, y = b

while y != 0 {

(x, y) = (y, x % y)

}

return x

}

let x = 75, y = 100

let result = gcd(a: x, b: y)

print("(x) 和 (y) 的最大公約數是 (result)")

Go語言版本

package main

import "fmt"

func main() {

var x, y int = 18, 12

result := gcd(x,y)

fmt.Printf("x, y 的最大公約數是 : %d",result)

}

func gcd(x,y int) int{

for y != 0 {

x, y = y, x%y

}

return x

}

Pascal語言版

var a,b,c:integer;

begin

readln(a,b);

c:=a mod b;

while c<>0 do

begin

a:=b;b:=c;c:=a mod b;

end;

write(b);

end.

C語言版

歐幾裡得算法：輾轉求餘

原理： gcd(a,b)=gcd(b,a mod b)

當b為0時，兩數的最大公約數即為a

getchar()會接受前一個scanf的回車符

#include

unsigned int MaxCommonFactor(int a,int b)

{

if(a % b == 0)

return b;

return MaxCommonFactor(b, a % b);

}

unsigned int Gcd(unsigned int M,unsigned int N)

{

unsigned int Rem;

while(N > 0)

{

Rem = M % N;

M = N;

N = Rem;

}

return M;

}

int main(void)

{

int a,b;

scanf("%d %d",&a,&b);

printf("the greatest common factor of %d and %d is ",a,b);

printf("%dn",Gcd(a,b));

printf("recursion:%dn",MaxCommonFactor(a,b));

return 0;

}

Ruby語言版

#用歐幾裡得算法計算最大公約數(排版略）

def gcd(x, y)

if y == 0

return x

else

return gcd(y, x % y)

end

C++版

#include

using namespace std;

int gcd(int a, int b)

{

if (a % b==0) return b;

else return gcd(b, a % b);

}

int x, y;

int main(){

cin >> x >> y;

cout << gcd(x, y);

return 0;

}

Java版

int gcd(int m,int n)

{ if(n == 0){

return m;

}

int r = m%n;

return gcd(n,r);

}

JavaScript版

function gcd(a, b) {

if (a % b == 0) return b;

return gcd(b, a % b);

}

Python版

def gcd(a, b):

while a != 0:

a, b = b % a, a

return b

Erlang版

gcd(A, 0) -> A;

gcd(A, B) -> gcd(B, A rem B).

Rust版

pub fn gcd(x: u64, y: u64) -> u64 {

let remainder = x % y;

if remainder == 0 {

return y;

} else {

return gcd(y, remainder);

}

#[cfg(test)]

mod tests {

use super::*;

#[test]

fn gcd_works() {

assert_eq!(gcd(2, 4), 2);

assert_eq!(gcd(6, 27), 3);

assert_eq!(gcd(4, 2), 2);

assert_eq!(gcd(27, 6), 3);

}

Bash版

function gcd() {

if [ ! -n "$2" ];then

return

if [ "$2" == "0" ];then

echo "$1"

return

gcd "$2" "$[$1%$2]"

}

模P乘法逆元

對于整數a、p，如果存在整數b，滿足ab mod p =1，則說，b是a的模p乘法逆元。

定理：a存在模p的乘法逆元的充要條件是gcd(a，p) = 1

證明：

首先證明充分性

如果gcd(a，p) = 1，根據歐拉定理，aφ（p) ≡ 1 mod p，因此

顯然aφ（p)-1 mod p是a的模p乘法逆元。

再證明必要性

假設存在a模p的乘法逆元為b

ab ≡ 1 mod p

則ab = kp +1 ，所以1 = ab - kp

因為gcd(a，p) = d

所以d | 1

所以d隻能為1

Stein算法

歐幾裡得算法是計算兩個數最大公約數的傳統算法，他無論從理論還是從效率上都是很好的。但是他有一個緻命的缺陷，這個缺陷隻有在大素數時才會顯現出來。

硬件平台，一般整數最多也就是64位，對于這樣的整數，計算兩個數之間的模是很簡單的。對于字長為32位的平台，計算兩個不超過32位的整數的模，隻需要一個指令周期，而計算64位以下的整數模，也不過幾個周期而已。但是對于更大的素數，這樣的計算過程就不得不由用戶來設計，為了計算兩個超過 64位的整數的模，用戶也許不得不采用類似于多位數除法手算過程中的試商法，這個過程不但複雜，而且消耗了很多CPU時間。對于現代密碼算法，要求計算 128位以上的素數的情況比比皆是，設計這樣的程序迫切希望能夠抛棄除法和取模。

Stein算法由J. Stein于1961年提出，這個方法也是計算兩個數的最大公約數。和歐幾裡得算法不同的是，Stein算法隻有整數的移位和加減法，這對于程序設計者是一個福音。

為了說明Stein算法的正确性，首先必須注意到以下結論：

gcd(a,a) = a，也就是一個數和他自身的公約數是其自身

gcd(ka,kb) = k gcd(a,b），也就是最大公約數運算和倍乘運算可以交換，特殊的，當k=2時，說明兩個偶數的最大公約數必然能被2整除

C++/java 實現

// c++/java stein 算法

int gcd(int a,int b)

{if(ab

{int temp = a;a = b;b=temp;}

if(0==b) //the base case

return a;

if(a%2==0 && b%2 ==0) //a and b are even