アルゴリズム論特論（塩田） 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ビット程度の素数を作ってみよ。
戻る