互除法

$a$, $b$ の GCD を ${\tt gcd}(a,b)$ であらわそう. 便宜上, ${\tt gcd}(a,0)$ は $a$ と定義する. ユークリッドの互除法は次の定理を基礎としている.

定理 7.2   $a$, $b$ を自然数として $a \geq b$ と仮定しよう. このとき

$${\rm gcd}(a,b) = {\rm gcd}(b,r)$$

がなりたつ. ここで, $q$ を $a$ わる $b$ の商, $r$ を $a$ わる $b$ の余り, すなわち,

$$a = b q + r, \quad r < b$$

が成立していると仮定する.

証明: $d$ が $a$, $b$ の公約数なら, $r = a-bq$ なので, $d$ は $r$ を割り切る. また $b$ も割り切る. したがって, $d$ は $b$ と $r$ の公約数である.

$d'$ が $b$ と $r$ の公約数なら, 同じ理由で, $d'$ は $a$ と $b$ の公約数である.

したがって, $a$, $b$ の公約数の集合と $b$, $r$ の公約数の集合は等しい. とくに GCD 同士も等しい. 証明おわり.

例題 7.2   $18$ と $15$ の GCD を上の定理を利用して求めよ.

$$\begin{eqnarray*} & 18 ÷ 15 = 1\ \cdots 3 \\ & 15 ÷ 3 = 5\ \cdots 0 \end{eqnarray*}$$

である. したがって, 上の定理より.

$${\rm gcd}(18,15) = {\rm gcd}(15,3) = {\rm gcd}(3,0) = 3$$

となる.

この GCD 計算方法をユークリッドの互除法という. プログラムに書くと次のようになる. 次の関数 e_gcd(A,B) は 数 A と数 B の GCD を互除法で求める.

def e_gcd(A,B) {
  if (B>A) {
    T = A; A = B; B=T;
  }
  while (B>0) {
    R = A%B;
    A=B; B=R;
  }
  return(A);
}

さてこのアルゴリズムの計算量を考察しよう. 命令 R = A%B が何回実行されるのか考えればよいであろう. (最悪)計算量を求めるには, プログラムが最悪の振舞をする データが何かわかれば計算量の評価ができる. 実は互除法での 最悪の場合のこの回数はフィボナッチ数列で実現できる. 次の漸化式

$$F_{k+2} = F_{k+1}+F_k , \quad F_0 = F_1 = 1$$

できまる数列をフィボナッチ数列とよぶ.

定理 7.3   互除法による $a$ と $b$ の GCD 計算が $n$ 回の R = A%B の計算で終了したとする. このとき, $b$ の値によらず, $a \geq F_n$ が成立する.

証明: $a_n = a$, $a_{n-1} = b$ とおく. 互除法の各ステップにでてくる数を次のように $a_k$, $a_{k-1}$ とおく.

$$\begin{eqnarray*} & a_n ÷ a_{n-1} = q_n \ \cdots \ a_{n-2} \\ & a_{n-1} ÷ a_{... ...\cdots \ a_{n-3} \\ & \cdots \\ & a_1 ÷ a_0 = q_1\ \cdots \ 0 \end{eqnarray*}$$

このように定義すると

$$a_{k+2} = q_{k+2} a_{k+1} + a_k, \quad q_{k+2} \geq 1$$

がなりたつ. また $a_0 \geq 1$, $a_1 \geq 2$ がなりたつ. よって, フィボナッチ数列の漸化式とくらべることにより,

$$a_k \geq F_k \quad k=0,1,2, \ldots, n$$

が成り立つ. 証明おわり.

この証明により, $a=F_n$, $b=F_{n-1}$ に互除法を適用すると, $n$ 回の R = A%B の計算が必要なことも分る.

$F_n$ の一般項を計算することにより, 次の定理が得られる.

定理 7.4   $m$ 桁の数の GCD の計算は, 互除法で $O(m)$ 時間でできる.

問題 7.1   $F_n$ の一般項を計算し, 上の定理の証明を完成せよ.

上の結果により, 互除法による GCD 計算は素因数分解による GCD 計算に くらべ圧倒的に早いことがわかる.

問題 7.2   $a=1000000000000283$ と $b=3256594799$ の GCD を互除法および素因数分解を用いて求めよ. 時間を計測せよ. 1 時間待っても答えがでないときはあきらめよ.

インターネットなどで用いられている暗号は素因数分解に計算時間 がかかる -- 計算量が大きい -- という経験則に立脚して設計されている.