暗号理論の問題

$p-1=72=2^3\cdot 3^2$ なので、Pohlig–Hellman の方法で $x\mathrm{mod}8$ と $x\mathrm{mod}9$ を別々に求め、中国剰余定理でつなぐ。

準備. $5$ のべきを計算しておく（法 $73$）。
$$5^2=25,5^3=125\equiv 52,5^6\equiv 52^2=2704=73\cdot 37+3\equiv 3.$$
また $42^2=1764=73\cdot 24+12\equiv 12$、$42^4\equiv 144\equiv -2$、$42^8\equiv 4$。

$x\mathrm{mod}8$ を求める. 両辺を $9$ 乗すると、位数 $8$ の元についての離散対数問題
$$(5^9{)}^x\equiv 42^9$$
になる。$5^9=5^6\cdot 5^3\equiv 3\cdot 52=156\equiv 10$、$42^9=42^8\cdot 42\equiv 4\cdot 42=168\equiv 22$。よって $10^x\equiv 22$ で、$10$ の位数は $8$。
$10^2\equiv 27$、$10^4\equiv 27^2=729\equiv -1$、$10^{-1}\equiv 22$（$10\cdot 22=220=3\cdot 73+1$）。
$x\equiv x_0+2x_1+4x_2(\mathrm{mod}8)$（$x_i\in \{0,1\}$）とおく。
- $22^4$: $22^2=484\equiv 46$、$46^2=2116=73\cdot 28+72\equiv -1$。$22^4\equiv -1=(10^4{)}^{x_0}$ より $x_0=1$。
- $22\cdot 10^{-1}\equiv 22\cdot 22\equiv 46$。$46^2\equiv -1=(10^4{)}^{x_1}$ より $x_1=1$。
- $46\cdot 10^{-2}\equiv 46\cdot 22^2\equiv 46\cdot 46\equiv -1=(10^4{)}^{x_2}$ より $x_2=1$。

したがって $x\equiv 1+2+4=7(\mathrm{mod}8)$。

$x\mathrm{mod}9$ を求める. 両辺を $8$ 乗すると
$$(5^8{)}^x\equiv 42^8\equiv 4.$$
$5^8=5^6\cdot 5^2\equiv 3\cdot 25=75\equiv 2$。$2$ の位数は $9$（$2^3=8\not\equiv 1$、$2^9=512=73\cdot 7+1\equiv 1$）。$2^x\equiv 4=2^2$ より $x\equiv 2(\mathrm{mod}9)$。

中国剰余定理. $x\equiv 2(\mathrm{mod}9)$ を満たす $0\le x\le 71$ は $2,11,20,29,38,47,56,65$ で、このうち $x\equiv 7(\mathrm{mod}8)$ となるのは $47$ だけである。

検算. $5^{36}\equiv -1$（原始根なので）、$5^{11}=5^6\cdot 5^3\cdot 5^2\equiv 3\cdot 52\cdot 25$。$3\cdot 52=156\equiv 10$、$10\cdot 25=250=3\cdot 73+31\equiv 31$。よって $5^{47}=5^{36}\cdot 5^{11}\equiv -31\equiv 42$ で正しい。

よって $x=47$。

$5$ の冪を法 $73$ で順に計算する: $5^1=5,5^2=25,5^3=52,5^4=41,5^5=59,5^6=3,5^7=15,5^8=2$。よって $3\equiv 5^6$, $2\equiv 5^8$。さらに続けて $5^9=10,5^{10}=50,5^{11}=31,5^{12}=9,5^{13}=45,5^{14}=6,5^{15}=30,5^{16}=4,5^{17}=20,5^{18}=27,5^{19}=62,5^{20}=18,5^{21}=17,5^{22}=12,5^{23}=60,5^{24}=8,5^{25}=40,5^{26}=54,5^{27}=51,5^{28}=36,5^{29}=34,5^{30}=24,5^{31}=47,5^{32}=16,5^{33}=7$。よって $7\equiv 5^{33}$。

$42=2\cdot 3\cdot 7\equiv 5^8\cdot 5^6\cdot 5^{33}=5^{47}$。

検算: $5^{36}\equiv 5^{33}\cdot 5^3=7\cdot 52=364\equiv -1(\mathrm{mod}73)$（位数 $72$ の原始根で $5^{36}\equiv -1$ となるはずで、一致する）。よって $5^{47}=5^{36}\cdot 5^{11}\equiv -31\equiv 42(\mathrm{mod}73)$。確かに成り立つ。$0\le x\le 71$ の範囲で一意なので $x=47$。