アルゴリズム論特論（塩田）　2020年度教材 第3回

  • 出席代わりに、塩田 ( shiota＠is.kochi-u.ac.jp ) 宛てにメールを出してください。
  • 件名は「アルゴリズム論特論第３回出席」とでもしてください。
  • 内容は何でもいいです。

今日のテーマ

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

はじめに

　RSA暗号をはじめとする公開鍵暗号の設計には、 2000ビット程度の整数 $a$, $b$ に対して、 最大公約数 $\gcd(a,b)$ や、$ax+by=\gcd(a,b)$ を満たす $x$, $y$ を計算する必要があります。 しかし、
  • RSA暗号は大きな数の素因数分解問題が困難であることに基づく暗号ですから、 最大公約数の計算に $a$, $b$ の素因数分解を仮定してはいけません。
  • $ax+by=\gcd(a,b)$ を満たす $x$, $y$ も、前回の授業で存在することだけはわかりましたが、 単純な検索で求めることは不可能です。
これらの計算を高速に実現できる「ユークリッドのアルゴリズム」を今日は勉強します。
問　2000ビットの整数は10進数でおよそ何桁か？
問　宇宙の年齢はおよそ何秒と言われているか？

素因数分解と gcd, lcm

Th.1　ふたつの自然数 $a$, $b$ の素因数分解を
$a=\displaystyle{\prod_{p} p^{e_p}},\qquad$ $b=\displaystyle{\prod_{p} p^{f_p}}$
とすると、
$\gcd(a,b)=\displaystyle{\prod_{p} p^{\min(e_p,f_p)}},\quad$ $\mbox{lcm}(a,b)=\displaystyle{\prod_{p} p^{\max(e_p,f_p)}}$
Ex.2　総積記号 $\prod_p$ は全ての素数 $p$ についての積を表す記号で、
$a = 630 = 2^1 \times 3^2 \times 5^1 \times 7^1,$
$b = 168 = 2^3 \times 3^1 \times 5^0 \times 7^1\,$
のときは、$e_p$, $f_p$ は
$e_2 = 1$, $e_3 = 2$, $e_5 = 1$, $e_7 = 1$, 他の $e_p = 0,$
$f_2 = 3$, $f_3 = 1$, $f_5 = 0$, $f_7 = 1$, 他の $f_p = 0\,$
となります。べき指数の小さい方を掛け合わせたのが gcd, 大きい方を掛け合わせたのが lcm になります：
$\gcd(630,168) = 2^1 \times 3^1 \times 5^0 \times 7^1 = 42,$
$\mbox{lcm}(630,168) = 2^3 \times 3^2 \times 5^1 \times 7^1 = 2520$
　数字ならできる、と言っても、 記号で書かないとプログラミングできませんので、 記号の使い方を覚えてください。
Cor.3　$\gcd(a,b) \times \mbox{lcm}(a,b)=a \times b.$
証明　$x \geqq y$ のとき $\max(x,y)+\min(x,y) = x + y$,
$x \lt y$ のとき $\max(x,y)+\min(x,y) = y + x = x + y$ ゆえ。(証明終)
Cor.4　$\mbox{lcm}(a,b)$ の計算時間 ≒ $\gcd(a,b)$ の計算時間.

Key Lemma

　ここでは、ユークリッドのアルゴリズムでキーとなる命題を示します。
Lemma 5　$a=bq+r$ が成り立つとき、
$\gcd(a,b) = \gcd(b,r).$
証明　$d = \gcd(a,b)$, $e = \gcd(b,r)$ とおいて、$d = e$ を示しましょう。
(1)　まず、$b$, $r$ は $e$ の倍数ゆえ、
$a = bq + r$
から
$a$ は $e$ の倍数
∴ $e$ は $a$ の約数
∴ $e$ は $a$, $b$ の公約数
∴ $e \leqq \gcd(a,b) = d$
(2)　他方、$a$, $b$ は $d$ の倍数ゆえ、
$r = a - bq$
から
$r$ は $d$ の倍数
∴ $d$ は $r$ の約数
∴ $d$ は $b$, $r$ の公約数
∴ $d \leqq \gcd(b,r) = e$
(1), (2) より $d = e$. (証明終)

