インストール方法 (Mac)
homebrew でインストールできないため、ソースからビルド&インストールを行います。
事前準備
ecm.h と gmp.h が必要なので、インストールします。
ecm のインストール
brew でインストールできるバージョンは古いので、ソースからインストールします。
記事作成時の最新バージョンは 7.0.4 です。(公式サイト)
$ curl https://gforge.inria.fr/frs/download.php/zip/9946/ecm-7.0.4.zip -O
$ unzip ecm-7.0.4.zip
$ tar xvf ecm-7.0.4.tar.gz
$ cd ecm-7.0.4/
$ ./configure
$ make
$ make check
$ make install
gmp のインストール
Install gmp on Mac OSX を参考に brew でインストールを行います。
$ ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)" < /dev/null 2> /dev/null
$ brew install gmp
msieve のダウンロード
$ curl -L https://sourceforge.net/projects/msieve/files/msieve/Msieve%20v1.53/msieve153_src.tar.gz/download -o msieve153.tar.gz
$ tar xvf msieve153.tar.gz
$ cd msieve-1.53/
コンパイル
その後、パスが通っている適当な場所に移動すれば使えるようになります。
$ mv msieve ~/.local/bin/
インストール方法 (Ubuntu 18.04)
依存関係のインストール
$ sudo apt install build-essential libgmp3-dev zlib1g-dev libecm-dev
msieve のダウンロード
$ curl -L https://sourceforge.net/projects/msieve/files/msieve/Msieve%20v1.53/msieve153_src.tar.gz/download -o msieve153.tar.gz
$ tar xvf msieve153.tar.gz
$ cd msieve-1.53/
コンパイル & インストール
$ make all ECM=1
$ sudo mv msieve /usr/local/bin/
使い方
-v オプションで途中経過や、実行にかかった時間がわかるので、つけておくと便利かも。
$ msieve -q -v <number>
# 楕円曲線法
$ msieve -q -v -e <number>
具体例 (ECM)
ECM を使わない場合は -e をオプションから外すだけで良いです。
$ msieve -q -v -e 97139961312384239075080721131188244842051515305572003521287545456189235939577
Msieve v. 1.53 (SVN Unversioned directory)
Fri Apr 19 12:18:15 2019
random seeds: 34182d8c daa410fb
factoring 97139961312384239075080721131188244842051515305572003521287545456189235939577 (77 digits)
searching for 15-digit factors
searching for 20-digit factors
commencing quadratic sieve (77-digit input)
using multiplier of 17
using generic 32kb sieve core
sieve interval: 12 blocks of size 32768
processing polynomials in batches of 17
using a sieve bound of 922619 (36471 primes)
using large prime bound of 92261900 (26 bits)
using trial factoring cutoff of 26 bits
polynomial 'A' values have 10 factors
sieving in progress (press Ctrl-C to pause)
36805 relations (19586 full + 17219 combined from 191943 partial), need 36567
36805 relations (19586 full + 17219 combined from 191943 partial), need 36567
sieving complete, commencing postprocessing
begin with 211529 relations
reduce to 51920 relations in 2 passes
attempting to read 51920 relations
recovered 51920 relations
recovered 40614 polynomials
attempting to build 36805 cycles
found 36805 cycles in 1 passes
distribution of cycle lengths:
length 1 : 19586
length 2 : 17219
largest cycle: 2 relations
matrix is 36471 x 36805 (5.3 MB) with weight 1103069 (29.97/col)
sparse part has weight 1103069 (29.97/col)
filtering completed in 3 passes
matrix is 25427 x 25490 (4.0 MB) with weight 848421 (33.28/col)
sparse part has weight 848421 (33.28/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 25379 x 25490 (2.6 MB) with weight 609482 (23.91/col)
sparse part has weight 417167 (16.37/col)
commencing Lanczos iteration
memory use: 2.6 MB
lanczos halted after 403 iterations (dim = 25376)
recovered 16 nontrivial dependencies
p39 factor: 299681192390656691733849646142066664329
p39 factor: 324144336644773773047359441106332937713
elapsed time 00:02:18
2分ちょっとで解析完了してますね。2回目以降はキャッシュされるのですぐ結果が返ってきます。
参考リソース