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

数十桁～百数十桁の大きな整数を素因数分解したくなったときに使える素因数分解ソフト Msieve の使い方についてのメモです。

Windows 環境での使い方について記載しています。

※インストール不要で、PC・スマホ関係なくブラウザ上で実行できるWeb上の高速な素因数分解ツールをお探しの場合はこちらをご覧ください。

素因数分解ツール(Web)

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

[usemath] 数十桁～百数十桁の大きな整数を素因数分解したくなったときに使えるネット上の高速な素因数分解ツールを紹介します。 (Web上のほとんどのツールは厳しい桁数制限があるので、入力上の桁数制限が基本的に無いツールを載[…]

↑このWebツールだと速度が不十分 or 他の素因数分解アルゴリズムも用いたい などの希望がある場合、Msieve が Windows 環境で手軽に動かせて良さそうです。

Msieve のダウンロード・導入

ダウンロード

素因数分解ソフト Msieve は以下のリンク先サイトからダウンロードできます。
(作者の Jason Papadopoulos さんの公式サイト(魚拓) によると、以下の SourceForge が公式のホスト先みたいです)

 Msieve のダウンロード先 (SourceForge)

Download ボタンを押すと、Windows 環境なら Windows用ソフト(バイナリ)がダウンロードされます。

※私がダウンロードしたバージョンは 2023/11/01 に更新された v1.53 です。ファイル名は「msieve153_win64.zip」

ソフトの導入

ダウンロードしたzipファイルを解凍し、適当なフォルダに展開するだけです。

特にインストール作業は不要ですが、ここから先はコマンド操作が必要になります。

(※GUIを持たないソフトなので、解凍して出てきたソフト本体 msieve153.exe をダブルクリックしてもソフトは実行できません)

Msieve の使い方 (整数を楕円曲線法で素因数分解する)

まず、ソフトがあるディレクトリでコマンドプロンプトを立ち上げます。

ソフト本体があるフォルダにて、画像赤枠のアドレスバーに「cmd」と入力してEnterすれば、この場でコマンドプロンプトを立ち上げられます。

次に、以下の形式でコマンドを入力します。

例えばソフトのファイル名が msieve153.exe で、素因数分解したい数が 1234567890123456789 なら

と入力します。

入力したら、Enter キーを押すと素因数分解が始まります。

このくらいの桁数なら一瞬で処理が完了し、次のように結果が表示されます。

下の方に「p○ factor: 数」という形式で列挙されているのが素因数です。

上記画像の例なら、

$$ 1234567890123456789 = 3 \times 3 \times 101 \times 3541 \times 3607 \times 3803 \times 27961 $$

と素因数分解できたことが分かります。

コマンドについて

コマンドには以下の2つのオプションを指定してます。

• -e：素因数分解に楕円曲線法(ECM)を用いる
• -v：結果(ログ)をプロンプト画面に表示する

他にも色々なオプション引数を指定可能です。

-h を指定するとヘルプが表示されるのでそこから設定可能なオプションを確認できます。

※オプションを日本語で説明してくださっているページがありました。

速度チェック

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

141桁の整数です。2×(19桁の素数)×(123桁の素数) の形です。

こちらのページで紹介している高速素因数分解ツール(Web版)では、私の環境で 10.8 秒かかっていました。

さて、Msieve では何秒で素因数分解できるでしょうか…？
(※楕円曲線法 (ECM) で分解します)

実行コマンド：

結果：

なんと 1 秒で

2 × 1482692616151688761 × 153431857662937227474501042211122068306895763518856237258299616079759236835346239364324513867253092619961581324439880635107

と素因数分解できました！

もうちょっと時間がかかる例で試したいので、以下の82桁の合成数を用意します。

$$ 10^{81}+10^{41}+10^{21}+1 $$

実行コマンド：

↑この例のように、累乗 ^ や加減乗除の記号を使うこともできます。

結果：

39 秒で

7327009 × 92230491125613010818161 × 1479785453222243224132798508068574560810272067912049

と素因数分解できました。

オンライン素因数分解ツールでは 78.5 秒 かかったので、この例では半分の所要時間で実行できています！

Tips

計算の中断・分解の経過確認

Ctrl + C キーで計算を中断できます。

中断した場合も、素因数分解の途中経過が確認できます。

上記画像の例では、3つの素数 p1, p24, p32 と 1つの合成数 c104 の積にまでは分解できています。

※ p や c の後の数字は、因数の桁数を表しています。

GNFS 法で素因数分解

-e オプションに加えて -n オプションを使うと、80桁以上の整数であれば GNFS 法 (一般数体篩法) で素因数分解してくれるみたいです。

ソフトはパブリックドメイン

大変ありがたいことに、Msieve は著作権を放棄して Public Domain で公開されています。(Readme参照)

このような素晴らしいソフトを誰もが自由に利用できる形で公開してくださった作者の Jason Papadopoulos さんに大感謝です…!!

その他、素数情報

見て楽しい素数

回文素数以上に見た目が対称的で楽しい素数をピックアップしました。

$$ 7777777733333773777377373737737773773333377777777 $$

↓以下のページでたくさんの例を楽しめます。

関連記事

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

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

素数記事一覧

それ以外の素数系記事はこちら。(現在拡充途中)

 素数記事一覧ページ

素因数分解用ツール・ソフトについての情報まとめ

以下のフォーラムの情報が参考になりました。

 Links to factoring programs