計算機実験 II（塩田・森教官）　No.9

　　1995年12月15日の課題　：　ユークリッドのアルゴリズム
［始めに］　

情報化社会において暗号は欠くべからざるものである。 （例えば、現在ネットワーク上ではパスワードは暗号化されずに送信されているが、 これはセキュリティ上大きな問題があり、その改善が急務とされている、等々。） 現在は「公開鍵暗号」と言って暗号化の方法を公開する暗号が主流であり、 その多くは初等整数論のアルゴリズムを用いて設計されている。 そこで今日から３回は、代表的な公開鍵暗号であるＲＳＡ暗号と、 その設計に必要な初等整数論アルゴリズムを講義する。
［記号 ］

ふたつの整数 a，b に対して、 その最大公約数を GCD(a,b) で表す。ただし、

  1. a，b の正負に関わらず最大公約数は GCD(a,b)≧0 に取る。

  2. b = 0 のときは GCD(a,b)=｜a｜（ a の絶対値 ） と定める。

  3. 特に a = b = 0 のときは GCD(a,b) = 0 と定める。
［補助定理］

b≠0 のとき、a を b で割った余りを r とおくと GCD(a,b) = GCD(b,r) が成り立つ。
この補助定理により次のアルゴリズムが導かれる。

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

次のアルゴリズムにより最大公約数が求まる：

  1. b = 0 ならば GCD(a,b) := ｜a｜ とせよ。

  2. b≠0 ならば

    a） 次の様に数列 rn を作る：

    r0 := a； r1 := b；
    rn := (rn-2 を rn-1 で割った余り) ( n = 2, 3,...)

    b） 数列 rn は減少列なので或る n で rn = 0 となる。 このとき

    GCD(a,b) := ｜rn-1｜

    とせよ。
［定理 ］ GCD(a,b) = d とおくとき、d = a x + b y を満たす整数 x，y が存在する。
［ユークリッドのアルゴリズム ver. 2］

GCD(a,b) = d とおくとき、d = a x + b y を満たす整数 x，y は次のアルゴリズムにより求まる：

  1. b=0 のとき

    GCD(a,b) := ｜a｜，
    x := 1（ a≧0 のとき）， x := -1（ a＜0 のとき），
    y := 0

    とせよ。

  2. b≠0 のとき

    a） 次の様に数列 rn，xn，yn を作る：

    r0 := a； r1 := b；
    x0 := 1； x1 := 0；
    y0 := 0； y1 := 1；

    q := (rn-2をrn-1で割った商)；
    rn := rn-2-q*rn-1 （=rn-2をrn-1で割った余り）；
    xn := xn-2-q*xn-1；
    yn := yn-2-q*yn-1； （n=2,3,...）

    b） rn=0 となる n で、

    rn-1＞0 のとき
    GCD(a,b) := rn-1； x := xn-1； y := yn-1；

    rn-1＜0 のとき
    GCD(a,b) := -rn-1； x := -xn-1； y := -yn-1；

    とせよ。
［系］

a と b が互いに素ならば （ すなわち a と b の最大公約数が 1 ならば ） ax+by=1 を満たす整数 x，y が ユークリッドのアルゴリズム ver. 2 によって求まる。
レポート課題［６］

ユークリッドのアルゴリズム ver. 2 を実際にプログラミングせよ。

［プログラミング上の注意］

  1. 入力を a，b＞0 に限ればアルゴリズムの 1. は省略できる。

  2. 割り算の余りは、負の数も許して ｜rn｜≦｜rn-1｜/2 と 取っておけば計算ステップ数が少なくなる。

  3. 計算には数列 rn，xn，yn の直前の2つの項のみが必要なので、 配列変数を用いなくてもプログラムが書ける。

  4. y は、GCD(a,b) と x が計算できれば y := (GCD(a,b)-x*a)/b という式で求まるが、 上の様に求める方がオーバーフローの危険が少ない。
［補足］

ユークリッドのアルゴリズム （ ver. 2 ） は 一変数の多項式についても成り立ち、 情報理論に幅広い応用を持つ「有限体」 のデータを計算機で計算するときに用いられる （次回の「発展した話題」参照）。

次回のプリントへ