ユークリッド互除法 - ちりもつもればミルキーウェイ

はじめに

これは RSA完全理解 Advent Calendar の6日目の記事です

RSAの話は一旦お休みして、今回からは剰余環の逆元をもとめるための前提知識をまとめていきたいと思います
おおまかな流れとしては、

みたいな流れを想定してます。

今回はその一発目でユークリッド互除法の紹介です！

以下の性質を利用した、 $a, b$ の最大公約数 $gcd(a, b)$ を効率良く求めるアルゴリズムです。

ある値 $a, b$ についての割り算を $a = bq + r$ と表したときに
$gcd(a, b) = gcd(b, r)$ となる

具体的な手順は

$a = 1152$ , $b = 504$ としてやってみる

$1152\div 504 = 2 \ ... \ 144$
$504\div 144 = 3 \ ... \ 72$
$144\div 72 = 2 \ ... \ 0$

となり $gcd(a, b) = 72$ であることがわかる

手計算に自身がないのでmath/bigを使ってサクッとコードを書くとやっぱり72であることがわかる

func main() {
    a := big.NewInt(1152)
    b := big.NewInt(504)
    fmt.Println(new(big.Int).GCD(new(big.Int), new(big.Int), a, b))
}

なんかうまくいきそうだ

方針としては、 $a, b, r$ についての関係 $a = bq + r$ をうまく利用しながら

のどちらも同時に満たされることを確認すれば $gcd(a, b) = gcd(b, r)$ となりそうなのでその方向で頑張る

$gcd(a, b) \leq gcd(b, r)$ について

$a, b$ はどちらも $gcd(a, b)$ の倍数でありそれぞれ

とかける。したがって $a = bq + r$ を変形した $r = bq - a$ についても

$r = bq - a = m'(gcb(a, b))\cdot q - m(gcd(a, b))$

とかけるので $r$ も $gcd(a, b)$ の倍数

$gcd(a, b)$ は $b, r$ をともに割り切れるので $b, r$ の公倍数でもある $gcd(b, r)$ は $b, r$ の公約数の中では最大なはずなので、すくなくとも

$gcd(a,b)\leq gcd(b,r)$

が成り立つ

$gcd(a, b) \geq gcd(b, r)$ について

$b, r$ はどちらも $gcd(b, r)$ の倍数でありそれぞれ

とかける。したがって

$a = bq + r = n(gcd(b, r))\cdot q + n'(gcd(b, r))$

と書けるので $a$ も $gcd(b, r)$ の倍数

$gcd(b, r)$ は $a, b$ をともに割り切れるので $a, b$ の公約数でもある
$gcd(a, b)$ は $a, b$ の公約数の中で最大なはずなので、すくなくとも

$gcd(a, b)\geq gcd(b, r)$

が成り立つ

これで $gcd(a, b) \leq gcd(b, r)$ と $gcd(a, b) \geq gcd(b, r)$ がどちらも示せたので

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

が成り立つ。証明終了

証明みればわかるけど $q$ はべつに割り算の商じゃなくてもよくて
$a\geq bq$ が成り立つ範囲において好きな正の整数をとっていいです

無駄にステップ数増やしても特に意味がないから商でやるのが効率良いよねというだけの話