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

  • 授業内容 その１：素数の個数
    • 素数が無限個存在することの証明
    • 算術級数定理
    • 素数定理： x 以下の素数の個数 ～ x / log(x)
  • 授業内容 その２：べき乗による変換
    • 命題
           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 位の大きさの数はおおよそ log(n) 個に１個が素数
    • フェルマ・テストやミラー・ラビン・テストを用いて n 位の大きさの素数を生成する計算量は O(log4(n))
    • 素数を法とするべき乗変換は公開鍵暗号にならない

戻る