Msieveは楕円曲線法、複数多項式二次ふるい法、一般数体ふるい法などの効率的なアルゴリズムを用いて、高速に素因数分解が行えるプログラムです。

apt-getの環境におけるインストール方法を解説した記事は沢山ありますが、CentOSやAlmaLinuxなどyumの環境でのインストール方法が調べても出てこなかったのでメモ書き程度に残します。

早速ですがインストール方法です。

まずは、ECMを有効にしてビルドするため、ecm-7.0.5を入れます。

$ wget "https://ftp.iij.ad.jp/pub/linux/gentoo/distfiles/15/ecm-7.0.5.tar.gz"
$ tar xvf ecm-7.0.5.tar.gz
$ cd ecm-7.0.5
$ ./configure
$ make
$ sudo make install

次に、msieveを落としてビルドします。

$ cd ../
$ wget "http://downloads.sourceforge.net/project/msieve/msieve/Msieve%20v1.52/msieve152.tar.gz?r=&ts=1602107977&use_mirror=jaist" -O msieve152.tar.gz
$ tar xvf msieve152.tar.gz
$ cd msieve152
$ make all ECM=1

これで、ECMを有効化してビルドすることができました。 もしビルドが通らない場合、ECMのインストールに失敗している可能性があります。

また、ECMは現在公式サイトから落とせない状態となっているので、必要であれば以下の非公式ミラーから取得してください。

msieve152.tar.gz - End2End.tech

Msieveには、以下のようなコマンドラインオプションがあります。

オプションの数は多いですが、ざっくりと以下の認識で問題ありません。

60桁以下の数

基本的なアルゴリズム(Fermat's method, Pollard Rhoなど)で十分ですので、特に引数の指定は必要ありません。

$ ./msieve -v 1234567890

60桁～100桁程度の数

Quadratic Sieve (QS) アルゴリズムを使用するため、-eを指定します。

$ ./msieve -e -v 1234.....(以下40桁)

100桁以上の数

Number Field Sieve (NFS) アルゴリズムが適しているため、-eを指定し、複数のスレッド(-t)の使用がお勧めです。 また、このサイズの数では多項式選択段階が重要になるため、-nを使うべきではありません。

$ ./msieve -e -v -t スレッド数 1234.....(以下95桁)

Msieveを用いて、巨大な合成数の素因数分解に挑戦してみました。

ここでは、以下の10進法で80桁の合成数を素因数分解してみます。

73460199659581590761841786284855071489788498913754722072104008491726817735612791

CPU: i9 12900Kの環境では、1分36秒で分解することができました。

$ ./msieve -v -e -t 12 73460199659581590761841786284855071489788498913754722072104008491726817735612791

Msieve v. 1.52 (SVN unknown)
Mon Sep  2 20:20:40 2024
random seeds: 879547d7 6e9cb0fc
factoring 73..91 (80 digits)
searching for 15-digit factors
searching for 20-digit factors
commencing quadratic sieve (80-digit input)
using multiplier of 1
using generic 64kb sieve core
sieve interval: 6 blocks of size 65536
processing polynomials in batches of 17
using a sieve bound of 1301081 (49839 primes)
using large prime bound of 130108100 (26 bits)
using trial factoring cutoff of 27 bits
polynomial 'A' values have 10 factors

sieving in progress (press Ctrl-C to pause)
50354 relations (26704 full + 23650 combined from 268071 partial), need 49935
50354 relations (26704 full + 23650 combined from 268071 partial), need 49935
sieving complete, commencing postprocessing
begin with 294775 relations
reduce to 71156 relations in 2 passes
attempting to read 71156 relations
recovered 71156 relations
recovered 55528 polynomials
attempting to build 50354 cycles
found 50354 cycles in 1 passes
distribution of cycle lengths:
   length 1 : 26704
   length 2 : 23650
largest cycle: 2 relations
matrix is 49839 x 50354 (7.4 MB) with weight 1538706 (30.56/col)
sparse part has weight 1538706 (30.56/col)
filtering completed in 4 passes
matrix is 33546 x 33610 (5.4 MB) with weight 1155512 (34.38/col)
sparse part has weight 1155512 (34.38/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 33498 x 33610 (3.7 MB) with weight 861839 (25.64/col)
sparse part has weight 644448 (19.17/col)
using block size 8192 and superblock size 2949120 for processor cache size 30720 kB
commencing Lanczos iteration
memory use: 2.2 MB
lanczos halted after 531 iterations (dim = 33493)
recovered 14 nontrivial dependencies
prp40 factor: 7805805930349305111814906387390356128801
prp40 factor: 9410969259940887499391300875191187171991
elapsed time 00:01:36

無事に40桁の素数2つの積に分解することができました。

7805805930349305111814906387390356128801 ×
9410969259940887499391300875191187171991