シルヴァーマン 「はじめての数論」第3版 第18章練習問題

18.1

FERMAT (フェルマー)

18.2

(a)共通因数を持たなければ、アルゴリズム17.1が適用できるから。

(b)

暗号化はmを法としているから、mより長いメッセージと、

mを法として合同なメッセージとは区別できない。

だからメッセージはmより短くしなければならない。

アルゴリズム17.1の過程が満たされていれば、

mより短いメッセージは唯一の解に必ず復号できる。

gcd(a,m)=pでも、練習問題17.4により復号できる。

(c)

φ(m)=6なので、kの選択肢としてはk=5しかない。

暗号化は3⁵≡9 (mod 18)だが、

gcd(9,18) ≠1で18は相異なる素数の積でもない（練習問題17.4）のでうまくいかない。

実際、x⁵≡9 (mod 18)を強引にアルゴリズム17.1で解くと、

x≡9≠3 (mod 18)となり復号できていない。

18.3, 18.6

…ウィキペとか

18.4
(a)

6番目と10番目の暗号は誤植。正しくは
6番目：26945939925、10番目：2163791130（原著者公式参照）。
誤植を直して復号すると

Mathematics is the queen of science and number theory is the queen of mathematics. K. F. Gauss.

（数学は科学の女王であり、数論は数学の女王である。K. F. ガウス）