高速素因数分解ソフト Msieve を使ってみます

https://sourceforge.net/projects/msieve/

ubuntu 18.04 on MacBookPro Docker でセットアップします

$ sudo apt install -y build-essential libgmp3-dev zlib1g-dev libecm-dev
$ wget https://jaist.dl.sourceforge.net/project/msieve/msieve/Msieve%20v1.53/msieve153_src.tar.gz
$ tar xvf msieve153_src.tar.gz
$ cd msieve-1.53
$ make all ECM=1

素因数分解するターゲットとなる数を作ります

from Crypto.Util.number import *

b = 128

p = getPrime(b)
q = getPrime(b)

n = p * q

print("p :", p)
print("q :", q)
print("n :", n)

p : 301232924948100841508504118779499055081
q : 237351279678538533736478579313958901047
n : 71498020217740890560454784710693626062632337432666489427782288145405681569807

msieve で素因数分解します

$ time ./msieve -q 71498020217740890560454784710693626062632337432666489427782288145405681569807

71498020217740890560454784710693626062632337432666489427782288145405681569807
p39: 237351279678538533736478579313958901047
p39: 301232924948100841508504118779499055081

146.19user 0.16system 2:26.52elapsed 99%CPU (0avgtext+0avgdata 41036maxresident)k
0inputs+12544outputs (0major+19742minor)pagefaults 0swaps

128bit の素数 2 つからなる数だとノートパソコンで 2 分ちょっとで分解できました。