暗号理論の問題

方針　$30=2\cdot 3\cdot 5$ なので、$x\mathrm{mod}2,x\mathrm{mod}3,x\mathrm{mod}5$ をそれぞれ求め、中国剰余定理でまとめる。各素因数 $q$ について、$3^x\equiv 11$ の両辺を $\frac{30}{q}$ 乗すると
$${\left(3^{30/q}\right)}^x\equiv 11^{30/q}(\mathrm{mod}31)$$
となる。$3^{30/q}$ の位数は $q$ なので、この式から $x\mathrm{mod}q$ が決まる。

準備（べき剰余の計算）
$3$ のべき: $3^2=9,3^4=81\equiv 19,3^5=3^4\cdot 3=57\equiv 26,3^6=26\cdot 3=78\equiv 16,3^{10}=(3^5{)}^2=26^2=676\equiv 676-651=25,3^{15}=3^{10}\cdot 3^5=25\cdot 26=650\equiv 650-620=30\equiv -1$。
$11$ のべき（繰り返し二乗法）: $11^2=121\equiv 121-93=28\equiv -3,11^4\equiv (-3{)}^2=9,11^8\equiv 81\equiv 19$。

(1) $q=2$（$30/2=15$ 乗）
$3^{15}\equiv -1$。$11^{15}=11^8\cdot 11^4\cdot 11^2\cdot 11\equiv 19\cdot 9\cdot (-3)\cdot 11$。$19\cdot 9=171\equiv 16$, $16\cdot (-3)=-48\equiv 14$, $14\cdot 11=154\equiv 154-124=30\equiv -1$。
よって $(-1{)}^x\equiv -1$ より $x\equiv 1(\mathrm{mod}2)$。

(2) $q=3$（$30/3=10$ 乗）
$3^{10}\equiv 25$。$11^{10}=11^8\cdot 11^2\equiv 19\cdot (-3)=-57\equiv 5$。
$25^x\equiv 5$ を $x=0,1,2$ で調べる: $25^0=1,25^1=25,25^2=625\equiv 625-620=5$。よって $x\equiv 2(\mathrm{mod}3)$。

(3) $q=5$（$30/5=6$ 乗）
$3^6\equiv 16$。$11^6=11^4\cdot 11^2\equiv 9\cdot (-3)=-27\equiv 4$。
$16^x\equiv 4$ を調べる: $16^1=16,16^2=256\equiv 256-248=8,16^3\equiv 8\cdot 16=128\equiv 128-124=4$。よって $x\equiv 3(\mathrm{mod}5)$。

(4) 中国剰余定理でまとめる
$x\equiv 1(\mathrm{mod}2)$ かつ $x\equiv 2(\mathrm{mod}3)$ より $x\equiv 5(\mathrm{mod}6)$。$0\le x\le 29$ の候補は $5,11,17,23,29$ で、このうち $5$ で割って $3$ 余るのは $23$。

確かめ　$3^{23}=3^{15}\cdot 3^8$, $3^8=3^4\cdot 3^4\equiv 19^2=361\equiv 361-341=20$ なので $3^{23}\equiv -20\equiv 11(\mathrm{mod}31)$。正しい。

よって $x=23$。

法 $31$ で $3$ の冪を順に計算する（検算用）と $3^{15}\equiv -1$、$3^{18}\equiv 4$、$3^{20}\equiv 5$、$3^{23}\equiv 11$ となる。以下、ポーリッヒ・ヘルマン法で $x$ を $30=2\cdot 3\cdot 5$ の各素因数ごとに求める。

(1) 法 $2$: $11^{15}\equiv \pm 1$ を調べる。$11^2=121\equiv 28$、$11^3\equiv 28\cdot 11=308\equiv 29$、$11^6\equiv 29^2=841\equiv 4$、$11^{12}\equiv 16$ より $11^{15}=11^{12}\cdot 11^3\equiv 16\cdot 29=464\equiv 464-434=30\equiv -1$。$g^{15}\equiv -1$ なので $x\equiv 1(\mathrm{mod}2)$。

(2) 法 $3$: $11^{10}=11^6\cdot 11^3\cdot 11\equiv 4\cdot 29\cdot 11=1276\equiv 1276-1271=5$。$g^{10}\equiv 25$、$g^{20}\equiv 5$ なので $x\equiv 2(\mathrm{mod}3)$。

(3) 法 $5$: $11^6\equiv 4$。$g^6\equiv 16$ に対し $(g^6{)}^k\equiv 3^{6k}$ で、$3^{18}\equiv 4$ より $k=3$。よって $x\equiv 3(\mathrm{mod}5)$。

(4) 中国剰余定理: $x\equiv 1(\mathrm{mod}2)$、$x\equiv 2(\mathrm{mod}3)$ より $x\equiv 5(\mathrm{mod}6)$。$x\equiv 3(\mathrm{mod}5)$ と合わせると、候補 $5,11,17,23,29$ のうち $\mathrm{mod}5$ が $3$ になるのは $23$。よって $x=23$。

検算: 冪の表から $3^{23}\equiv 11(\mathrm{mod}31)$ が成り立つ。