GMP (The GNU Multiple Precision Arithmetic Library)

私の環境にはすでに入っていた

brew install gmp

GMP-ECM (Elliptic Curve Method)

参考にした: https://stdkmd.net/nrr/ecm_ja.htm

GMP-ECM をダウンロードしてきて展開

# configure --enable-shared # うまくいかないので諦めた (後述)
./configure
make tune # かなり時間がかかるのでスキップも可
make
make check
make install

試してみる。200ビットくらいなら1分かからないで求まる。
(OpenSSLで素数生成している)
パラメータ (B1 パラメータというらしい) は候補が決まっているらしいので上記サイトを参考に与える

echo "$(openssl prime -bits 100 -generate)*$(openssl prime -bits 100 -generate)" | bc | ecm -c 1290 250000
...
********** Factor found in step 2: 1263560899608128279579214206459
Found prime factor of 31 digits: 1263560899608128279579214206459
Prime cofactor 1015132868242207190409188028479 has 31 digits

桁数が大きくなると SIQS (自己初期化2次ふるい法) や NFS (数体ふるい法) でやるほうがいいらしい

Msieve

とっても参考にした: http://inaz2.hatenablog.com/entry/2016/01/09/032521

ダウンロードしてくる

$ make
to build:
make all
add 'WIN=1 if building on windows
add 'WIN64=1 if building on 64-bit windows
add 'ECM=1' if GMP-ECM is available (enables ECM)
add 'CUDA=1' for Nvidia graphics card support
add 'MPI=1' for parallel processing using MPI
add 'BOINC=1' to add BOINC wrapper
add 'NO_ZLIB=1' if you don't have zlib

さっき GMP-ECM を入れたのでビルドに使えるはず

$ ECM=1 make all

ビルドできた気がする。試してみる。
(tee は生成した数をファイルに保存したいので使っている。bc は出力を勝手に改行するので抑制している)

MPQS (デフォルト: 複数多項式二次ふるい法)

$ echo "$(openssl prime -bits 100 -generate -safe)*$(openssl prime -bits 100 -generate -safe)" | bc | xargs ./msieve-1.53/msieve -q

...

p31 factor: 1153396382405170806596946382283
p31 factor: 1233154291347766628102667262007
elapsed time 00:00:03

ECM (楕円曲線法):

200ビットだとすぐ求まる:

$ echo "$(openssl prime -bits 100 -generate -safe -checks 200)*$(openssl prime -bits 100 -generate -safe -checks 200)" | \
BC_LINE_LENGTH=999 bc | tee number.txt | xargs ./msieve-1.53/msieve -q -v -e

p31 factor: 1153396382405170806596946382283
p31 factor: 1233154291347766628102667262007
elapsed time 00:00:03

ので、250ビットでやってみると計算時間が急に増大:

$ echo "$(openssl prime -bits 125 -generate -safe -checks 200)*$(openssl prime -bits 125 -generate -safe -checks 200)" | \
BC_LINE_LENGTH=999 bc | tee number.txt | xargs ./msieve-1.53/msieve -q -v -e

...

p38 factor: 37678557816673654138209162703386412367
p38 factor: 41044829572147638975932293376132540459
elapsed time 00:01:05

ログを見ると no P-1/P+1/ECM available, skipping とあり、ECMが使えてない気がする。

GNFS (一般数体ふるい法):

10進80桁以上でないと使えないので入力を300ビットとした。また、入力をファイルに書いておく必要がある

$ echo "$(openssl prime -bits 150 -generate -safe -checks 200)*$(openssl prime -bits 150 -generate -safe -checks 200)" | BC_LINE_LENGTH=999 bc > number.txt && ./msieve-1.53/msieve -v -n -i number.txt


Msieve v. 1.53 (SVN Unversioned directory)
Wed Apr 17 01:13:53 2019
random seeds: 212a3ada 1ac43d44
factoring 1605045377288341641411365792758163726496235567595159788245524834884305941375686373461464169 (91 digits)
no P-1/P+1/ECM available, skipping
commencing number field sieve (91-digit input) #この行が出たらGNFSが使えているはず
commencing number field sieve polynomial selection

...
(現在計算中)

前半では何かのテーブルを作成しているように見える (factor base? .fb ファイル)

(補足) GMP-ECM での `--enable-shared`

GMP-ECM の共有ライブラリをビルドしようと思ったが失敗

Shared library をインストールするのに ar が必要? と思い入れてみる

brew install binutils

うまくいかなかった。ネットで調べると gcc と clang の ar の使用の違いとか言われているので 'gcc' を入れてみる

brew install gcc

やっぱりうまく行かなかったので諦める

【ライブラリの使いかた】Macで素因数分解