素因数分解計算機

素因数分解計算機について

このツールは2以上 2¹²⁸ − 1（約3.4 × 10³⁸、39桁）以下の整数を素因数分解します。計算は3段階です。まず2²⁰（約105万）までの小さな素数で試し割りをして小さな因数を取り除き、残りが素数かどうかをミラー–ラビン判定で確かめ、合成数ならブレント改良版のポラード・ロー法で因数を1つ見つけて再帰的に分けていきます。

39桁まで扱えるのは、128ビット整数の演算を WebAssembly で直接実装しているからです。JavaScript の通常の数値は 2⁵³（約9 × 10¹⁵）を超えると整数を正確に保持できません。かかる時間は数の大きさよりも「2番目に大きい素因数の大きさ」で決まるため、同じ39桁でも一瞬で終わることも数時間かかることもあります。

試し割りが大きな数で止まる理由

一番素朴な方法は2、3、5、7…と順に割ることです。合成数 n には必ず √n 以下の因数があるので √n まで割れば十分ですが、その √n が大きすぎます。20桁の数なら √n は10桁で、最悪100億回近い割り算が必要です。39桁なら10¹⁹回を超えます。

そこでこのツールは試し割りを2²⁰までに限っています。多くの整数は小さな因数をいくつも持つのでこの段階でほぼ分解され、最後まで残るのは大きな素数か、大きな素数2〜3個の積だけです。

ポラード・ロー法：約 √p 回で因数 p を見つける

ポラードが1975年に発表したこの方法は、x → x² + c (mod n) のような擬似乱数列を作り、それを未知の素因数 p で割った余りがいつか繰り返すことを利用します。誕生日問題と同じ理屈で、繰り返しはおよそ √p 回以内に起こり、そのとき2つの値の差と n の最大公約数を取ると p が現れます。1980年にブレントが循環検出を改良し、同じ年にこの方法でフェルマー数 F₈（78桁）が分解されました。

時間を決めるのは n ではなく最小の素因数 p の大きさです。最悪は2つの素因数が同じくらいの大きさの半素数（p ≈ √n）で、反復回数は約 n^(1/4) になります。計算前に表示される予想時間もこの最悪ケースを前提にしているので、小さな因数が1つでもあれば実際はずっと早く終わります。

実測すると差ははっきりしています。デスクトップで10桁の素数2つの積（20桁）は約0.05秒、13桁の素数2つの積（25桁）は約1.5秒でした。n が16ビット（約5桁）増えるごとに時間は16倍になるので、20桁の素数2つを掛けた39桁の半素数は数時間かかりえます。一方、2¹²⁷ − 1 のような39桁の素数は判定だけなので約0.01秒です。

素数判定は分解よりずっと易しい

素数かどうかを確かめることと因数を見つけることは、難しさがまったく違います。ミラー–ラビン判定は数回のべき乗剰余計算だけで合成数を見抜きます。このツールは2⁶⁴未満では2から37までの素数を底に使って決定的に判定し、それ以上では61までの18個の底による確率的判定を行います。この範囲で18個すべてを通過する合成数は知られていません。

フェルマー判定だけだと 561 = 3 × 11 × 17 のようなカーマイケル数にだまされます。ミラー–ラビンはだまされず、561を入れるとすぐ 3 × 11 × 17 が出ます。

RSA暗号が素因数分解の難しさに頼る仕組み

RSA の公開鍵は、大きな素数 p、q の積 n を公開します。暗号化は n だけでできますが、復号鍵を作るには p と q が必要です。掛けるのは一瞬で、戻すのは難しいという非対称性が安全性の根拠です。1977年にマーティン・ガードナーのコラムで出題された129桁の RSA-129 は、世界中のボランティアのコンピュータを動員して1994年にようやく分解されました。

現在使われる RSA 鍵は一般に2048ビット（約617桁）で、このツールの上限128ビットの16倍の長さです。その規模には数体ふるい法のような高度なアルゴリズムが使われ、それでも公開されている分解記録は2048ビットに遠く及びません。

例

使い方

1. 2以上の整数を入力します。カンマや空白は無視されます。
2. 大きな数では予想時間が先に表示され、計算中も中断できます。
3. 同じ素因数は指数でまとめて表示され、履歴を押すと等式がコピーされます。

よくある質問