暗号理論の問題

方針　$143=11\cdot 13$ と素因数分解し、中国剰余定理によって、法 $11$ と法 $13$ での離散対数の問題に分けて考える。

$$2^x\equiv 19(\mathrm{mod}143)⟺2^x\equiv 19(\mathrm{mod}11)\text{ かつ }{2}^x\equiv 19(\mathrm{mod}13)$$

であり、$19\equiv 8(\mathrm{mod}11)$、$19\equiv 6(\mathrm{mod}13)$ である。

法 $11$ について　$2$ のべきを順に計算すると
$$2^1=2,2^2=4,2^3=8,2^4\equiv 5,2^5\equiv 10\equiv -1(\mathrm{mod}11)$$
である。$2^5\equiv -1$ より $2^{10}\equiv 1$ となり、$2^2\not\equiv 1$、$2^5\not\equiv 1$ なので、$2$ の位数は $10$ である（$2$ は法 $11$ の原始根）。$2^3\equiv 8$ だから
$$2^x\equiv 8(\mathrm{mod}11)⟺x\equiv 3(\mathrm{mod}10).(1)$$

法 $13$ について　
$$2^1=2,2^2=4,2^3=8,2^4\equiv 3,2^5\equiv 6,2^6\equiv 12\equiv -1(\mathrm{mod}13)$$
である。$2^6\equiv -1$ より $2^{12}\equiv 1$ となり、$2^4\equiv 3\not\equiv 1$、$2^6\not\equiv 1$ なので、$2$ の位数は $12$ である（$2$ は法 $13$ の原始根）。$2^5\equiv 6$ だから
$$2^x\equiv 6(\mathrm{mod}13)⟺x\equiv 5(\mathrm{mod}12).(2)$$

連立合同式を解く　$\gcd (10,12)=2$ であり、$3\equiv 5(\mathrm{mod}2)$ なので $(1)$, $(2)$ は両立し、解は法 $\mathrm{lcm}(10,12)=60$ でただ一つに定まる。$(2)$ より $x=12k+5$（$k$ は整数）とおくと、$(1)$ から
$$12k+5\equiv 3(\mathrm{mod}10)⟺2k\equiv -2(\mathrm{mod}10)⟺k\equiv 4(\mathrm{mod}5).$$
よって $x=12(5j+4)+5=60j+53$（$j$ は整数）となり、
$$x\equiv 53(\mathrm{mod}60)$$
を得る。なお、法 $143$ での $2$ の位数は $\mathrm{lcm}(10,12)=60$ である。

したがって最小の正の整数解は $x=53$ である。

検算　$2^{10}=1024\equiv 23$、$2^{20}\equiv 23^2=529\equiv 100$、$2^{40}\equiv 100^2=10000\equiv 133$、$2^{50}\equiv 133\cdot 23=3059\equiv 56$、$2^{53}\equiv 56\cdot 8=448\equiv 19(\mathrm{mod}143)$ となり、正しい。

答え　$53$

$143=11\cdot 13$ なので、中国剰余定理で各素数を法として考える。

(1) 法 11: $19\equiv 8(\mathrm{mod}11)$。2 の累乗は $2^1=2,2^2=4,2^3=8$ なので $2^3\equiv 8$。2 の位数は 10 (原始根) なので $x\equiv 3(\mathrm{mod}10)$。

(2) 法 13: $19\equiv 6(\mathrm{mod}13)$。$2,4,8,16\equiv 3,6$ より $2^5\equiv 6$。2 の位数は 12 (原始根) なので $x\equiv 5(\mathrm{mod}12)$。

(3) 連立合同式: $x=3+10k$ とおくと $3+10k\equiv 5(\mathrm{mod}12)$ より $10k\equiv 2(\mathrm{mod}12)$、すなわち $5k\equiv 1(\mathrm{mod}6)$ なので $k\equiv 5(\mathrm{mod}6)$。よって $x=53$、周期は $\mathrm{lcm}(10,12)=60$、すなわち $x\equiv 53(\mathrm{mod}60)$。

検算: $53\mathrm{mod}10=3$、$53\mathrm{mod}12=5$ で両方満たす。したがって $2^{53}\equiv 8\equiv 19(\mathrm{mod}11)$ かつ $2^{53}\equiv 6\equiv 19(\mathrm{mod}13)$ となり、$2^{53}\equiv 19(\mathrm{mod}143)$。最小の正の整数解は 53。