2016年度現代数学入門 B 第9回演習

2016 年度現代数学入門 B 第 9 回演習
演習 9.34. Z×
pe の群構造に関する定理を以下の場合に具体的にチェックせよ．
∼
(1) 群としての同型 Z×
8 = Z/2Z × Z/2Z,
∼
Z×
16 = Z/2Z × Z/4Z を示せ．
(2) 群 Z×
9 が巡回群になることをチェックし，その原始根をすべて求めよ．
(3) 位数 n の元 a で生成される巡回群 ⟨a⟩ の位数 n の元は，{aj (j は n と互いに素)} で与
えられることを示せ．
×
(4) (3) を用いて，Z×
19 , Z25 について，それぞれ巡回群となることをチェックし，その原始
根をすべて求めよ．
演習 9.35. 公開鍵暗号を使ってやり取りしているアリスとボブに対し，その秘密文を解
読しようとしているオスカーの立場で考える．
(1) RSA 暗号を考える．アリスの公開鍵は (n, e) = (899, 11) である．ボブから暗号文 c =
468 がアリスに送られた．ボブの送った元の文 m は何か？
(2) エルガマル暗号を考える．アリスの公開鍵は (p, g, A) = (53, 2, 28) である．ボブから暗
号文 (B, c) = (24, 37) がアリスに送られた．ボブの送った元の文 m は何か？
演習 9.36. n = 21, 91, 105 のそれぞれについて，講義中に述べた J, K, L, M およびミラー・
ラビンテストで n を素数と判定してしまう集合 B を決定せよ．なお，手ですべてを計算す
るのは大変なので，プログラムを書いて求める方が良い．その場合は使用したプログラム
を添付することが望ましい．
演習 9.37. p, q を相異なる素数とし，n = pq とする．
(1) d = gcd(p − 1, q − 1) とする．b が講義で述べた J に属するための必要十分条件は bd ≡ 1
mod n であることを示せ．さらに，講義で述べた J の位数を d で表せ．
(2) q = 2p + 1 の場合，講義で述べた J の元を p を用いてすべて書き出せ．
(3) n = 341 とする．n と互いに素な b をランダムに選んだとき，フェルマーテストによっ
て n が素数の可能性があると判定される確率はいくらか．
演習 9.38. 今回の講義では，合成数 n がカーマイケル数であることの定義を
「n と互いに素なすべての自然数 a に対して，an−1 ≡ 1 mod n が成り立つ」· · · (ア)
とした．カーマイケル数の次の性質①, ②, ③を示したい．
① カーマイケル数は奇数である．
② 合成数 n がカーマイケル数であるための必要十分条件は次の 2 つが成り立つことで
ある．
(i) n を割り切るどんな素数 p に対しても，p − 1 が n − 1 を割り切る．
(ii) どんな素数 q に対しても q 2 は n を割り切らない．
③ カーマイケル数は少なくとも 3 つの相異なる素因数を持つ．
しかし，上の定義 (ア) から②を示すのは難しい．
問 1 次の議論は，カーマイケル数の定義 (ア) から② (i),(ii) が成り立つことを導く証明と
して，ある本に書かれているものである．この証明は不十分である．何が不十分なの
だろうか？少なくともミスプリと思われる箇所が 1 箇所，本質的なギャップが 1 箇
所ある．
問 2 合成数 n がカーマイケル数であることの定義として，
「すべての整数 a に対して，an ≡ a mod n が成り立つ」· · · (イ)
とする方法もある．(イ)⇒(ア) が成り立つことを示せ．（逆は難しい．
）
問 3 定義 (イ) の基づいて，上の性質①, ②, ③を証明せよ．

Download Report