暗号理論の問題

位数 12 の元を離散対数で表す. $2$ は法 $37$ の原始根なので、$1\le a\le 36$ の各 $a$ は $a\equiv 2^t(\mathrm{mod}37)$（$0\le t\le 35$）とただ 1 通りに表せる。このとき $a$ の位数は
$$\frac{36}{\gcd (t,36)}$$
である。これが $12$ になるのは $\gcd (t,36)=3$ のとき、すなわち $t=3s$（$0\le s\le 11$）で $\gcd (s,12)=1$ のときである。よって $s=1,5,7,11$、つまり
$$t=3,15,21,33$$
の 4 個（個数は $\phi (12)=4$ と一致する）。

値を計算する. $\mathrm{mod}37$ で
- $2^3=8$
- $2^5=32$, $2^{10}=1024=27\cdot 37+25$ より $2^{10}\equiv 25$。$2^{15}=2^{10}\cdot 2^5\equiv 25\cdot 32=800=21\cdot 37+23$ より $2^{15}\equiv 23$
- $2^{18}\equiv -1$（$2$ が原始根なので $2^{18}\not\equiv 1$ かつ $(2^{18}{)}^2\equiv 1$）。$2^{21}=2^{18}\cdot 2^3\equiv -8\equiv 29$
- $2^{33}=2^{18}\cdot 2^{15}\equiv -23\equiv 14$

よって位数 $12$ の元は $8,23,29,14$ である。

確認. 例えば $8=2^3$ について、$8^4=2^{12}\equiv 25\cdot 4=100\equiv 26\ne 1$、$8^6=2^{18}\equiv -1\ne 1$、$8^{12}=2^{36}\equiv 1$ なので位数は $12$。また、これら 4 個は円分多項式 ${\Phi }_{12}(x)=x^4-x^2+1$ の $\mathrm{mod}37$ での根であり、$x^3$ の係数が $0$ だから和は $\equiv 0(\mathrm{mod}37)$ のはずである。実際
$$8+23+29+14=74=2\cdot 37$$
で整合する。

したがって求める総和は $74$ である。

2 は法 37 の原始根なので、$1\le a\le 36$ の各 $a$ はただ 1 通りに $a\equiv 2^k$ $(1\le k\le 36)$ と書け、$a$ の位数は $36/\gcd (k,36)$ である。位数がちょうど 12 となる条件は $\gcd (k,36)=3$。$1\le k\le 36$ でこれを満たすのは $k=3,15,21,33$ の 4 個（$\phi (12)=4$ と一致）。\n\n2 のべきを法 37 で計算する: $2^3=8$, $2^6=64\equiv 27$, $2^9\equiv 31$, $2^{12}\equiv 26$, $2^{15}=2^{12}\cdot 8=208\equiv 208-185=23$, $2^{18}\equiv -1$（$2^{18}=2^{15}\cdot 8=184\equiv 184-148=36$）。よって $2^{21}=-2^3\equiv -8\equiv 29$, $2^{33}=-2^{15}\equiv -23\equiv 14$。\n\nしたがって該当する $a$ は $8,23,29,14$。総和は $8+23+29+14=74$。\n\n検算: $8^4=4096\equiv 26$, $26^3=17576\equiv 1(\mathrm{mod}37)$ より $8^{12}\equiv 1$、かつ $8^4\equiv 26\ne 1$, $8^6\equiv 27^2=729\equiv 26\ne 1$ なので位数は 12。また 1 の原始 12 乗根の総和は $\mu (12)=0$ なので和は 37 の倍数のはずで、$74=2\cdot 37$ と整合する。