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

  • 授業内容
    • フェルマ・テストによる素数判定： 
      入力：n
出力：n が素数か否か
while 十分な回数:
    b = ( 2 以上 n 未満の乱数 )
    if gcd(b, n) > 1:
        return False
    if b ** (n - 1) % n != 1:
        return False
return True
    • n 位の大きさの数はおおよそ log(n) 個に１個が素数
    • フェルマ・テストによる素数生成の計算量は O(log4n)
    • フェルマ・テストでは素数と誤判定されるカーマイケル数という数があるが、 それほど多くない。

  • ツボ
    • 素数判定・素数生成も、高速べき乗法の応用で実装できる。

  • 宿題
    • RSA暗号の鍵 p, q, n, e, d を、p が 510ビット、q が 515ビット程度になるように生成し、 公開鍵 n, e を塩田に送信せよ。秘密鍵は各自保管しておくこと。
    • 折り返し塩田から暗号文を返送するので復号せよ。 正しく復号できれば復号文は８桁の数字になり、西暦４桁＋月２桁＋日２桁である著名人の誕生日を表している。 その著名人を答えよ。
    • メールは ここ から。

戻る