nextProbablePrime() について
?
2 likes?3,608 views
第十五回 #渋谷java にてLT発表を行いました。 java.math.BigInteger#nextProbablePrime() が、どこまで使えるかを検証してみました。 http://shibuya-java.connpass.com/event/29113/
nextProbablePrime() について
- 1. nextProbablePrime() について 福原和朗 第十五回 #渋谷java 2016-04-23 1
- 2. 自己紹介 ? 福原和朗 @kazurof ? twitter, Qiita, Facebook やってます。 ? 所属 ? GMOリサーチ ? アンケートシステムの開発保守 2
- 3. 本日のお題 ? nextProbablePrime() ? java.math.BigInteger ? 巨大な整数 ? 「おそらく素数」 ? どこまで使えるのか？ 3
- 4. 動かしてみた ? 素数リストを用意して突き合わせる。 ? 10億までの素数 ? https://primes.utm.edu/lists/small/millions ? 100億までの素数 ? http://www.saoyagi2.net/integer/primelist.html ? リストは正しいものとみなす。 4
- 5. 100億まで正解でした ? ファイルサイズ ? 4.6 Gbyte ? 所要時間 ? 17 hrs 44 mins 31.635 secs ? これ以上試すのは無理。 5
- 6. ソースを読んでみました ? nextProbablePrime()の処理概要 ? おそらく素数が見つかるまでループ 1. 次の候補を決める。 2. 候補がおそらく素数か合成数か判定する。 6
- 7. 大きさで処理を分ける ? 基準はビット長 ? 予備知識 ? intの最大値 2147483647 ? 31ビット ? 100億 ≦ 171億 ≒ 171,7986,9184 = 234 ? 34ビット ? long の最大値 9223372036854775807 ? 63ビット 7
- 8. 分ける基準 1. ビット長が95未満 ? 19807040628566084398385987584 2. 95 ~ 5,0000,0000 ビットまで ? 5億ビット。10進では書けません。 3. それ以上 ? サポートしない（即例外が上がる） ? 他のところでオーバーフローするため。 8
- 9. 95未満の場合 1. 次の候補の決め方。 ? 41までの素数で試し割り。割れた数字は スキップ。 ? 41はチューニングの結果とのこと。 2. おそらく素数か合成数かの判定 ? ミラー–ラビン素数判定法 9
- 10. ミラー–ラビン素数判定法 ? 素数かどうか判定するアルゴリズム ? 実際に割らないから高速 ? 大学の教科書で紹介されるレベル ? フェルマーの小定理を元にしている。 ? これだけだと抜けがあるので色々工夫さ れている。 10
- 11. ミラーラビン法超概要 ? フェルマーの小定理 ? p を素数、a を p で割れない整数。 ? どんな a でも、a(p-1) を pで割った余りは 1 になる。 ? 例 ? p = 5 ,a = 8 ? a(p-1) = 84 = 82 * 82 = 642= .....6 ? 余り 1 11
- 12. ミラーラビン法 (1) ? 小定理の対偶 ? 「余りが1でないaがあるなら素数でない」 ? a(p-1) を pで割った余りを調べればよい ? 割ってまわるよりは遥かに簡単 ? a を１個適当に決めて計算すればOK？ 12
- 13. ミラーラビン法 (2) ? 誤判定する場合がある。 ? p = 341, a = 2 の場合 ? 2340 を 341で割った余り → 1 ? 341 = 11 * 14 素数ではない。 ? こんな例が比率低いながら存在する。 ? a の選び方が悪い？ 13
- 14. ミラーラビン法 (3) ? 改良 ? a を一つに固定せず、ランダムにいくつか 選んで試す。 ? １個だと不安だが、幾つかやってOKなら多分OK ? 全部は無理。そんな余裕があったら試し割り。 ? 「おそらく素数」の根拠 ? もう1つ工夫をする。 ? aを累乗する際に、非自明な１の平方根があるか チェック 14
- 15. 95 ~ 5,0000,0000 まで 1. 次の候補の決め方。 ? エラトステネスの篩(ふるい)で決定。 2. おそらく素数かの判定 ? ミラー–ラビン素数判定法 ? リュカ–レーマー?テスト 15
- 16. エラトステネスの篩 ? 数字を表に書いて素数以外を消していく。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 16
- 17. 実際の処理 ? 19200までの篩を用意する。 ? 候補をのせたい範囲の篩から、合成数を消す。 ? できた篩から次の候補を取り出す 19200までのふるい 候補をのせたい範囲のふるい 17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 30000 30001 30002 … … … … … … … … …
- 18. まとめ:どこまで使えるか？ ? 「おそらく」とは理論上確率ゼロでは ないという意味。 ? 現実にはほぼ間違えない。 ? 巨大な数でも間違えやすくはならない。 ? 処理に時間がかかる ? (244497 – 1)*(286243 – 1) を素数判定するのに およそ100分かかりました。 18
- 19. 背景となる用途 ? RSA暗号 ? 巨大な素数が欲しい。 ? 鍵ペアの元にする。 ? 絶対に素数である保証はいらない。 ? 極小さい確率であることが保証されればOK ? そこそこ巨大(2048ビット)なものが判定 できればOK ? 試したら、300ミリ秒でできました。 19
- 21. ご清聴ありがとうございました nextProbablePrime() について 福原和朗 @kazurof 第十五回 #渋谷java 2016-04-23 21