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

暗号理論の問題

難易度 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$ なので、両辺を $15, 10, 6$ 乗した $(3^{15})^{x} \equiv 2 2^{15}$ , $(3^{10})^{x} \equiv 2 2^{10}$ , $(3^{6})^{x} \equiv 2 2^{6} (mod 31)$ を考える。

ヒント 3

$3^{15} \equiv - 1, 2 2^{15} \equiv - 1$ 、 $3^{10} \equiv 25, 2 2^{10} \equiv 5$ 、 $3^{6} \equiv 16, 2 2^{6} \equiv 8$ となる。ここから $x \equiv 1 (mod 2)$ が分かり、残りの $x mod 3$ 、 $x mod 5$ を求める。

答えと解説

答えを見る

17

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

解説を読む

方針 $p - 1 = 30 = 2 \cdot 3 \cdot 5$ と素因数分解する。各素因数 $q \in {2, 3, 5}$ について、両辺を $\frac{30}{q}$ 乗すると
$(3^{30/ q})^{x} \equiv 2 2^{30/ q} (mod 31)$
となる。 $3^{30/ q}$ の位数は $q$ なので、この式から $x mod q$ が決まる。最後に中国剰余定理でまとめる。

準備（繰り返し二乗法） $g = 3$ のべき：
$3^{2} = 9$ , $3^{4} = 81 \equiv 19$ , $3^{5} \equiv 19 \cdot 3 = 57 \equiv 26$ , $3^{6} \equiv 26 \cdot 3 = 78 \equiv 16$ , $3^{10} \equiv 2 6^{2} = 676 \equiv 25$ , $3^{15} \equiv 25 \cdot 26 = 650 \equiv 30 \equiv - 1$ 。

$h = 22$ のべき：
$2 2^{2} = 484 \equiv 19$ , $2 2^{4} \equiv 1 9^{2} = 361 \equiv 20$ , $2 2^{5} \equiv 20 \cdot 22 = 440 \equiv 6$ , $2 2^{6} \equiv 6 \cdot 22 = 132 \equiv 8$ , $2 2^{10} \equiv 6^{2} = 36 \equiv 5$ , $2 2^{15} \equiv 5 \cdot 6 = 30 \equiv - 1$ 。

$q = 2$ （指数 $15$ ） $(3^{15})^{x} \equiv 2 2^{15}$ より $(- 1)^{x} \equiv - 1$ 。よって $x \equiv 1 (mod 2)$ 。

$q = 3$ （指数 $10$ ） $2 5^{x} \equiv 5 (mod 31)$ 。 $2 5^{0} = 1$ , $2 5^{1} = 25$ , $2 5^{2} = 625 \equiv 5$ なので $x \equiv 2 (mod 3)$ 。

$q = 5$ （指数 $6$ ） $1 6^{x} \equiv 8 (mod 31)$ 。 $1 6^{0} = 1$ , $1 6^{1} = 16$ , $1 6^{2} = 256 \equiv 8$ （ $1 6^{3} \equiv 4$ , $1 6^{4} \equiv 2$ で他と一致しない）なので $x \equiv 2 (mod 5)$ 。

中国剰余定理 $x \equiv 2 (mod 3)$ かつ $x \equiv 2 (mod 5)$ より $x \equiv 2 (mod 15)$ 、すなわち $x = 2$ または $17$ （ $0 \leq x \leq 29$ ）。このうち奇数なのは $17$ 。

検算 $3^{17} = 3^{15} \cdot 3^{2} \equiv (- 1) \cdot 9 = - 9 \equiv 22 (mod 31)$ 。

よって $x = 17$ 。

別解

$p - 1 = 30 = 2 \cdot 3 \cdot 5$ なので、ポーリッヒ・ヘルマン法で $x mod 2, 3, 5$ を求める。

(1) 法 2: $2 2^{15} \equiv 3^{15 x}$ である。 $3^{15} \equiv - 1$ なので、 $2 2^{15} \equiv (- 1)^{x}$ となる。 $2 2^{15}$ を直接計算すると $22 \equiv - 9$ 、 $2 2^{2} = 484 \equiv 19$ 、 $2 2^{4} \equiv 361 \equiv 20$ 、 $2 2^{8} \equiv 400 \equiv 28$ である。よって $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 154 - 124 = 30 \equiv - 1$ 。したがって $x$ は奇数、すなわち $x \equiv 1 (mod 2)$ 。

(2) 法 3: $2 2^{10} \equiv (3^{10})^{x} = 2 5^{x}$ である。 $2 2^{10} = 2 2^{8} \cdot 2 2^{2} \equiv 28 \cdot 19 = 532 \equiv 532 - 527 = 5$ 。 $2 5^{2} = 625 \equiv 5$ なので $x \equiv 2 (mod 3)$ 。

(3) 法 5: $2 2^{6} \equiv (3^{6})^{x} = 1 6^{x}$ である。 $2 2^{6} = 2 2^{4} \cdot 2 2^{2} \equiv 20 \cdot 19 = 380 \equiv 380 - 372 = 8$ 。 $1 6^{2} = 256 \equiv 8$ なので $x \equiv 2 (mod 5)$ 。

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

検算: $3^{15} \equiv - 1$ より $3^{17} \equiv - 9 \equiv 22 (mod 31)$ となり、条件を満たす。

暗号理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題