msieve
素因数分解を高速に行うためのツール

インストール方法 (Mac)

homebrew でインストールできないため、ソースからビルド&インストールを行います。

事前準備

ecm.hgmp.h が必要なので、インストールします。

ecm のインストール

brew でインストールできるバージョンは古いので、ソースからインストールします。
記事作成時の最新バージョンは 7.0.4 です。(公式サイト)
1
$ curl https://gforge.inria.fr/frs/download.php/zip/9946/ecm-7.0.4.zip -O
2
$ unzip ecm-7.0.4.zip
3
$ tar xvf ecm-7.0.4.tar.gz
4
$ cd ecm-7.0.4/
5
6
$ ./configure
7
$ make
8
$ make check
9
$ make install
Copied!

gmp のインストール

Install gmp on Mac OSX を参考に brew でインストールを行います。
1
$ ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)" < /dev/null 2> /dev/null
2
$ brew install gmp
Copied!

msieve のダウンロード

1
$ curl -L https://sourceforge.net/projects/msieve/files/msieve/Msieve%20v1.53/msieve153_src.tar.gz/download -o msieve153.tar.gz
2
$ tar xvf msieve153.tar.gz
3
$ cd msieve-1.53/
Copied!

コンパイル

1
$ make all ECM=1
Copied!
その後、パスが通っている適当な場所に移動すれば使えるようになります。
1
$ mv msieve ~/.local/bin/
Copied!

インストール方法 (Ubuntu 18.04)

依存関係のインストール

1
$ sudo apt install build-essential libgmp3-dev zlib1g-dev libecm-dev
Copied!

msieve のダウンロード

1
$ curl -L https://sourceforge.net/projects/msieve/files/msieve/Msieve%20v1.53/msieve153_src.tar.gz/download -o msieve153.tar.gz
2
$ tar xvf msieve153.tar.gz
3
$ cd msieve-1.53/
Copied!

コンパイル & インストール

1
$ make all ECM=1
2
$ sudo mv msieve /usr/local/bin/
Copied!

使い方

-v オプションで途中経過や、実行にかかった時間がわかるので、つけておくと便利かも。
1
$ msieve -q -v <number>
2
3
# 楕円曲線法
4
$ msieve -q -v -e <number>
Copied!

具体例 (ECM)

ECM を使わない場合は -e をオプションから外すだけで良いです。
1
$ msieve -q -v -e 97139961312384239075080721131188244842051515305572003521287545456189235939577
2
3
4
Msieve v. 1.53 (SVN Unversioned directory)
5
Fri Apr 19 12:18:15 2019
6
random seeds: 34182d8c daa410fb
7
factoring 97139961312384239075080721131188244842051515305572003521287545456189235939577 (77 digits)
8
searching for 15-digit factors
9
searching for 20-digit factors
10
commencing quadratic sieve (77-digit input)
11
using multiplier of 17
12
using generic 32kb sieve core
13
sieve interval: 12 blocks of size 32768
14
processing polynomials in batches of 17
15
using a sieve bound of 922619 (36471 primes)
16
using large prime bound of 92261900 (26 bits)
17
using trial factoring cutoff of 26 bits
18
polynomial 'A' values have 10 factors
19
20
sieving in progress (press Ctrl-C to pause)
21
36805 relations (19586 full + 17219 combined from 191943 partial), need 36567
22
36805 relations (19586 full + 17219 combined from 191943 partial), need 36567
23
sieving complete, commencing postprocessing
24
begin with 211529 relations
25
reduce to 51920 relations in 2 passes
26
attempting to read 51920 relations
27
recovered 51920 relations
28
recovered 40614 polynomials
29
attempting to build 36805 cycles
30
found 36805 cycles in 1 passes
31
distribution of cycle lengths:
32
length 1 : 19586
33
length 2 : 17219
34
largest cycle: 2 relations
35
matrix is 36471 x 36805 (5.3 MB) with weight 1103069 (29.97/col)
36
sparse part has weight 1103069 (29.97/col)
37
filtering completed in 3 passes
38
matrix is 25427 x 25490 (4.0 MB) with weight 848421 (33.28/col)
39
sparse part has weight 848421 (33.28/col)
40
saving the first 48 matrix rows for later
41
matrix includes 64 packed rows
42
matrix is 25379 x 25490 (2.6 MB) with weight 609482 (23.91/col)
43
sparse part has weight 417167 (16.37/col)
44
commencing Lanczos iteration
45
memory use: 2.6 MB
46
lanczos halted after 403 iterations (dim = 25376)
47
recovered 16 nontrivial dependencies
48
p39 factor: 299681192390656691733849646142066664329
49
p39 factor: 324144336644773773047359441106332937713
50
elapsed time 00:02:18
Copied!
2分ちょっとで解析完了してますね。2回目以降はキャッシュされるのですぐ結果が返ってきます。

参考リソース

Last modified 2yr ago