ポーリッヒ・ヘルマン法による離散対数

$p - 1 = \prod q_{i}^{e_{i}}$ と分解し、各 $q_{i}^{e_{i}}$ について $(g^{(p - 1) / q_{i}^{e_{i}}})^{x} \equiv h^{(p - 1) / q_{i}^{e_{i}}}$ から $x mod q_{i}^{e_{i}}$ を求め、中国剰余定理でまとめて $5^{x} \equiv 42 (mod 73)$ のような離散対数 $x$ を求められる

前提

繰り返し二乗法によるべき剰余（大学数学暗号理論）
剰余類環の単元群とオイラー関数（大学数学代数学）

この技能までの道筋（25 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
約数の見つけ方（算数整数の性質）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
n 進法（数学A 整数の性質）
繰り返し二乗法によるべき剰余（大学数学暗号理論）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
群の位数と元の位数（大学数学代数学）
有限アーベル群の構造と部分群の個数（大学数学代数学）
剰余類環の単元群とオイラー関数（大学数学代数学）

説明

素数 $p$ と $mod p$ の原始根 $g$ 、および $p$ で割り切れない整数 $h$ が与えられたとき、 $g^{x} \equiv h (mod p)$ を満たす指数 $x$ （離散対数）を求める方法です。 $p - 1$ が小さな素因数だけに分解できる場合、 $x$ を $0$ から順に全部試さなくても、 $x$ を「小さな法での余り」に分けて求め、最後に中国剰余定理で組み立てられます。暗号の安全性を考えるときにも、「 $p - 1$ が小さな素因数ばかりだと離散対数が簡単に解けてしまう」ことを示す基本的な手法として使われます。

なぜそうしてよいのか

$g$ が原始根であるとは、 $g$ の $(Z / p Z)^{\times}$ での位数が $n = p - 1$ であることです。このとき $g^{0}, g^{1}, \dots, g^{n - 1}$ は $1$ から $p - 1$ までの剰余類をちょうど 1 回ずつとります。したがって $g^{x} \equiv h$ の解 $x$ は $mod n$ で一つに決まり、 $g^{a} \equiv g^{b} ⟺ a \equiv b (mod n)$ が成り立ちます。

$n = \prod q_{i}^{e_{i}}$ と素因数分解し、 $m_{i} = n / q_{i}^{e_{i}}$ とおきます。元の位数の性質から、 $g_{i} = g^{m_{i}}$ の位数は $n / g cd (n, m_{i}) = q_{i}^{e_{i}}$ です。 $g^{x} \equiv h$ の両辺を $m_{i}$ 乗すると $g_{i}^{x} \equiv h_{i}$ （ただし $h_{i} = h^{m_{i}}$ ）が得られます。 $g_{i}$ の位数は $q_{i}^{e_{i}}$ なので、 $g_{i}^{y} \equiv h_{i}$ を満たす $y$ はちょうど $y \equiv x (mod q_{i}^{e_{i}})$ となる $y$ です。つまり位数 $q_{i}^{e_{i}}$ の小さな群で離散対数を解けば、 $x mod q_{i}^{e_{i}}$ がわかります。調べる候補は $n$ 個ではなく $q_{i}^{e_{i}}$ 個で済みます。

$q_{1}^{e_{1}}, q_{2}^{e_{2}}, \dots$ はどの 2 つも互いに素です。そのため、すべての $i$ について $x mod q_{i}^{e_{i}}$ がわかれば、中国剰余定理によって $x mod n$ がただ一つに決まります。なお $q_{i}^{e_{i}}$ が大きいときは、 $x mod q_{i}^{e_{i}}$ を $q_{i}$ 進法の各桁に分けて 1 桁ずつ求めると、各桁は位数 $q_{i}$ の群での離散対数になり、さらに計算が軽くなります。

手順

$p - 1 = \prod q_{i}^{e_{i}}$ と素因数分解し、 $g$ の位数が $p - 1$ （原始根）であることを確かめる。
各 $i$ について $m_{i} = \frac{p - 1}{q _{i}^{e_{i}}}$ とし、繰り返し二乗法で $g_{i} \equiv g^{m_{i}}$ 、 $h_{i} \equiv h^{m_{i}} (mod p)$ を計算する。
$g_{i}^{x_{i}} \equiv h_{i}$ を満たす $x_{i}$ を $0 \leq x_{i} < q_{i}^{e_{i}}$ の中から探す。 $g_{i}$ のべきを順に並べて $h_{i}$ と比べればよい。 $e_{i}$ が大きいときは $q = q_{i}, e = e_{i}$ として $x_{i} = d_{0} + d_{1} q + \dots + d_{e - 1} q^{e - 1}$ と書く。 $γ = g_{i}^{q^{e - 1}}$ とおき、 $k = 0, 1, \dots, e - 1$ の順に $(h_{i} g_{i}^{- (d_{0} + \dots + d_{k - 1} q^{k - 1})})^{q^{e - 1 - k}} \equiv γ^{d_{k}}$ から各桁 $d_{k}$ を決める。
中国剰余定理で、連立合同式 $x \equiv x_{i} (mod q_{i}^{e_{i}})$ を解き、 $0 \leq x < p - 1$ の $x$ を求める。
繰り返し二乗法で $g^{x} \equiv h (mod p)$ となることを確かめる。

