最終更新日:2003.05.31
素因数分解とは、ご存知の通り、自然数Nを素数の積として書き表すことです。これは、極めて単純ながらも決して容易ではなく、興味深い問題です。
例えば、２つの素数33553991,33554473の積を計算しなさいといわれたら、「面倒」とは思うかも知れませんが、その気になれば数分で計算できることでしょう。しかし、逆に1125886485051743が33553991×33554473であることを発見するのは容易ではありません。12を因数分解しようとして2,3と順に小さな素数で割ってみるのとは訳が違います。
これはコンピュータにとっても同様です。そもそもコンピュータは加減算、乗算ほどには除算が得意ではありません。例えばIntel x86系CPUの場合、除算は乗算の7倍〜10倍、加減算の30〜40倍程度の時間がかかります。加えて、自然数Nに対しては(√N)/log(N)個程度の素因数の候補がある（素数定理より）ので、こんなに沢山の候補の中から素因数を探すのは手間が掛かります。
2002年現在、10万円程度で購入可能な一般的なパソコンで計算することを考えてみましょう。10,000桁×10,000桁=20,000桁程度の乗算には1秒も掛かりません。これに対して、100桁=50桁×50桁程度の数を素因数分解するにはどう頑張っても数週間は掛かります。
実は、この非対称性こそが現代の暗号/電子署名を支えています。暗号化には素数同士の乗算を、復号化には合成数の素因数分解を必要とするようなアルゴリズムを作っておけば、元の素因数を知らない限り容易には復号化できません(RSA暗号などがそうです)。現代の計算機暗号においては、合い言葉やアンクルトムではなく、合成数の素因数が暗号鍵であると言えます。
勿論、根気強く素因数分解計算を行えばいつかはこの暗号は解けます。しかしながら、暗号化された情報が意味を失うまでの間復号化できなければそれで十分です。例えば、次年度に発表予定の新製品に関する企画書に対して、暗号鍵を知らない限り解読するのに1000年掛かるような暗号化を施すとすれば、それは十分実用的であると言えます。
ネットワーク時代(w のセキュリティは素因数分解の困難性により支えられています。
この一連の資料「素因数分解」は、筆者の勉強のために素因数分解のアルゴリズム・その理論・及び実装を記すことを目的としています。
言語は主としてRubyを用いています。その他に、整数論の世界で使われているUBASICや、JAVA、C言語による実装も（言語の特性と私の気分に応じて）適宜行います。
なお、理論的な内容については複雑な数式を記す必要からHTMLでは十分ではなく、DVI及びPDFの形式で公開している部分もあります。
ここで主として扱いたいのは計算機の語長に収まらないような大きな整数の素因数分解です。JAVAやRubyやPythonは標準で多倍長整数クラスがついていますし、UBASICもかなり大きな整数を扱えるので特に問題はありません。
しかし、一般の言語では標準ライブラリだけで巨大整数を扱うのは容易ではありません。GMPやMintのようなライブラリの助けが必要となります。
素因数分解のC言語版実装ではGMPを使ってしまえば楽で信頼性も高いでしょうが、ついでなので勉強のためにライブラリを自作しています。なかなか時間がとれずにライブラリが完成していないため、C言語版実装の公開は他の言語に比べて遅れるでしょう。
この資料群の著作権は、このサイトについてにあるとおり、私が有していますので、私的利用の範囲を超えた無断転載・改変等はご遠慮ください。
例外として、http://idm.s9.xrea.com/factorization/impl/以下にある実装のソースコードはGPLに従って公開します。著作権は私にありますが、GPLの規定に従う限りにおいて自由に複製・改変・再頒布することができます。
この資料に於いては、素因数分解の対象となる合成数をNと記し、またp,qは原則として素数を表すものとします。