この章のまとめ

(1) $\bmod5$ では $2,4,3,1$ で位数 $4$、$\bmod7$ では $2,4,1$ で位数 $3$ なので、中国剰余定理から $r=\operatorname{lcm}(4,3)=12$ である。$r$ は偶数で、$2^6=64\equiv29$ は $-1\equiv34$ でない。$\gcd(28,35)=7$、$\gcd(30,35)=5$ で、$35=5\times7$ である。

(2) $35^2=1225$ で $2^{10}=1024<1225\le2048=2^{11}$ なので $t=11$ である。山は $2048s/12=170.67s$ の近く、$s=0,\dots,11$ の12か所に立つ。$2048s/12$ が整数になるのは $s$ が3の倍数のとき（$0,512,1024,1536$）で、この4本は山が1本で高さ $1/12=0.0833$ である。他の8本は最も近い $m$ で $2^{11}\delta=\pm1/3$ となり、例題 6.3.4 と同じく条件付き確率 $0.684$、高さ $0.0570$ である。最も近い $m$ のどれかが出る確率は $4\times0.0833+8\times0.0570=0.789$ で、$\gcd(s,12)=1$ の $s=1,5,7,11$ に限ると $4\times0.0570=0.228$ である。どちらも $N=21$ と同じ値になるのは、$r=6$ と $r=12$ がともに $2^t/r$ の端数を $\pm1/3$ にするからである。

(3) $1195/2048=[0;1,1,2,2,42,4]$ で、近似分数は $1/1$、$1/2$、$3/5$、$7/12$、$297/509,\dots$ である。分母 $q<35$ の候補 $1,2,5,12$ を順に試すと、$2^1$、$2^2$、$2^5=32$ は $1$ でなく、$2^{12}\equiv1$ で $r=12$ を得る。誤差は $\lvert 1195/2048-7/12\rvert =1/6144\le1/4096$ である。$m=512$ は $512/2048=1/4$ で $s=3$ の山、約分で分母 $4$ が出て $2^4=16\not\equiv1$ である。$m=1365$ は $s=8$ の山（$1365.33$）で、近似分数に $2/3$ が現れ分母 $3$ だが $2^3=8\not\equiv1$ である。2つを合わせて $\operatorname{lcm}(4,3)=12$ を試すと $2^{12}\equiv1$ で位数が分かる。

(4) 数値で $H(M)=3.311$、$H(M\,|\,S)=0.830$、$I(S;M)=2.481$ nat で、$\ln12=2.485$ の $99.8\%$ である。$D(P_M\,\|\,u)=t\ln2-H(M)=7.625-3.311=4.314$ nat である。$N=21$ と比べて $I(S;M)$ は $\ln12-\ln6=\ln2$ ほど増え、$t$ も2増えたので $D$ も増えた。$35<2^6$ で第2のレジスタは $n=6$ 量子ビット、$n\ln2=4.159\ge\ln12$ で、周期の情報 $\ln r$ はレジスタの容量の中に収まる。第1のレジスタの容量 $t\ln2=7.625$ は $\ln r$ の3倍ほどで、残りは連分数で分母を一意に読むための精度に使われている。

(5) $\phi(35)=24$、$5\cdot5=25\equiv1\pmod{24}$ なので $d=5$ である。$c=2^5=32$ である。$32=2^5$ で $\gcd(5,12)=1$ なので $\operatorname{ord}_{35}(32)=\operatorname{ord}_{35}(2)=12$ で、(1) の位数がそのまま使える。$d'=5^{-1}\bmod12=5$（$25\equiv1$）で、$32^5=2^{25}=2^{2\cdot12+1}\equiv2\pmod{35}$ となり、平文 $2$ が戻る。位数を求める同じ回路が、因数分解にも RSA の復号にも使える。