非常に高速な素因数分解ツール (オンライン)

数十桁～百数十桁の大きな整数を素因数分解したくなったときに使えるネット上の高速な素因数分解ツールを紹介します。

(Web上のほとんどのツールは厳しい桁数制限があるので、入力上の桁数制限が基本的に無いツールを載せました)

高速な素因数分解ツール (オンライン)

 Integer factorization calculator

↑こちらのリンクから移動できます。

使い方 (簡易版)

1. 入力ボックスに素因数分解したい整数を入力する
2. Factor (素因数分解) ボタンを押す
3. 下に素因数分解結果が表示される

入力した数が素数だった場合

「入力した数 is prime」と表示されます。

(例) 以下の121桁の、各桁が「7」と「3」だけからなる回文素数を入力

↓

百桁を超えるなど桁数がかなり大きい場合でも、素数ならほとんど一瞬で判定が終わります。

ちなみに、上記素数を11桁ごとに区切って正方形に並べると、綺麗な対象配置になります！

正方形に並べると見た目が綺麗な対象配置になる回文素数を以下のページにまとめています。よろしければ一緒にお楽しみください。

見て楽しい素数たち

【見て驚く素数集】正方形に並べて対称になる綺麗な素数編

[usemath] [sumaho] 「見て楽しい」観賞用の素数ギャラリー。 今回は、各桁の数字を正方形になるように並べると超綺麗に見えるような素数を集めました。 全て回文素数ですが、ただの回文素数よりも(見た目の)対称[…]

便利な使い方

素数判定のみ行う

素因数分解せずに素数判定のみ行いたい場合、Factor ボタンの隣にある Prime ボタンを押せばOKです。

素因数分解よりもずっと高速に処理が終わるので、桁数が大きい整数が素数か否か単に確認するだけなら素数判定だけ先にするのがおすすめです。

複数個の整数を一括で素因数分解

入力ボックスに複数の数を改行区切りで入力すれば、まとめて素因数分解できます。

入力ボックス内に計算式を入れる

ボックス内には数値だけでなく + - * / ( ) などの計算記号も入力可能で、計算式を入れるとそれを計算して得られた整数を素因数分解してくれます。

計算式に使える記号は Functions (関数) メニューのボタンから確認可能です。

Category リストから、カテゴリー別に関数や記号を選択可能です。

それぞれの関数の意味は、Help ボタン を押して表示される説明の Expressions の項で確認できます。

速度チェック

この手の素因数分解ツールの実行速度を簡易的に確認するために普段使っているベンチマーク用合成数(?)を使って、どのくらいの速さで素因数分解ができるか確認してみます。

141桁の整数です。2×(19桁の素数)×(123桁の素数) の形で、すぐ 2 で割れるので素因数分解の途中経過の表示有無が確認できます。

素因数分解に時間がかかる場合、途中経過がリアルタイムで青字で表示されます。
(偶数なので「2×」はすぐ表示されました。)

私の環境では、10.8 秒 で素因数分解が完了しました。

※計算にかかった時間はページの下の方に「Time elapsed: ○○」と表示されています。

計算にかかる時間について

オンラインツールと紹介しましたが、素因数分解の計算が実際に行われているのはWebサイトのサーバー側ではなくサイトに接続している端末側です。

Webブラウザ内で計算処理が実行されます。

計算にかかる時間はお使いの端末のスペックなどの環境に依存します。

(一度スマホで同じ整数を素因数分解したら、約30秒かかりました)

注意

現実的な時間で素因数分解できるかどうかは、桁数だけでなく素因数の中身にもよって大きく変わります。

今回の141桁の合成数は確認するのにちょうどよい時間で素因数分解できる都合の良い整数をピックアップしたものです。

これより桁数が少ない100桁未満の合成数でも素因数分解に数千倍以上時間がかかるケースがあります。

例えば以下の99桁の合成数は2つの50桁の素数の積ですが、私の環境では500分経過しても素因数分解できませんでした。

数十桁の大きな素因数が2つ以上含まれていると、時間がかかります。

使用されているアルゴリズム

素因数分解には 楕円曲線法(ECM) が用いられています。

高速に実行できるよう色々と最適化を行っているみたいです。

アルゴリズムについての簡単な説明は Help の Factoring using the Elliptic Curve Method (ECM) の項にて確認できます。

また、ソースコードはこちらの GitHub ページにて閲覧できます。

もっと高速に素因数分解したい場合は

PC用ソフトでは、このWebツールよりも高速に素因数分解できるものがあります。

例えば素因数分解に今回 10.8 秒かかっていた整数を、1 秒で素因数分解できました。

こちらのページでそのような素因数分解ソフトの一つ Msieve の導入・使用方法について記載しているのでご参照ください。

超高速素因数分解ソフト

超高速な素因数分解ソフト Msieve の使い方

[usemath] 数十桁～百数十桁の大きな整数を素因数分解したくなったときに使える素因数分解ソフト Msieve の使い方についてのメモです。 Windows 環境での使い方について記載しています。 ※インストール不要で[…]

その他、素数情報

素数記事一覧 (現在拡充途中)

 素数記事一覧ページ