この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

暗号理論の問題

難易度 1教科書の例題レベル大学数学暗号理論

素数 $p = 31$ について、 $g = 3$ は法 $31$ の原始根です（ $3$ の法 $31$ での位数は $30$ ）。ポーリッヒ・ヘルマン法を用いて、 $3^{x} \equiv 22 (mod 31), 0 \leq x \leq 29$ を満たす整数 $x$ を求めよ。

この問題で使うもの

ポーリッヒ・ヘルマン法による離散対数（説明と入口の問題）

この問題を解けるようになるまで（26 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

ポーリッヒ・ヘルマン法を使います。まず $p - 1 = 30$ を素因数分解し、素因数ごとに $x$ の余りを求めましょう。

ヒント 2

$30 = 2 \cdot 3 \cdot 5$ です。各素因数 $q$ について $(3^{30/ q})^{x} \equiv 2 2^{30/ q} (mod 31)$ を考えると、 $x mod q$ が決まります。べき乗は繰り返し二乗法で計算します。

ヒント 3

$3^{15} \equiv - 1$ , $2 2^{15} \equiv - 1$ より $x \equiv 1 (mod 2)$ 。 $3^{10} \equiv 25$ , $2 2^{10} \equiv 5$ より $x \equiv 2 (mod 3)$ 。 $3^{6} \equiv 16$ , $2 2^{6} \equiv 8$ から $x mod 5$ を求め、最後に中国剰余定理でまとめます。

答えと解説

答えを見る

17

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

$p - 1 = 30 = 2 \cdot 3 \cdot 5$ と素因数分解します。各素因数 $q$ について、両辺を $\frac{30}{q}$ 乗した $(3^{30/ q})^{x} \equiv 2 2^{30/ q} (mod 31)$ を解いて $x mod q$ を求めます。 $3^{30/ q}$ の位数は $q$ なので、 $x$ を $q$ で割った余りだけが決まります。

準備（繰り返し二乗法）
$2 2^{2} = 484 \equiv 19$ , $2 2^{4} \equiv 1 9^{2} = 361 \equiv 20$ , $2 2^{8} \equiv 2 0^{2} = 400 \equiv 28 (mod 31)$ 。
また $3^{2} = 9$ , $3^{3} = 27$ , $3^{5} = 243 \equiv 26$ , $3^{6} \equiv 2 7^{2} = 729 \equiv 16$ , $3^{10} \equiv 2 6^{2} = 676 \equiv 25$ , $3^{15} = 3^{10} \cdot 3^{5} \equiv 25 \cdot 26 = 650 \equiv 30 \equiv - 1 (mod 31)$ 。

(1) $q = 2$ （指数 $15$ ）
$3^{15} \equiv - 1$ 。 $2 2^{15} = 2 2^{8} \cdot 2 2^{4} \cdot 2 2^{2} \cdot 22 \equiv 28 \cdot 20 \cdot 19 \cdot 22$ 。 $28 \cdot 20 = 560 \equiv 2$ , $2 \cdot 19 = 38 \equiv 7$ , $7 \cdot 22 = 154 \equiv 30 \equiv - 1$ 。
よって $(- 1)^{x} \equiv - 1$ となり、 $x \equiv 1 (mod 2)$ 。

(2) $q = 3$ （指数 $10$ ）
$3^{10} \equiv 25$ 。 $2 2^{10} = 2 2^{8} \cdot 2 2^{2} \equiv 28 \cdot 19 = 532 \equiv 5$ 。
$2 5^{0} = 1$ , $2 5^{1} = 25$ , $2 5^{2} = 625 \equiv 5$ なので $2 5^{x} \equiv 5$ より $x \equiv 2 (mod 3)$ 。

(3) $q = 5$ （指数 $6$ ）
$3^{6} \equiv 16$ 。 $2 2^{6} = 2 2^{4} \cdot 2 2^{2} \equiv 20 \cdot 19 = 380 \equiv 8$ 。
$1 6^{1} = 16$ , $1 6^{2} = 256 \equiv 8$ なので $1 6^{x} \equiv 8$ より $x \equiv 2 (mod 5)$ 。

(4) 中国剰余定理でまとめる
$x \equiv 2 (mod 3)$ と $x \equiv 2 (mod 5)$ から $x \equiv 2 (mod 15)$ 。 $0 \leq x \leq 29$ の範囲では $x = 2$ または $17$ です。このうち $x \equiv 1 (mod 2)$ を満たすのは $x = 17$ です。

確認: $3^{17} = 3^{15} \cdot 3^{2} \equiv - 9 \equiv 22 (mod 31)$ 。

よって $x = 17$ です。

別解

$3$ のべきを法 $31$ で順に計算すると、 $3^{1} = 3, 3^{2} = 9, 3^{3} = 27, 3^{4} = 19, 3^{5} = 26, 3^{6} = 16, 3^{7} = 17, 3^{8} = 20, 3^{9} = 29, 3^{10} = 25, 3^{11} = 13, 3^{12} = 8, 3^{13} = 24, 3^{14} = 10, 3^{15} = 30, 3^{16} = 28, 3^{17} = 22$ となる。

ポーリッヒ・ヘルマン法では $30 = 2 \cdot 3 \cdot 5$ なので、 $x$ を $2, 3, 5$ を法として決める。

法 $2$ : $2 2^{15} \equiv (- 1)^{x}$ であり、 $2 2^{15} \equiv 3^{255} \equiv 3^{15} \equiv 30 \equiv - 1$ なので、 $x \equiv 1 (mod 2)$ 。
法 $3$ : $2 2^{10} \equiv 3^{170} \equiv 3^{20} \equiv 5$ 。位数 $3$ の元は $3^{10} = 25, 3^{20} = 5$ なので、 $(3^{10})^{x} = 5 = (3^{10})^{2}$ より $x \equiv 2 (mod 3)$ 。
法 $5$ : $2 2^{6} \equiv 3^{102} \equiv 3^{12} \equiv 8$ 。 $3^{6} = 16$ で、 $1 6^{2} = 256 \equiv 8$ なので $x \equiv 2 (mod 5)$ 。

中国剰余定理より、 $x \equiv 2 (mod 15)$ かつ $x$ は奇数なので $x = 17$ 。

検算: 上の表から $3^{17} \equiv 22 (mod 31)$ であり、 $0 \leq x \leq 29$ を満たす。

暗号理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題