アルゴリズム論特論(塩田)第11回 (1) 観察
戻る / 次へ
$\newcommand{\ol}[1]{\overline{#1}}$
$\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$
$\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$
$\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$
観察
RSA 暗号では、
鍵生成や暗号化関数・復号関数で
$x^e \,\%\, n$ という計算(法べき乗)が使われていました。
法べき乗は、法が素数のときには特徴的な振る舞いをします。
まずはそれを観察してみましょう。
問 $p$ を素数、$a$ を法 $p$ の既約剰余類とする ( $a \in \znzc{p}$, 第7回 Def.6 )。
このとき、
$a^1$, $a^2$, $a^3$, $\cdots$
はどんな振る舞いをするか観察せよ。
- 例えば $p=7$, $a=2$ のときは
$2^1 = 2$, $2^2 = 4$, $2^3 = 1$,
$2^4 = 2$, $2^5 = 4$, $2^6 = 1$
となります。$2^6 = 1$ はフェルマの小定理でわかっていますが、
それまでの間は $2$, $4$, $1$, $2$, $4$, $1$ という数列になります。
-
$p=7$, $a=3$ のときはどうでしょうか。
$3^1 = 3$, $3^2 = 2$, $3^3 = 6$,
$3^4 = 4$, $3^5 = 5$, $3^6 = 1$
今度は $3$, $2$, $6$, $4$, $5$, $1$ という数列になりました。
-
$3 \leqq p \leqq 17$ について表を作ってあります。
ここから download してしばらく自分で観察してみてください。
観察
- 初めて $a^e = 1$ になる指数 $e$ は $p-1$ の約数である。
- 一度 $a^e = 1$ になると、その先は繰り返しになる。
- その繰り返しの周期は (1) の指数 $e$ に等しい。
- $a^1$, $\cdots$, $a^{p-1}$ には同じ数が $(p-1)/e$ 回ずつ現れる。
- どの素数 $p$ についても、$a^1$, $\cdots$, $a^{p-1}$ がすべて異なるような $a$ が必ずある。
... そのような $a$ だけ赤く塗った表は ここから download。