アルゴリズム論特論(塩田) 2015年度教材 第7回

  • 授業内容
    • 反復二乗法(高速べき乗法)
    • 擬素数、フェルマ・テスト
    • 強擬素数、ミラー・ラビン・テスト

  • ツボ
    • 暗号理論に必須な ae mod n の計算は、二乗を上手く使って高速化できる。

  • 宿題
    • 反復二乗法を実装することにより、下記の素数 p たちについて、フェルマの小定理
            2p - 1 ≡ 1 ( mod p )
      を確かめてみよ。
    • (1)  p = 607 ( 10-bit )
      (2)  p = 552259 ( 20-bit )
      (3)  p = 900949267 ( 30-bit )
      (4)  p = 660768960311 ( 40-bit )
      (5)  p = 661425977735249 ( 50-bit )

  • 発展課題
    • フェルマ・テスト、またはミラー・ラビン・テストを実装して512ビット程度の素数を作ってみよ。

戻る