Primality testing
応用数学科 4年
5499053 鈴木 一也
目的
・
LEDAを使用しての、素数判定アルゴリ
ズムの実装と実験。
目次
１．はじめに…
２．用語解説
３．Fermat の小定理とは？
４．Fermat test のアルゴリズムの解説
５．Strong pseudoprimality testとは？
６．Strong pseudoprimality testの解説
７．ドイツ人の論文に載っていたアルゴリズム
１．はじめに…
我々は、ある一定の整数が素数であるかどう
かを知りたい。
それには因数分解することにより、素数判定で
きることが知られている。
しかし、少なくとも現時点では、primality
testing が因数分解よりはるかに簡単であるこ
とが、解かっている。
これから素数生について有効的な見込みのあ
るアルゴリズムを紹介する。
２．用語解説
2.1 RSAとは？
2.2 カーマイケル数とは？
素数pに対し、整数aがな
んであっても
ap ≡ a(mod p)
これから、
(a,p)=1 →
ap-1≡1(mod p)
従ってある整数nが素数
でないことを示すには次
のテストをすればよい。
ある整数aが見つかり
(a,n)=1 →
an-1≠ 1(mod n)
であればnは素数でない。
しかし、逆は成立せず
(a,n)=1 →
an-1≡1(mod n)
となる合成数が存在す
る。
このような合成数をカー
マイケル数と呼ぶ。
2.3 rem と mod の違い。
２．Fermat の小定理とは？
N:素数
a:Nで割り切れない整
数（∀a∈Z）
とすると、
aN-1≡1 mod N
が、成立する。
＊ しかし、逆の命題は
成り立たない。
合成数（素数以外
の数）であっても
Fermatの小定理を
満たす数字が存在す
る。そういった数字を
擬素数という。
３．Fermat test アルゴリズム
の解説
入力：奇数である整数
N≧5
出力：合成数 か 擬素数
1. a∈{2,…,N－2}をランダ
ムで、選ぶ。
2. b=aN-1 rem N の計算。
3. if b ≠ 1 then return
「合成数」
else return 「擬素数」
先ほど紹介したFermat
の小定理
N:素数
a:Nで割り切れない整数
（∀a∈Z）
aN-1≡1 mod N
←
４．Strong pseudoprimality
test
とは？
Fermat test では、素数判定の正確さが
あまりよくなかった。
これでは、RSA暗号には使えない。
そのため、Fermat test よりも 正確なプ
ログラムを作成したい。
そこで、もう少し正確な、素数判定プログ
ラム、Strong pseudoprimality test を、
次に紹介する。
５．Strong pseudoprimality
testの解説
入力：奇数である整数
N≧5
出力：合成数 か 擬素数
1. a∈{2,…,N－2}をランダムで、
選ぶ。
2. a と N の gcd を求める。
3. N－1 = 2k m となる k,m を求
める。（k≧1）
b0 = am rem N の計算
if b0 = 1 then return 「合成数」
b0 ≠ 1 `4番へ`
if b0 = 1 then return 「合成数」
b0 ≠ 1 `4番へ`
4. for 1≦i≦k do bi ← b2i-1 rem
N
bk≠1 なら「合成数」
bk＝1 なら `5番へ`
5. j ← min{0 ≦ i ＜ k :
bi+1 = 1}
6. g ← (bj + 1 , N)
g=1 か g=N ならば「擬素数」
else `1番へ戻る。`
７．ドイツ人の論文に載ってい
たアルゴリズム
これからの課題
プログラムをLEDAになおす。
青い本の理解をすすめる（18章）。
２つのプログラムについての実験、考察。
（確率的にどのくらい、正しい値をかえす
か？また、なぜこのプログラムで正しいの
か？etc...）
© Copyright 2024 ExpyDoc
