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

  • 授業内容
    • 剰余類、既約剰余類
    • オイラー関数　φ(n) = ( 法 n の既約剰余類の個数 )
    • オイラーの定理　gcd(a, n) = 1 ⇒ 法 n で a φ(n) = 1
    • 命題　 p が素数で、e, d が ed ≡ 1 ( mod (p-1) ) を満たす自然数ならば、
      任意の整数 x に対して  xed ≡ x ( mod p )
    • 暗号 E : P → C, D : C → P が次のように設計できる：
      • 平文集合　 P = {0, 1, ..., p-1}
      • 暗号文集合 C = {0, 1, ..., p-1}
      • 暗号化関数 E(x) = xe % p
      • 復号化関数 D(y) = yd % p

  • 宿題
    • 上記の暗号は公開鍵暗号になり得るか？

  • ツボ
    • フェルマの小定理は、オイラーの定理で n が素数の場合
    • オイラーの定理は群論的に証明される

戻る