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

  • 前回の復習

  • 授業内容
    • 素数判定・素数生成
      • フェルマ・テスト（擬素数テスト)
      • ソロベイ・ストラッセン・テスト（オイラー擬素数テスト)
      • ミラー・ラビン・テスト（強擬素数テスト)
    • 高速べき乗法（反復２乗法）

  • サンプルプログラム

  • ツボ
    • 法演算の下でのべき乗等を用いて素数判定ができる。
    • n 程度の素数を生成する計算量は O(log4 n)

戻る