msieveをMac OS Xにインストールする
Mac OSでmakeをするために必要なCommand Line Tools for Xcodeのインストールについての記述は省略。
Msieveをダウンロードしてきて、
http://sourceforge.net/projects/msieve/
$ tar xvzf msieve152.tar.gz $ cd msieve-1.52 $ make
とダウンロードしたファイルをmakeすると、
include/gmp_xface.h:19:10: fatal error: 'gmp.h' file not found #include <gmp.h> ^ 1 error generated. make: *** [common/filter/clique.o] Error 1
gmp.hがないと怒られる。このためMsieveより先にGMPをインストールする。GMPは多倍長計算を高速にするためのライブラリとのこと。GMPのインストールの手順はこちらを参考にする。
http://math.digi2.jp/math/mp/mpfr/install.html
ただしgmp-6.1.0.tar.lzはtarで解凍ができないため、gmp-6.1.0.tar.bz2をダウンロードする。
https://gmplib.org/
% tar zxvf gmp-6.1.0.tar.bz2 % cd gmp-4.2.1 % ./configure % make % make check % sudo make install
makeやmake checkがものすごく時間がかかる。GMPがインストールできれば準備完了。もう一度Msieveをmakeする。
$ cd msieve-1.52 $ make
これがうまくいけばMsieveが実行できる。
$ ./msieve -q 0x123456789abcdef
qオプションをつけなくても実行できるが、その場合はmsieve.logに結果が出力されるため、
$ tail msieve.log
でログを確認すること。
最後にメモとしてusageをメモしておく。
$ ./msieve --h Msieve v. 1.52 (SVN Unversioned directory) usage: ./msieve [options] [one_number] numbers starting with '0' are treated as octal, numbers starting with '0x' are treated as hexadecimal options: -s <name> save intermediate results to <name> instead of the default msieve.dat -l <name> append log information to <name> instead of the default msieve.log -i <name> read one or more integers to factor from <name> (default worktodo.ini) instead of from the command line -m manual mode: enter numbers via standard input -q quiet: do not generate any log information, only print any factors found -d <min> deadline: if still sieving after <min> minutes, shut down gracefully (default off) -r <num> stop sieving after finding <num> relations -p run at idle priority -v verbose: write log information to screen as well as to logfile -t <num> use at most <num> threads elliptic curve options: -e perform 'deep' ECM, seek factors > 15 digits quadratic sieve options: -c client: only perform sieving number field sieve options: [nfs_phase] "arguments" where the first part is one or more of: -n use the number field sieve (80+ digits only; performs all NFS tasks in order) -nf <name> read from / write to NFS factor base file <name> instead of the default msieve.fb -np perform only NFS polynomial selection -np1 perform stage 1 of NFS polynomial selection -nps perform NFS polynomial size optimization -npr perform NFS polynomial root optimization -ns perform only NFS sieving -nc perform only NFS combining (all phases) -nc1 perform only NFS filtering -nc2 perform only NFS linear algebra -ncr perform only NFS linear algebra, restarting from a previous checkpoint -nc3 perform only NFS square root the arguments are a space-delimited list of: polynomial selection options: polydegree=X select polynomials with degree X min_coeff=X minimum leading coefficient to search in stage 1 max_coeff=X maximum leading coefficient to search in stage 1 stage1_norm=X the maximum norm value for stage 1 stage2_norm=X the maximum norm value for stage 2 min_evalue=X the minimum score of saved polyomials poly_deadline=X stop searching after X seconds (0 means search forever) X,Y same as 'min_coeff=X max_coeff=Y' line sieving options: X,Y handle sieve lines X to Y inclusive filtering options: filter_mem_mb=X try to limit filtering memory use to X megabytes filter_maxrels=X limit the filtering to using the first X relations in the data file filter_lpbound=X have filtering start by only looking at ideals of size X or larger target_density=X attempt to produce a matrix with X entries per column X,Y same as 'filter_lpbound=X filter_maxrels=Y' linear algebra options: skip_matbuild=1 start the linear algebra but skip building the matrix (assumes it is built already) la_block=X use a block size of X (512<=X<=65536) la_superblock=X use a superblock size of X cado_filter=1 assume filtering used the CADO-NFS suite square root options: dep_first=X start with dependency X, 1<=X<=64 dep_last=Y end with dependency Y, 1<=Y<=64 X,Y same as 'dep_first=X dep_last=Y'
http://stdkmd.com/nrr/msieve_ja.htm
このようにmsieveぐらいならMac OS Xにもインストールできるが、素因数分解に関することを試したい場合はGMPだけならまだしMPFRとMPCが必要なケースも多いので、gccがインストールされている環境でしたほうが確実..。