3.1 ユークリッドの互除法
四条にあるジュンク堂で、暗号理論入門を購入。少し読んでみた。
- 作者: 林芳樹
- 出版社/メーカー: 丸善出版
- 発売日: 2012/04/20
- メディア: 単行本
- この商品を含むブログを見る
最初の方は、微積の教科書を思い出すような感じだった。実数や整数の定義や性質から始まる。暗号理論なので、整数がメイン。整数の性質について、非常に詳しく述べられている。む、難しい…。
御約束ともいえるが、ユークリッドの互除法が出てきた。
最大公約数(gcd)を求めるアルゴリズムで、明示的に書かれた最古のアルゴリズムである(らしい)。
自然数 a, b の最大公約数は、b, a mod b の最大公約数に等しい。
これを利用したgcd(a,b)なる関数は、これまで何度も書いてきた。
…のだが、実はこのアルゴリズムが何故成立するのか、という証明は、恥ずかしながら理解していなかった。この機会に日本酒を煽りながら様々な文献を漁り、ようやく自分的に納得のいく証明が得られたので、ここに書いておく。
[証明]*1
全ての文字は整数とする。
a = bq + r とする。また、ある m, n が存在して、a = mx, b = nx とする。すなわち、x は a, b の公約数である。
このとき、
r = a - bq
r = mx - nxq
r = (m - nq)x
より、x は r の約数である。すなわち、「a, b の全ての公約数は、b, r の公約数でもある」ことが示せた。
また、r < b より、
int gcd(int a, int b){ return (b == 0 ? a : gcd(b, a%b)); }
なる関数gcdの第2引数は強い意味で単調減少であり、いずれ0になる*2。
ところで、ある整数 c について、gcd(c, 0) = c である。なぜなら、c は c の最大の約数であり、0 = 0*c が成立するからである。よって、上記アルゴリズムで a, b の最大公約数が求まる。
次回は拡張ユークリッドアルゴリズムについて学ぶ。
