暗号理論入門　2.9〜2.10

作者: 林芳樹
出版社/メーカー: 丸善出版
発売日: 2012/04/20
メディア: 単行本
この商品を含むブログを見る

2.9 拡張されたユークリッドのアルゴリズム

ユークリッドのアルゴリズムを拡張して、 $gcd(a, b) = ax + by$ が成立するような整数 $x,\ y$ を計算する。

ユークリッドのアルゴリズムを $a,\ b$ に適用したときの剰余数列を $r_0,\ ...,\ r_{n+1}$ で、商の数列を $q_1,\ ...,\ q_{n}$ で表す。

$x = (-1)^{n} x_n$ と $y = (-1)^{n+1} y_n$ が上記の等式を満たすように二つの数列 $(x_k) \ \ (y_k)$ を構成する。
初期値は $x_0 = 1,\ \ x_1 = 0,\ \ y_0 = 0,\ \ y_1 = 1$ とし、
　 $x_{k+1} = q_k x_k + x_{k-1}$ 、　 $y_{k+1} = q_k y_k + y_{k-1}$ 、　 $1 \le k \le n$
とおく。

$0 \le k \le n+1$ に対して、 $r_k = (-1)^{k} x_k a + (-1)^{k+1} y_k b$ が成立する。

$a = 100$ かつ $b = 35$ の場合は以下のようになる。

$k$	0	1	2	3	4
$r_k$	100	35	30	5	0
$q_k$		2	1	6
$x_k$	1	0	1	1	7
$y_k$	0	1	2	3	20

$n = 3$ かつ $gcd(100, 35) = 5 = -1 * 100 + 3 * 35$ である。
拡張ユークリッドアルゴリズムにより、 $gcd(a, b)$ 以外にも係数
　 $x = (-1)^{n} x_n$ 、　 $y = (-1)^{n+1} y_n$
が計算された。

pythonで書いてみた。

def xeuclid(a, b):
    x = [1, 0]
    y = [0, 1]
    sign = 1

    while b:
        q, r = divmod(a, b)
        a, b = b, r
        x[1], x[0] = q*x[1] + x[0], x[1]
        y[1], y[0] = q*y[1] + y[0], y[1]
        sign = -sign

    x = sign * x[0]
    y = -sign * y[0]

    return a, x, y