　Ex.2 では $630 = 168 \times 3 + 126$ より $\gcd(630,168) = \gcd(168, 126)$ となり、 ２変数関数 gcd が、より小さい引数で計算できることになります。

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

Algorithm 6 (ユークリッドのアルゴリズム)
  • 入力：$a$, $b$
  • 出力：$\gcd(a,b)$
  1. 数列 $\{\,r_n\,\}$ を宣言する
  2. $r_0 \leftarrow a$, $r_1 \leftarrow b$, $n \leftarrow 0$ とおく
  3. $r_{n+1}=0$ ならば $|\,r_n\,|$ を出力
  4. $r_{n+2} \leftarrow (\,r_n \div r_{n+1}$ の余り ), $n \leftarrow n+1$ として 3° へ
証明　(1)　出力が $\gcd(a, b)$ であること
　L'a 5 より全ての $n$ について
$\gcd(r_n, r_{n+1}) = \gcd(r_{n+1}, r_{n+2})$
が成り立ち、$n=0$ のときは
$\gcd(r_0, r_1) = \gcd(a, b)$
です。また 3. の終了条件 $r_{n+1}=0$ が満たされるときには
$\gcd(r_n, r_{n+1}) = \gcd(r_n, 0) = |\,r_n\,|$
ゆえ、出力される $|\,r_n\,|$ は $\gcd(a, b)$ に等しくなります。
(2)　アルゴリズムが有限回のステップで終了すること
　数列 $\{\,r_n\,\}$ は順番に余りを取って定めていますので、 非負整数からなる単調減少列であり、 有限回で $r_{n+1}=0$ となります。(証明終)
Ex.7　$\gcd(13579, 2468)=$？
$r_0=13579,\quad$ $r_1=2468,\quad$ $r_2=1239,\quad$ $r_3=1229,\quad$
$r_4=10,\quad$ $r_5=9,\quad$ $r_6=1,\quad$ $r_7=0$.
$r_n$ が 0 になる直前を見て $\gcd(13579,2468)=|\,r_6\,|=1$.
Rem.8　L'a 5 の余り $r$ は負であっても良いので、
$r_0=13579,\quad$ $r_1=2468,\quad$ $r_2=1239,\quad$ $r_3=-10,\quad$
$r_4=-1,\quad$ $r_5=0\quad$
として $\gcd(13579,2468)=|\,r_4\,|=1$ でも構いません。
やってみよう　$\gcd(1357, 246)=$？

拡張ユークリッドアルゴリズム

　ユークリッドのアルゴリズムを改良して
$ax+by=\gcd(a,b)$
を満たす $x$, $y$ も求めましょう。
Algorithm 9 (拡張ユークリッドアルゴリズム)
  • 入力：$a$, $b$
  • 出力：$d = \gcd(a,b)$ と、$ax+by=\gcd(a,b)$ を満たす $x$, $y$
  1. ３つの数列 $\{\,r_n\,\}$, $\{\,x_n\,\}$, $\{\,y_n\,\}$ を宣言する
  2. $r_0 \leftarrow a$, $r_1 \leftarrow b$, $x_0 \leftarrow 1$, $x_1 \leftarrow 0$, $y_0 \leftarrow 0$, $y_1 \leftarrow 1$, $n \leftarrow 0$ とおく
  3. $r_{n+1}=0$ ならば 5. へ
  4. $q \leftarrow (\,r_n \div r_{n+1}$ の商 ),
    $r_{n+2} \leftarrow r_n - q \times r_{n+1}$,
    $x_{n+2} \leftarrow x_n - q \times x_{n+1}$,
    $y_{n+2} \leftarrow y_n - q \times y_{n+1}$,
    $n \leftarrow n+1$ として 3° へ
  5. $r_{n} \lt 0$ ならば $(r_n,x_n,y_n) \leftarrow (-r_n,-x_n,-y_n)$,
  6. $(d,x,y)=(r_n,x_n,y_n)$ を出力