例題

$2$ は $mod 37$ の原始根である。 $2^{x} \equiv 5 (mod 37)$ を満たす整数 $x$ で $0 \leq x < 36$ となるものを求めよ。

例題の解答

【手順 1】 $p - 1 = 36 = 2^{2} \cdot 3^{2}$ です。原始根であることも確かめておきます。 $2^{12} = 4096 \equiv 26$ 、 $2^{18} \equiv 26 \cdot 64 = 1664 \equiv 36 \equiv - 1 (mod 37)$ です。36 の約数のうち 36 以外の最大のものは 12 と 18 で、36 未満のどの約数もこのどちらかを割ります。 $2^{12} \neq \equiv 1$ 、 $2^{18} \neq \equiv 1$ なので、2 の位数は 36 です。

【手順 2・3（法 $4$ ）】 $m = 36/4 = 9$ です。 $g_{1} \equiv 2^{9} = 512 \equiv 31 (mod 37)$ となります。 $h_{1} \equiv 5^{9}$ は $5^{2} = 25$ 、 $5^{4} = 625 \equiv 33$ 、 $5^{8} \equiv 3 3^{2} = 1089 \equiv 16$ から $5^{9} \equiv 16 \cdot 5 = 80 \equiv 6$ と求まります。 $31$ のべきを並べると、 $3 1^{0} \equiv 1$ 、 $3 1^{1} \equiv 31$ 、 $3 1^{2} \equiv 961 \equiv 36$ 、 $3 1^{3} \equiv 36 \cdot 31 \equiv - 31 \equiv 6$ です。よって $x \equiv 3 (mod 4)$ です。

【手順 2・3（法 $9$ ）】 $m = 36/9 = 4$ です。 $g_{2} \equiv 2^{4} = 16$ 、 $h_{2} \equiv 5^{4} \equiv 33 (mod 37)$ となります。 $16$ のべきを並べると、 $1 6^{1} \equiv 16$ 、 $1 6^{2} = 256 \equiv 34$ 、 $1 6^{3} \equiv 34 \cdot 16 = 544 \equiv 26$ 、 $1 6^{4} \equiv 26 \cdot 16 = 416 \equiv 9$ 、 $1 6^{5} \equiv 9 \cdot 16 = 144 \equiv 33$ です。よって $x \equiv 5 (mod 9)$ です。

【手順 4】 $x \equiv 5 (mod 9)$ を満たす $0 \leq x < 36$ の候補は $5, 14, 23, 32$ です。このうち $4$ で割って余り $3$ になるのは $23$ だけなので、 $x = 23$ です。

【手順 5】 $2^{23} = 2^{18} \cdot 2^{5} \equiv (- 1) \cdot 32 = - 32 \equiv 5 (mod 37)$ となり、正しいことが確かめられます。

答え: $23$

よくある誤り

素数のべき $q_{i}^{e_{i}}$ ではなく素数 $q_{i}$ で割った指数 $(p - 1) / q_{i}$ を使ってしまう誤り。例題で $36/3 = 12$ 乗すると、わかるのは $x mod 3$ だけです。正しくは $36/ 3^{2} = 4$ 乗して $x mod 9$ を求めます（または 3 進法の桁を 2 つとも求めます）。
答えを $mod p$ で考えてしまう誤り。指数は $mod p$ ではなく $mod (p - 1)$ （ $g$ の位数）で決まります。例題でも $2^{23} \equiv 2^{59} (mod 37)$ が成り立ちます。答えは $x \equiv 23 (mod 36)$ と考え、 $0 \leq x < 36$ の範囲で答えます。
片方の辺だけをべき乗してしまう誤り。たとえば $g^{m}$ を作ったのに $h$ のまま $(g^{m})^{x_{i}} \equiv h$ を解いてしまう場合です。正しくは両辺を同じ $m_{i}$ 乗して $(g^{m_{i}})^{x_{i}} \equiv h^{m_{i}}$ を解きます。
$g$ が原始根かどうか確かめずに使ってしまう誤り。 $g$ の位数 $N$ が $p - 1$ より小さいと、解がない場合や $mod (p - 1)$ で一つに決まらない場合があります。 $mod 37$ では $2^{12} \neq \equiv 1$ かつ $2^{18} \neq \equiv 1$ であることを確かめてから使います。位数が $N$ の $g$ を使うときは、 $p - 1$ の代わりに $N$ を素因数分解します。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

難易度 4（大学院入試の標準レベル）
素数 $p = 73$ について、 $g = 5$ は法 $73$ の原始根である（ $5$ の法 $73$ での位数は $72$ ）。
$5^{x} \equiv 42 (mod 73), 0 \leq x \leq 71$
を満たす整数 $x$ （ $42$ の底 $5$ に関する離散対数）を求めよ。