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

　　1995年12月22日の課題　：　法演算

今日はＲＳＡ暗号設計の基礎である法演算を説明する。
以下、文字は全て整数を表すものとする。
［合同式］

正整数 m とふたつの整数 a,b に対して、a - b が m で割り切れるとき、 「a と b は m を法 ( ほう ) として合同である」と言い、 a ≡ b ( mod m ) と表す（ a 合同 b モド m と読む ）。 法が明らかな場合には ( mod m ) を省略しても良い。
［命題Ａ］

  1. a ≡ b, c ≡ d ( mod m ) ⇒ a ± c ≡ b ± d, a c ≡ b d ( mod m ).

    すなわち法演算では加法・減法・乗法が普通の数と同様にでき、 結合法則・分配法則も成り立つ。 ただし除法は次のようにあまり自由にはできない。

  2. c a ≡ c b ( mod m ) ⇒ a ≡ b ( mod m/GCD(c,m) )

    ただし GCD(c,m) は c と m の最大公約数。

［例題］

10100 を 37 で割った余りを求めよ。
［解］

9×3×37 = 999 ゆえ 1000 = 1+999 ≡ 1 ( mod 37 ). 従って 10100 = (1000^33)×10 ≡ (1^33)×10 = 10 ( mod 37 ). 答えは 10。
［互いに素］

ふたつの整数 a, m は、 その最大公約数 GCD(a,m) が 1 であるとき 「互いに素である」と言う。
［オイラーの関数］

1 から m までの整数の中で法 m と互いに素である整数の個数を φ(m) と表す。これを「オイラーの関数」と呼ぶ。
［オイラーの定理］

整数 a が法 m と互いに素であるとき、 aφ(m) ≡ 1 ( mod m ) が成り立つ。
［命題Ｂ］

整数 a が法 m と互いに素であるとき、 a x ≡ 1 ( mod m ) を満たす整数 x が ユークリッドのアルゴリズム ver.2 によって求まる。
実際、a と m についてのユークリッドのアルゴリズム ver.2 によって a x + m y = GCD(a,m) = 1 を満たす整数 x, y が求まるが、 このとき、a x = 1 - m y ≡ 1 ( mod m ) となっている。
［命題Ｃ］

オイラーの関数は手計算では次の性質を用いて計算する。

  1. p が素数、e が自然数ならば φ(pe) = (pe-1)×(p-1).

  2. m と n が互いに素ならば φ(mn) = φ(m)×φ(n).
［例］

φ(72) = φ(23×32) = φ(23)×φ(32) = (22)×(2-1)×(31)×(3-1) = 4×6 = 24.
レポート課題追加

［課題］

  1. オイラーの関数 φ(m) を m = 2, 3, …, 200 について計算する プログラムを作れ。

  2. 法 m = 105 に対して a = 1, 2, …, 104 の中で m と互いに素な整数 すべてについて aφ(105) ≡ 1 ( mod 105 ) が 成り立つことをプログラムを組んで確かめよ。
発展した話題

［剰余環］

法 m を固定するとき、整数 a を含む剰余類を

[a] := { x | x≡a ( mod m ) }

と表し、m を法とする剰余類全体の集合（剰余環）を

Z/mZ := { [0], [1], …, [m-1] }

と表す。 命題Ａにより、剰余類に対して和・差・積が次の様に定義できる：

[a]±[b] := [a±b],
[a]×[b] := [a×b].

（剰余類はバーで書くことが多いが、ブラウザの関係でここでは [ ] を用いた。）

［有限体 Fp］

特に法が素数 p の場合は Fp := Z/pZ と表す。 Fp は「標数 p の有限体」である。その意味は、
［命題Ｄ］

Fp では加減乗除の四則演算ができる。すなわち、 Fp では [0] 以外の元は乗法の逆元を持つ。（命題Ｂより）
［有限体は情報理論に不可欠］

有限体 Fp は

という特徴があり、暗号理論や誤り訂正符号の理論等、情報理論に 実に幅広い応用がある。 特に F2 = {0,1} の計算はビット演算そのものである :

［一般の有限体］

四則演算の定義されている有限集合を一般に「有限体」と言う。 Fp 以外にも有限体が存在するが、 それらは Fp の数を係数にもつ一変数の多項式を用いて表現される。

次回のプリントへ