数学からの準備

RSA 暗号系は, 次の定理を基礎としている.

定理 16.1   $G$ を位数(要素の個数)が $n$ の群とするとき $G$ の任意の元 $a$ に対して $a^n = e$である. ここで $e$ は単位元である.

群の定義については, 適当な数学の本を参照されたい.

この定理は可換とは限らない一般の群で成立するが, ここでは可換な場合の証明のみを紹介する. この証明の理解には群の定義を知ってるだけで十分である.

定理 17.1 の証明: 群 $G$ の $n$ 個の相異なる要素を $g_1, \ldots, g_n$ としよう. このとき, $\{ a g_1, \ldots, a g_n \}$ を考えるとこれらもまた, $G$ の $n$ 個の相異なる元の集合となる. なぜなら, たとえば $a g_i = a g_j$ となると, $a$ の逆元を両辺にかけることにより, $g_i = g_j$ になり, 仮定に反するからである.

$\{g_1, \ldots, g_n \}$ と $\{ a g_1, \ldots, a g_n \}$ は集合として等しいのであるから,

$$g_1 \cdots g_n = (a g_1) \cdots (a g_n) = a^n (g_1 \cdots g_n)$$

がなりたつ. 両辺に $g_1 \cdots g_n$ の逆元を掛けてやると, $e = a^n$ をえる. 証明おわり.

$p$ を素数としよう. とくにこの定理を, ${\bf Z}/p{\bf Z}$ の乗法群

$$G =\{ 1, 2, \ldots, p-1\}$$

に適用すると, 次の定理を得る.

定理 16.2   $p$ を素数とするとき, $p$ で割れない任意の整数 $x$ について,

$$x^{p-1} = 1 \ {\rm mod}\,p$$

となる.

もうすこしくわしくこの定理の説明をしよう. $a \ {\rm mod}\,p$ で, $a$ を $p$ でわった余りをあらわすものとする. このとき

$$(a \ {\rm mod}\,p) (b \ {\rm mod}\,p) \ {\rm mod}\,p = ab \ {\rm mod}\,p$$

が成立する. 左辺は, $a$ を $p$ でわった余りと $b$ を $p$ でわった余りを掛けたあと, $p$ でわった余りをとることと, $ab$ を $p$ でわった余りをとることは同じである. という意味である. この事実および $p$ が素数のとき, 集合 $G =\{ 1, 2, \ldots, p-1\}$ の元 $a\in G$, $b \in G$ に対して, $ab \ {\rm mod}\,p \in G$ でかけ算を定義することにより, $G$ は位数 $p-1$ の可換な群となることを 用いると, 定理 17.2 の証明ができる. もちろん $1$ がこの群の単位元である. $G$ が(可換な)群であるを示すには, 逆元の存在が非自明である. 次の問題の 1 を示す必要がある.

問題 16.1  

1. $p$ を素数とする. $a$ を $1$ 以上, $p-1$ 以下の数とするとき,
   
   $$a b = 1 \ {\rm mod}\,p$$
   
   
   となる $1$ 以上, $p-1$ 以下の数 $b$ が存在する.
2. $a$, $p$ が互いに素な数なら, $a b = \ {\rm mod}\,p$ となる数 $b$ が存在する.
3. $b$ を構成するアルゴリズムを考えよ. その計算量を考察せよ.

ヒント: $a$ と $p$ にユークリッドの互除法を適用せよ. Asir では, 関数 inv を $a$, $p$ より $b$ を求めるのに 利用できる.

[346] for (I=1; I<5; I++) print(inv(I,5));
1
3
2
4

上の結果をみればわかるように, たしかに $1 \times 1 \ {\rm mod}\,5 = 1$, $2 \times 3 \ {\rm mod}\,5 = 1$, $3 \times 2 \ {\rm mod}\,5 = 1$, $4 \times 4 \ {\rm mod}\,5 = 1$ である.