素数判定の効率性について 東邦大学理学部情報科学科卒業研究発表会 指導教員 白柳 潔 提出者 後藤 雄大
さまざまな素数判定法 決定的な素数判定法 ・試し割り法 ・ 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 判定結果
AKS 素数判定法（決定的素数判定 法） 与えられた自然数が素数であるかどうかを決定的多項式時間で判定できる、世界初の アルゴリズム Fermat の小定理を改良 数判定結果 実行時間 (s) 数判定結果 実行時間 (s) 2 素数 合成数 素数 0.01 ９合成数 合成数 合成数 素数 素数 合成数 合成数 素数 素数 0.01 判定結果 ・実験した範囲では、処理時間も早 く利便性が高いと考えられる。 ・ RSA 暗号の鍵生成のように素数性 の判定は応用上重要であるので、素 数性を高速に判定するアルゴリズム は計算理論において魅力的。 ・実用的には、多項式の次数が高す ぎるので、高速に判定が出来ない。
実験結果（三つの判定法の比較） ・ Fermat テストの判定で Carmichael 数が存在する 確率的素数判定法のため除外。 ・２つの素数判定法の時間の比較 判定した数 AKS 試し割り ( 素数 ) ( 素数 ) ( 素数 ) ( 素数 ) ( 素数 ) ( 合成数 ) 桁数が増加すると「試し割り法」は、 「 AKS 素数判定法」と比較すると時間が かかることが分かった。 試し割り法と 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