アルゴリズム論特論（塩田）第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}$, 第７回 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 してしばらく自分で観察してみてください。

戻る / 次へ