ユークリッド互除法の証明とpythonによる実装

ユークリッド互除法とは、2つの自然数の最大公約数を高速に求めるアルゴリズムである。RSA暗号の処理などに用いられる。

この記事ではユークリッド互除法の解説とpythonで実装したプログラムを紹介する。

ユークリッド互除法のやり方

aとb(共に正の整数,a>b)の最大公約数gcd(a,b)を求めるとする。またa÷bの余りをrとすると、次の式が成り立つ。

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

「なぜ成り立つのか」については後述する。

ここで(a > b > r)であるから、gcd(a, b)と比べてgcd(r, b)のほうが扱う数字の値が小さくなる。

次に、

a’ = b
b’ = r
r’ = a’÷b’の余り

とするとa’>b’であるから

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

となる。このような操作を何度も繰り返していくとどんどん値が小さくなっていき、いずれ余りが0になる。そのときの割った数が最大公約数gcd(a,b)となる。

ユークリッド互除法の「互除」というのは、このような「お互いに除算し合う」という操作を表している。

具体的な数値をいれてみる。

ユークリッド互除法を用いてgcd(74646, 68172)を求めてみよう。

74646 ÷ 68172 = 1 余り 6474

であるから

gcd(74646, 68172) = gcd(6474, 68172)

次に

38172 ÷ 6474 = 10 余り 3432

であるから

gcd(6474, 68172) = gcd(6474, 3432)

同様の操作を繰り返していくと

6474 ÷ 3432 = 1 余り 3042
➡ gcd(6474, 3432) = gcd(3042, 3432)

3432 ÷ 3042 = 1 余り 390
➡ gcd(3042, 3432) = gcd(3042, 390)

3042 ÷ 390 = 7 余り 312
➡gcd(3042, 390) = gcd(312, 390)

390 ÷ 312 = 1 余り 78
➡gcd(312, 390) = gcd(312, 78)

312 ÷ 78 = 4 余り 0　➡　gcd(74646, 68172) = 78

最終的に78で割ったときに余りが０となったので、gcd(74646, 68172)＝78と求められる。

ユークリッド互除法のアルゴリズム

これまでに説明した流れをアルゴリズムの形に書くと、次のようになる。

入力:a,b(a>b),出力：gcd(a, b)

    step1: r = (a÷bの余り)とする。
   
    step2: r = 0になるまで、以下を繰り返す。
    
        step2-1: a = bとする。

        step2-2: b = rとする。

        step2-3: r = (a÷bの余り)とする。

    step3: gcd(a, b) = b を出力して終了。

かなりあっさりとしたアルゴリズムである。ゆえに、非常に高速。

素因数分解を行う方法に比べると、「公約数で割る」という行為がないのでかなり早い。「公約数を推測して当てはめる」という行為は、コンピュータにとってハードルが高い。

ユークリッド互除法は機械的な処理なので、コンピュータにやらせる分にはとても相性がいい。大きな数になっても、大したステップ数にならないのもメリット。

pythonによるユークリッド互除法の実装

def gcd(a,b): 
    r = a % b 
    while r != 0:
        a = b
        b = r
        r = a % b
    return b

print("gcd(74646,68172)=", + gcd(74646,68172))

上のほうで計算した「gcd(74646,68172)= 78」を求めることができた。動きがわかりやすいようにprint文を加えてみると、

def gcd(a,b): 
    r = a % b 
    while r != 0:
        a = b
        b = r
        r = a % b
        print(r)
    return b

print("gcd(74646,68172)=", + gcd(74646,68172))

余りを次々と求めていき、0になるまで繰り返していることがわかる。

ユークリッド互除法の証明

最後に、なぜこのような方法で最大公約数を求めることができるのかを説明しておく。

キーポイントは最初のほうに示したgcd(a, b) = gcd(r, b)の証明だ。

a÷bの商をq, 余りをrとすると

a = bq + r  ➡  r = a – bq

となるので、gcd(r, b) = gcd(a – qb, b)と表すことができる。ここで、gcd(a, b) = d とし,

a0 = a/d  (a = a0d)
b0 = b/d (b = b0d)
gcd(a0, b0) = 1

というようにa0,b0 を定義すると、

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

= gcd((a0 – qb0)d, b0d)

= d × gcd(a0 – qb0, b0)

と式を変形することができる。

このとき、gcd(a0 – qb0, b0) = 1 であれば、gcd(r, b) = d × 1 = gcd(a, b)となり、証明が完成する。

そこで、gcd(a0 – qb0, b0) ≠ 1と仮定し、これがあり得ないことを証明することで、gcd(a0 – qb0, b0) = 1を証明する。つまり背理法を活用するのだ。

「gcd(a0 – qb0, b0) ≠ 1」ということは、a0 – qb0とb0が1より大きな公約数Cを持つことになる。そうなると、a0 – qb0はCの倍数となり、a0もCの倍数であるという事になる。

つまり、a0もb0もともにCの倍数であるから、「gcd(a0, b0) = 1」に反する。したがって、「gcd(a0 – qb0, b0) ≠ 1」という仮定は成立せず、gcd(a0 – qb0, b0) = 1であることがわかり、gcd(a, b) = gcd(r, b)であることを証明できる。