素数判定の効率性について 東邦大学理学部情報科学科卒業研究発表会 指導教員 白柳 潔 提出者 5509036 後藤 雄大 さまざまな素数判定法 決定的な素数判定法 ・試し割り法 ・Eratosthenesの篩 ・APR ・ECPP ・AKS素数判定法 確率的素数判定法 ・Fermatテスト ・Solovay-Strassenテスト ・Miller-Rabin素数判定法 研究目的 ・素数判定法の把握 ・素数判定に必要な定理や性質を理解 三つの素数判定法の効率はどの ようになるか。 素数判定法の時間の比較とFermatテス トにおけるCarmichael数の出現率について Maple14を用いて計算機実験を行った。 Fermatテスト（確率的素数判定法） 対 偶 実行を繰り返し行っていくと．．． n=561とすると「合成数」や「素数」と判定にばらつきがある。 なぜか。。。 Carmichael数 Carmichael数を250回fermatテスト で実行したときの「合成数」と判定す る割合。 グラフを見ると… Carmichael数を大きくしていくと 「合成数」と判定する確率が下がってい る。 試し割り法（決定的素数判定法） ・最も初歩的な素数判定法 ・2から まで一回一回割り切れるかを判定して、自然数nの素数判定を行う。 判定結果 数 判定結果 実行時間 (s) 数 判定結果 実行時間 (s) 2 素数 0.01 7 素数 0.01 3 素数 0.01 8 合成数 0.01 4 合成数 0.01 9 合成数 0.01 5 素数 0.01 10 合成数 0.01 6 合成数 0.01 11 素数 0.01 AKS素数判定法（決定的素数判定 与えられた自然数が素数であるかどうかを決定的多項式時間で判定できる、世界初の 法） アルゴリズム Fermatの小定理を改良 判定結果 数 判定結果 実行時間 (s) 数 判定結果 実行時間 (s) 2 素数 0.01 8 合成数 0.01 3 素数 0.01 ９ 合成数 0.01 4 合成数 0.01 10 合成数 0.01 5 素数 0.01 11 素数 0.01 6 合成数 0.01 12 合成数 0.01 7 素数 0.01 13 素数 0.01 ・実験した範囲では、処理時間も早く利 便性が高いと考えられる。 ・RSA暗号の鍵生成のように素数性の 判定は応用上重要であるので、素数性 を高速に判定するアルゴリズムは計算 理論において魅力的。 ・実用的には、多項式の次数が高すぎ るので、高速に判定が出来ない。 実験結果（三つの判定法の比較） ・Fermatテストの判定でCarmichael数が存在する確率 的素数判定法のため除外。 ・２つの素数判定法の時間の比較 試し割り法とAKS素数判定法の 比較 判定した数 AKS 試し割り 3165473873(素数) 0.01 0.109 316547387353(素数) 0.01 0.484 31654738735379(素数) 0.016 5.413 3165473873537929(素数) 0.031 53.976 316547387353792927 (素数) 0.035 164.753 666666666666666666666 66667(合成数) 0.015 421.219 桁数が増加すると「試し割り法」は、「AKS素 数判定法」と比較すると時間がかかることが 分かった。 計算機実験に より確認できた まとめと今後の課題 実験を通してMaple１４を用いた素数判定法が 成功し、Carmichael数の性質を知ることが出 来た。 今後も様々な素数判定法について研究 し、新たな素数判定を生み出したい。 参考文献 ・素数全書 –計算からのアプローチ 監訳者 和田秀雄 朝倉 書店 （2010） ・素数大百科 編著 Chris K.Caldwell 編訳 SOJIN 共立出版 （2004） 付録① RSA暗号は、公開鍵として二つの素 数が必要となる。実際の処理におい ても数百桁を扱うため、素因数分解 を使って素数であるかを判断するこ とは不可能です。（RSA暗号は、素 因数分解が困難であることを前提に した暗号です。） 付録②(fermatテスト) fermattesut := proc (n) local a, st; st := time(); a := RandomTools[Generate](integer(range = 2 .. n-1)); if igcd(a, n) <> 1 then print*n*`は合成数である。` end if; if modp(a^(n-1), n) <> 1 then print(n*`は合成数である。`) else print(n*`は素数である。`) end if; print(time()-st) end proc
© Copyright 2024 ExpyDoc
