アルゴリズム論特論（塩田）　2017年度教材

アルゴリズム論特論（塩田）　2017年度教材　第7回

授業内容
- n が完全数とは、n 未満の n の約数の和が n に一致すること
  - 6 = 1 + 2 + 3
  - 28 = 1 + 2 + 4 + 7 + 14
- 6 は半年の月の数、28 はひと月の日数
- 完全数を知ることは、この世界を知ることにつながるのではないか。
- 定理Ａ　k も 2^k－1 も素数 ⇒ n = 2^k－1×(2^k－1) は完全数
- 定理Ｂ　n が偶数の完全数 ⇒ 2^k－1 が素数であるような素数 k が存在して n = 2^k－1×(2^k－1)
- フェルマの完全数探索プロジェクト
  - 2^k－1 が素数であるような素数 k をさがせ
  - 予想Ｃ　2^k－1 の約数 q は q ≡ 1 ( mod k ) を満たすらしい
  - 予想Ｃが正しければ 2^k ≡ 2 ( mod k ) ... フェルマの小定理の p = k, a = 2 の場合
  - フェルマは、小定理の証明に成功した。
  - 予想Ｃは逆にフェルマの小定理を使って証明できた。
  - 2^k－1 の素数判定は、q ≡ 1 ( mod k ) を満たす素因数 q のある無しだけ判定すればよくなった。
  - 沢山の完全数をみつけることができた。
ツボ
- 興味を持って研究したことが、300年以上たった今、RSA暗号として役に立つようになった。
- 世の中の研究者全てが直近の目的だけを追って研究している、という状況は良くない。