アルゴリズム論特論（塩田） 2016年度教材 第6回
授業内容
反復二乗法（高速べき乗法）
フェルマ・テストによる素数判定
ミラー・ラビン・テストによる素数判定
ツボ
暗号設計に必須な a
e
mod n の計算は、二乗を上手く使って高速化できる。
フェルマ・テストやミラー・ラビン・テストには a
e
mod n の計算を用いる。
問題
フェルマ・テストあるいはミラー・ラビン・テストを用いて
10
50
＜ p ＜ 10
50
+ 1000
の範囲の素数 p を全て求めよ。
戻る