証明　$\{\,r_n\,\}$ は Alg.6 と同じものなので、 出力が $\gcd(a, b)$ であることと、 有限回のステップで終了することは証明できています。 あとは、全ての番号 $n$ について
$r_n = a x_n + b y_n$
が成り立つことを帰納法で示します。
$n=0$, $1$ のときは、初期値設定から
$r_0 = a = a \times 1 + b \times 0 = a x_0 + b y_0,$
$r_1 = b = a \times 0 + b \times 1 = a x_1 + b y_1\,$
となって成り立っています。$n$, $n+1$ のとき正しければ
$r_{n+2}$$=$$r_n - q \times r_{n+1}$
$=$$(a x_n + b y_n) - q \times (a x_{n+1} + b y_{n+1})$
$=$$a (x_n - q \times x_{n+1}) + b (y_n - q \times y_{n+1})$
$=$$a x_{n+2} + b y_{n+2}$.
(証明終)
Ex.10　$13579 x + 2468 y=1$ を満たす $x$, $y$ は？
$n$ $q$ $r_n$ $x_n$ $y_n$
$0$ $13579$ $1$ $0$
$1$ $2468$ $0$ $1$
$2$$ 5=\lfloor 13579/2468\rfloor$ $1239$ $1$ $-5$
$3$$ 1=\lfloor 2468/1239\rfloor$ $1229$ $-1$ $6$
$4$$ 1=\lfloor 1239/1229\rfloor$ $10$ $2$ $-11$
$5$$ 122=\lfloor 1229/10\rfloor$ $9$ $-245$ $1348$
$6$$1=\lfloor 10/9\rfloor$ $1$ $247$$-1359$
$7$$ 9=\lfloor 9/1\rfloor$ $0$
$r_n$ が $0$ になる直前の行から
$\gcd(13579,2468)=1=13579 \times 247 + 2468 \times (-1359)$.
( 表の作り方：
$r_2 = r_0 - 5 \times r_1 = 13579 - 5 \times 2468$
に合わせて
$x_2 = x_0 - 5 \times x_1 = 1 - 5 \times 0$
$y_2 = y_0 - 5 \times y_1 = 0 - 5 \times 1$
のように計算します。)
Ex.10'　$13579 x + 2468 y=1$ を満たす $x$, $y$ を、負の余りも使うパターンでも計算してみましょう。
$n$ $q$ $r_n$$x_n$ $y_n$
$0$ $13579$ $1$ $0$
$1$ $2468$ $0$ $1$
$2$$ 6=\mbox{round}( 13579/2468)$$-1229$ $1$ $-6$
$3$$ -2=\mbox{round}(2468/(-1229))$ $10$ $-2$ $13$
$4$$-123=\mbox{round}( (-1229)/10)$ $1$$247$$-1359$
$5$$ 10=\mbox{round}( 10/1)$ $0$
$r_n$ が $0$ になる直前の行から
$\gcd(13579,2468)=1=13579 \times 247 + 2468 \times (-1359)$.
プログラミング上の注意
  • 数列 $\{\,r_n\,\}$, $\{\,x_n\,\}$, $\{\,y_n\,\}$ はいずれも直前の 2 項しか残す必要が無いので、変数を使い回せば配列を使わなくて済みます。
  • $y$ は $y = (\gcd(a,b) - ax)/b$ によって計算できるので、必ずしも $\{\,y_n\,\}$ を計算しなくて済みます。
  • 整数商は、Python 2 では / でも // でもＯＫですが、Python 3 では // と書いてください。 Python3 で / を使うと実数値での計算結果が返されてしまいます。

まとめ

  • RSA暗号の安全性は、大きな数の素因数分解が困難であることに基づいている。
  • 最大公約数 $\gcd(a, b)$ や $a x + b y = 1$ を満たす $x$, $y$ はRSA暗号に必要だが、その計算に素因数分解を使う訳にはいかない。
  • ユークリッドのアルゴリズム、拡張ユークリッドアルゴリズムという手がある。
  • プリント

自宅学習の例

  • Ex.10 を真似て $1357 x + 246 y=1$ を満たす $x$, $y$ を求めてみよう。

戻る