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

> sympy とか pycrypto でいいという噂を聞いた (きっと内部で以下のようなライブラリを使っているはず)
パフォーマンス的にはどうなんだろう

参考サイトがいくつかあるので後で載せる

# GMP (The GNU Multiple Precision Arithmetic Library)

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

```
brew install gmp
```

# GMP-ECM (Elliptic Curve Method)

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


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

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

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

```bash
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 (デフォルト: 複数多項式二次ふるい法)

```bash
$ 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ビットだとすぐ求まる:

```bash
$ 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ビットでやってみると計算時間が急に増大:

```bash
$ 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ビットとした。また、入力をファイルに書いておく必要がある

```bash
$ 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
```

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