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

  • 授業内容
    • 素数が無限個存在することの証明
      • ユークリッドによる証明
      • オイラーによる証明

    • 素数定理
           x 以下の素数の個数 ～ x / log(x)

    • n 位の大きさの数はおおよそ log(n) 個に１個が素数

    • 命題
           p : 素数
           e, d : gcd(e, p-1) = 1, 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 位の大きさの素数を生成する計算量は O(log4(n))

  • 宿題
    • 素数を法とするべき乗変換は公開鍵暗号になり得るか

戻る