- はじめに
- 素数は簡単に説明できるようでいて、非常に大きな複雑さを内包している
- 数学的概念、興味深い可視化、暗号学など幅広い分野で利用される
- コーディングを通じて素数生成に挑戦することにした
- 課題
- RSAアルゴリズムで使える素数を生成する
- 現在RSA鍵として適切な長さは2048ビットなので、1024ビットサイズの素数2つが必要
- 制約条件:
- 最初から自分でコードを書く（外部依存なし）
- ノートPCのAMD Ryzen 7 CPUと16GB RAMのみを使用
- 「合理的」な時間内で素数を生成する
- Rustを選択
- 16ビット素数生成
- 擬似乱数生成器
/dev/urandom を使って乱数を生成
- 簡潔な素数判定法である試し割り（Trial Division）を使用
- 平均40ms以内に16ビット素数を生成可能
- 64ビット素数生成
- 最適化された試し割りアルゴリズムを実装
6k±1 の形の数だけを確認- 小さい素数のリストを事前生成して、簡単に割り切れる数を先に除外
- 最適化後、約6秒かかった
- より大きな数には決定的アルゴリズムでは限界がある
- 確率的素数判定法
- フェルマーの小定理（Fermat's Little Theorem）を活用
- 合成数も条件を満たす可能性がある問題点がある（Pseudoprime）
- ミラー・ラビン素数判定法（Miller-Rabin Primality Test）
- フェルマー判定法を改良した確率的判定法
- 合成数がある底（base）に対して常にPseudoprimeになるケースはない
- 誤判定確率が非常に低く、実用的に使用可能
- 128ビット素数生成
- ミラー・ラビン判定法で高速に生成可能（平均0.03秒）
u128型の制約により1024ビットまで拡張するのが難しくなった
- 1024ビット向けBigInt実装
- 試行を重ねながら段階的に改善
- 試行1: 数値の各桁を配列に保存
- 試行2: 数値を2進数形式で保存
- 試行3: 数値をバイト単位のチャンクとして保存
- 試行4: 数値をu64単位のチャンクとして保存
- 試行5: 四則演算アルゴリズムを最適化
- ミラー・ラビン判定法と全体ロジックの最適化
- マルチスレッディングを活用した並列処理
- 最終結果
- 約40ms以内に1024ビット素数の生成が可能（8ms ~ 800ms）
- 並列処理を使って平均0.04秒かかった
GN⁺の見解
- 試行と失敗を繰り返しながら段階的に改善していく過程が印象的だった
- 単純な実装から始め、各段階で新しいアイデアを適用し最適化を実施
- 失敗を経験しても諦めず、問題の原因を特定して解決策を探る
- 著者の数学的な基礎知識が不足しているにもかかわらず、関連資料を調べて理解しようとした点が際立っていた
- フェルマーの小定理、ミラー・ラビン判定法など必要な数学的概念を学習
- 難しい内容を実装可能なレベルまで理解し、適用
- 固定長整数型の限界を克服するために自作でBigIntを実装した点が印象的だった
- 既存ライブラリを単に使うのではなく、内部動作原理を理解して最適化を実施
- 様々なアイデアを試しながら段階的に改善していく姿勢が印象的だった
- マルチスレッディングを活用した並列処理で性能を大きく向上させた点が興味深かった
- 独立した計算を行う問題の特性を適切に把握して活用
- 単に高速化を追求するだけでなく、問題特性を考慮した効果的なアプローチ
- 暗号学的に安全な水準ではないが、学習と探求の過程として大きな意義を持つプロジェクトだと考えられる
- 実用的活用よりも、著者の好奇心と挑戦心が際立つ課題
- 過程で得た洞察と経験が、著者の今後の成長に大きく役立つことが期待される
1件のコメント
Hacker Newsのコメント
関連して、一部の暗号通貨はプルーフ・オブ・ワーク関数の一部として大きな素数探索に関連する処理を使っている。約8年前には、かなり高速な素数判定実装でかなりのお金を稼げた。筆者はしばらくの間、Riecoin向けの採掘ソフトウェアの作成者かつ運営者だった。
この投稿では、速い素数判定のための最適化として最高のMontgomery乗算を省略している。これは速い実用的なモジュラ指数演算の実装の基礎となる。
Niall Emmartが公開したCGBNは、実に非常に高速なGPU bigintライブラリである。私が知る限り、いまだに最速のbatch modexp実装だ。
Pythonには
pow(x, y, m) → x^y % mを計算するかなり良いmodexpが組み込まれている。これを使えば、FermatやMiller-Rabinの素数判定を簡単に実装できる。最初は確率的な素数判定の概念が気味悪く、巨大数を扱える決定論的アルゴリズムを探していたが、APR-CLとECPPは数学的にあまりにも複雑で理解が難しかった。RSAを含め、ほとんどすべての場面で確率的アルゴリズムが使われていると気づいた。
特定の最大数の範囲に対してMiller-Rabinを決定論的にするのは明白だ。与えられた範囲で疑似素数をすべて排除することが証明された基底を選べばよい。
1行のインラインアセンブリで巨大数の乗算を簡単に実装できる。C言語に拡張乗算の概念を追加すればよい。ハードウェアサポートはどこにでもある。
Fermatテストで十分だったのは、数が実際に素数でないとアルゴリズムが機能しないからだ。だが、暗号化／復号化のメッセージを正常に処理できる非素数のP/Q値が存在しないことを証明できるかどうかは分からない。
このプロジェクトにはどれくらい時間がかかったのか気になる。著者はKaratsuba、Toom-Cook、複素FFT、NTT、Schönhage–Strassenを実装していた。Silvermanの『A Friendly Introduction to Number Theory』を推奨している。
大きな数を乗算するために独自コードを書いたとき、数学論文の高レベルな説明を実際の演算に変換することがどれほど難しいか身にしみて理解できる。基数に関する説明には少し問題がある。
新しい数を生成する代わりに2を加える最後の最適化は、セキュリティを多少損なう。素数は一様には分布していないため、大きな素数間隔のすぐ次の素数へと偏る。
Fermatの小定理の説明に少し誤りがある。
a^(p-1)がpで割り切れると言うが、a^(p-1) - 1がpで割り切れるべきである。モジュラー算術の用語では、適切に説明されている。