Tag: ecm

MacBook Pro 编译支持CUDA的MSIEVE

Post author By sskaje
Post date July 16, 2015
No Comments on MacBook Pro 编译支持CUDA的MSIEVE

By @sskaje
Link: https://sskaje.me/2015/07/macbook-pro-%e7%bc%96%e8%af%91%e6%94%af%e6%8c%81cuda%e7%9a%84msieve/

之前试过在CentOS 6上编译GMP-ECM和MSIEVE，后来有一天发现本机的MacPorts带的GMP-ECM不是最新版，当前6.4.4的情况下，MacPorts里的才6.3.
顺道也想侥幸一下看看这个2012款的rmbp能不能上CUDA，于是开始折腾。

环境

MacBook Pro with Retina Display 2012 (GT 650 M)
OS X 10.10.4
MacPorts

安装CUDA环境

CUDA Toolkit官方下载地址是：https://developer.nvidia.com/cuda-downloads
下载里目前最新版本是7.0.29，但是下载完成之后设置里还会提示有新版。
另外，Nvidia官方还给了个NVIDIA CUDA Getting Started Guide for Mac OS X.
我就简单地装了这个toolkit 没配环境变了。

第一次尝试

最早的尝试基于MacPorts自带的gmp和gmp-ecm编译CUDA版本的msieve，顺道还编译了个CPU版本的

# 安装 gmp 和 gmp-ecm
$ port install gmp gmp-ecm
# 编译 msieve，开gpu
PATH=/usr/local/cuda/bin/:$PATH MACHINE_FLAGS="-I/opt/local/include -I/usr/local/cuda/include" LIBS="-L/opt/local/lib -L/usr/local/cuda/lib" make all ECM=1 CUDA=1
# 编译 msieve 无gpu版本
MACHINE_FLAGS="-I/opt/local/include" LIBS="-L/opt/local/lib" make all ECM=1

# 安装 gmp 和 gmp-ecm

$ port install gmp gmp-ecm

# 编译 msieve，开gpu

PATH=/usr/local/cuda/bin/:$PATH MACHINE_FLAGS="-I/opt/local/include -I/usr/local/cuda/include" LIBS="-L/opt/local/lib -L/usr/local/cuda/lib" make all ECM=1 CUDA=1

# 编译 msieve 无gpu版本

MACHINE_FLAGS="-I/opt/local/include" LIBS="-L/opt/local/lib" make all ECM=1

这俩拿 RSA-39 的跑，都正常。但是自己生成了个RSA-256的，就有个ECM里报出的assert，没法工作。于是尝试编译ecm。
中间试过好几种方案，最后记录最后的版本

运行

GPU版本的msieve运行需要b40c/sort_engine_smXX.so，所以如果要移动目录，需要保证这个.so的相对位置。

$ ./msieve-gpu -g 0 -n
deadline: 800 CPU-seconds per coefficient
error (line 1135): CUDA_ERROR_OUT_OF_MEMORY

$ ./msieve-gpu -g 0 -n

deadline: 800 CPU-seconds per coefficient

error (line 1135): CUDA_ERROR_OUT_OF_MEMORY

切回来，花屏。

换个

$ ./msieve-gpu -g 1 -n
error: GPU 1 does not exist or is not CUDA-enabled

1 2	$ ./msieve-gpu -g 1 -n error: GPU 1 does not exist or is not CUDA-enabled

而，MSIEVE的GPU计算部分只在NFS polynomial selection里有用，其他过程没区别，于是白瞎了。

MacBook Pro 编译支持CUDA的MSIEVE by @sskaje: https://sskaje.me/2015/07/macbook-pro-%e7%bc%96%e8%af%91%e6%94%af%e6%8c%81cuda%e7%9a%84msieve/

Incoming search terms:

Tags cado-nfs, cuda, ecm, factor, factorization, ggnfs, gmp, gnfs, integer, integer factorization, msieve, msieve ecm, msieve gmp, NFS, Number Field Sieve, rsa, rsa algorithm, rsa factor, rsa factoring, yafu

Integer Factorization Linux 笔记

Build GMP-ECM on CentOS 6

Post author By sskaje
Post date July 11, 2015
No Comments on Build GMP-ECM on CentOS 6

By @sskaje
Link: https://sskaje.me/2015/07/build-gmp-ecm-centos-6/

1 Download GMP-ECM from http://ecm.gforge.inria.fr/

2 Download GMP-5.1.1 from PUIAS: http://springdale.math.ias.edu/data/puias/computational/6/x86_64/
wget http://springdale.math.ias.edu/data/puias/6/x86_64/os/RPM-GPG-KEY-puias -P /etc/pki/rpm/
Just wget all gmp511-*.rpm and rpm -i

3 Build GMP-ECM
./configure ... --with-gmp-include=/usr/local/gmp/5.1.1/include --with-gmp-lib=/usr/local/gmp/5.1.1/lib64
make

4 Build MSIEVE with ECM
Edit Makefile, add -I and -L to GMP-ECM prefix/{lib,include}
make

5 Add GMP-5.1.1 to ld.so.conf
ldconfig

6 RUN msieve

Build GMP-ECM on CentOS 6 by @sskaje: https://sskaje.me/2015/07/build-gmp-ecm-centos-6/

Tags ecm, ecm centos, ecm centos 6, gmp, gmp centos, gmp centos 6, gmp-ecm, gmp-ecm centos, gmp-ecm centos 6, msieve ecm, msieve ecm centos, msieve ecm centos 6, msieve gmp, msieve gmp centos, msieve gmp centos 6, msieve gmp-ecm, msieve gmp-ecm centos, msieve gmp-ecm centos 6

Integer Factorization OS X 杂七杂八

Factoring Integer on OS X with CADO-NFS

Post author By sskaje
Post date June 20, 2015
No Comments on Factoring Integer on OS X with CADO-NFS

By @sskaje
Link: https://sskaje.me/2015/06/factoring-integer-os-cado-nfs/

Environment: Mac OS X 10.10, MacPorts 2.3.3, CADO-NFS 2.1.1

Dependencies

Make sure all dependencies are installed.
CADO-NFS Required software tools

Required software tools

GMP: usually installed in most Linux distributions (on some Linux distributions you need to install libgmp*-dev including gmp.h, which is not installed by default). Note: make sure to configure GMP with –enable-shared so that a shared library is installed (libgmp.so under Linux) otherwise CADO-NFS might not compile. GMP 5 (or newer) is required.
GCC 4.4 or later ; some others compilers might work, but are unsupported. Both C and C++ compilers are required, with C99 support.
GNU make and CMake (2.6.3 or later) for building (CMake is installed on the fly if missing. This feature requires an Internet connection.)
Support for posix threads.
The main cadofactor.py script uses a lot of unix tools: Python, Python3, ssh, rsync, gzip to mention but a few.

# sudo port install cmake gmp gmp-ecm python34 python34-gmpy2 
# cd /opt/local/bin;
# ln -s python3.4 python3

# sudo port install cmake gmp gmp-ecm python34 python34-gmpy2

# cd /opt/local/bin;

# ln -s python3.4 python3

Install

just type make after tar xvf

Test

Msieve

Using msieve 1.51 from MacPorts and CADO-NFS. The integer is 179399505810976971998364784462504058921, used in old versions of IntelliJ IDEA.
Msieve find its factor in 1 second, no extra parameter used.

#  msieve 179399505810976971998364784462504058921
sieving in progress (press Ctrl-C to pause)
632 relations (273 full + 359 combined from 2370 partial), need 546
sieving complete, commencing postprocessing

# cat msieve.log
Sat Jun 20 14:00:42 2015  
Sat Jun 20 14:00:42 2015  
Sat Jun 20 14:00:42 2015  Msieve v. 1.51 (SVN Unversioned directory)
Sat Jun 20 14:00:42 2015  random seeds: abc834a8 c907c2ba
Sat Jun 20 14:00:42 2015  factoring 179399505810976971998364784462504058921 (39 digits)
Sat Jun 20 14:00:42 2015  no P-1/P+1/ECM available, skipping
Sat Jun 20 14:00:42 2015  commencing quadratic sieve (39-digit input)
Sat Jun 20 14:00:42 2015  using multiplier of 1
Sat Jun 20 14:00:42 2015  using generic 32kb sieve core
Sat Jun 20 14:00:42 2015  sieve interval: 4 blocks of size 32768
Sat Jun 20 14:00:42 2015  processing polynomials in batches of 51
Sat Jun 20 14:00:42 2015  using a sieve bound of 6961 (450 primes)
Sat Jun 20 14:00:42 2015  using large prime bound of 278440 (18 bits)
Sat Jun 20 14:00:42 2015  polynomial 'A' values have 5 factors
Sat Jun 20 14:00:42 2015  665 relations (276 full + 389 combined from 2450 partial), need 546
Sat Jun 20 14:00:42 2015  begin with 2726 relations
Sat Jun 20 14:00:42 2015  reduce to 986 relations in 2 passes
Sat Jun 20 14:00:42 2015  attempting to read 986 relations
Sat Jun 20 14:00:42 2015  recovered 986 relations
Sat Jun 20 14:00:42 2015  recovered 128 polynomials
Sat Jun 20 14:00:42 2015  attempting to build 665 cycles
Sat Jun 20 14:00:42 2015  found 665 cycles in 1 passes
Sat Jun 20 14:00:42 2015  distribution of cycle lengths:
Sat Jun 20 14:00:42 2015     length 1 : 276
Sat Jun 20 14:00:42 2015     length 2 : 389
Sat Jun 20 14:00:42 2015  largest cycle: 2 relations
Sat Jun 20 14:00:42 2015  matrix is 450 x 665 (0.1 MB) with weight 12334 (18.55/col)
Sat Jun 20 14:00:42 2015  sparse part has weight 12334 (18.55/col)
Sat Jun 20 14:00:42 2015  filtering completed in 3 passes
Sat Jun 20 14:00:42 2015  matrix is 430 x 494 (0.0 MB) with weight 8241 (16.68/col)
Sat Jun 20 14:00:42 2015  sparse part has weight 8241 (16.68/col)
Sat Jun 20 14:00:42 2015  commencing Lanczos iteration
Sat Jun 20 14:00:42 2015  memory use: 0.0 MB
Sat Jun 20 14:00:42 2015  lanczos halted after 8 iterations (dim = 426)
Sat Jun 20 14:00:42 2015  recovered 61 nontrivial dependencies
Sat Jun 20 14:00:42 2015  prp19 factor: 9939430972488238699
Sat Jun 20 14:00:42 2015  prp20 factor: 18049273274048008379
Sat Jun 20 14:00:42 2015  elapsed time 00:00:00

# msieve 179399505810976971998364784462504058921

sieving in progress (press Ctrl-C to pause)

632 relations (273 full + 359 combined from 2370 partial), need 546

sieving complete, commencing postprocessing

# cat msieve.log

Sat Jun 20 14:00:42 2015

Sat Jun 20 14:00:42 2015 Msieve v. 1.51 (SVN Unversioned directory)

Sat Jun 20 14:00:42 2015 random seeds: abc834a8 c907c2ba

Sat Jun 20 14:00:42 2015 factoring 179399505810976971998364784462504058921 (39 digits)

Sat Jun 20 14:00:42 2015 no P-1/P+1/ECM available, skipping

Sat Jun 20 14:00:42 2015 commencing quadratic sieve (39-digit input)

Sat Jun 20 14:00:42 2015 using multiplier of 1

Sat Jun 20 14:00:42 2015 using generic 32kb sieve core

Sat Jun 20 14:00:42 2015 sieve interval: 4 blocks of size 32768

Sat Jun 20 14:00:42 2015 processing polynomials in batches of 51

Sat Jun 20 14:00:42 2015 using a sieve bound of 6961 (450 primes)

Sat Jun 20 14:00:42 2015 using large prime bound of 278440 (18 bits)

Sat Jun 20 14:00:42 2015 polynomial 'A' values have 5 factors

Sat Jun 20 14:00:42 2015 665 relations (276 full + 389 combined from 2450 partial), need 546

Sat Jun 20 14:00:42 2015 begin with 2726 relations

Sat Jun 20 14:00:42 2015 reduce to 986 relations in 2 passes

Sat Jun 20 14:00:42 2015 attempting to read 986 relations

Sat Jun 20 14:00:42 2015 recovered 986 relations

Sat Jun 20 14:00:42 2015 recovered 128 polynomials

Sat Jun 20 14:00:42 2015 attempting to build 665 cycles

Sat Jun 20 14:00:42 2015 found 665 cycles in 1 passes

Sat Jun 20 14:00:42 2015 distribution of cycle lengths:

Sat Jun 20 14:00:42 2015 length 1 : 276

Sat Jun 20 14:00:42 2015 length 2 : 389

Sat Jun 20 14:00:42 2015 largest cycle: 2 relations

Sat Jun 20 14:00:42 2015 matrix is 450 x 665 (0.1 MB) with weight 12334 (18.55/col)

Sat Jun 20 14:00:42 2015 sparse part has weight 12334 (18.55/col)

Sat Jun 20 14:00:42 2015 filtering completed in 3 passes

Sat Jun 20 14:00:42 2015 matrix is 430 x 494 (0.0 MB) with weight 8241 (16.68/col)

Sat Jun 20 14:00:42 2015 sparse part has weight 8241 (16.68/col)

Sat Jun 20 14:00:42 2015 commencing Lanczos iteration

Sat Jun 20 14:00:42 2015 memory use: 0.0 MB

Sat Jun 20 14:00:42 2015 lanczos halted after 8 iterations (dim = 426)

Sat Jun 20 14:00:42 2015 recovered 61 nontrivial dependencies

Sat Jun 20 14:00:42 2015 prp19 factor: 9939430972488238699

Sat Jun 20 14:00:42 2015 prp20 factor: 18049273274048008379

Sat Jun 20 14:00:42 2015 elapsed time 00:00:00

CADO-NFS

Make sure your hostname is added to /etc/hosts, or you’ll get error like:

sskajedemini:cado-nfs-2.1.1 sskaje$ ./factor.sh 179399505810976971998364784462504058921 -t 2
Info:root: Command line parameters: /Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor/cadofactor.py /tmp/cado.fbmdQ6zdbs/param 'N=179399505810976971998364784462504058921' 'tasks.execpath=/Users/sskaje/Work/cado/cado-nfs-2.1.1/build/sskajedemini' 'tasks.threads=2' 'tasks.workdir=/tmp/cado.fbmdQ6zdbs' 'slaves.hostnames=localhost' 'slaves.nrclients=1' 'slaves.scriptpath=/Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor' 'server.address=localhost' 'slaves.basepath=/tmp/cado.fbmdQ6zdbs/client/'
Info:Server Launcher: Adding sskajedemini to whitelist to allow clients on localhost to connect
Info:HTTP server: Using non-threaded HTTPS server
Info:HTTP server: Using whitelist: localhost,192.168.0.0/16,localhost,sskajedemini
Traceback (most recent call last):
  File "/Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor/cadofactor.py", line 71, in <module>
    path_prefix = [])
  File "/Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor/cadotask.py", line 4568, in __init__
    whitelist=whitelist)
  File "/Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor/cadotask.py", line 4201, in __init__
    whitelist=server_whitelist)
  File "/Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor/wuserver.py", line 731, in __init__
    whitelist=whitelist, certfile=self.cafile)
  File "/Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor/wuserver.py", line 138, in __init__
    bind_and_activate=False, **kwargs)
  File "/Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor/wuserver.py", line 47, in __init__
    "CIDR notation)" % iprange)
ValueError: sskajedemini it not a valid IP range (must be CIDR notation)
FAILED ; data left in /tmp/cado.fbmdQ6zdbs

sskajedemini:cado-nfs-2.1.1 sskaje$ ./factor.sh 179399505810976971998364784462504058921 -t 2

Info:root: Command line parameters: /Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor/cadofactor.py /tmp/cado.fbmdQ6zdbs/param 'N=179399505810976971998364784462504058921' 'tasks.execpath=/Users/sskaje/Work/cado/cado-nfs-2.1.1/build/sskajedemini' 'tasks.threads=2' 'tasks.workdir=/tmp/cado.fbmdQ6zdbs' 'slaves.hostnames=localhost' 'slaves.nrclients=1' 'slaves.scriptpath=/Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor' 'server.address=localhost' 'slaves.basepath=/tmp/cado.fbmdQ6zdbs/client/'

Info:Server Launcher: Adding sskajedemini to whitelist to allow clients on localhost to connect

Info:HTTP server: Using non-threaded HTTPS server

Info:HTTP server: Using whitelist: localhost,192.168.0.0/16,localhost,sskajedemini

Traceback (most recent call last):

File "/Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor/cadofactor.py", line 71, in <module>

path_prefix = [])

File "/Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor/cadotask.py", line 4568, in __init__

whitelist=whitelist)

File "/Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor/cadotask.py", line 4201, in __init__

whitelist=server_whitelist)

File "/Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor/wuserver.py", line 731, in __init__

whitelist=whitelist, certfile=self.cafile)

File "/Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor/wuserver.py", line 138, in __init__

bind_and_activate=False, **kwargs)

File "/Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor/wuserver.py", line 47, in __init__

"CIDR notation)" % iprange)

ValueError: sskajedemini it not a valid IP range (must be CIDR notation)

FAILED ; data left in /tmp/cado.fbmdQ6zdbs

And, the number is to small for CADO-NFS, you have to copy a params file for this.

no parameter file found for c39 (last tried was /Users/sskaje/Work/cado/cado-nfs-2.1.1/params/params.c41)

1	no parameter file found for c39 (last tried was /Users/sskaje/Work/cado/cado-nfs-2.1.1/params/params.c41)

Here is the output of factor.sh

./factor.sh 179399505810976971998364784462504058921 -t 2
Info:root: Command line parameters: /Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor/cadofactor.py /tmp/cado.7tGd7jOZu9/param 'N=179399505810976971998364784462504058921' 'tasks.execpath=/Users/sskaje/Work/cado/cado-nfs-2.1.1/build/sskajedemini' 'tasks.threads=2' 'tasks.workdir=/tmp/cado.7tGd7jOZu9' 'slaves.hostnames=localhost' 'slaves.nrclients=1' 'slaves.scriptpath=/Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor' 'server.address=localhost' 'slaves.basepath=/tmp/cado.7tGd7jOZu9/client/'
Info:Server Launcher: Adding sskajedemini to whitelist to allow clients on localhost to connect
Info:HTTP server: Using non-threaded HTTPS server
Info:HTTP server: Using whitelist: localhost,192.168.0.0/16,localhost,sskajedemini
Warning:HTTP server: Server is listening on the loopback device. Clients on other hosts will not be able to connect.
Info:Complete Factorization: Factoring 179399505810976971998364784462504058921
Info:HTTP server: serving at https://localhost:8001 (127.0.0.1)
Info:HTTP server: For debugging purposes, the URL above can be accessed if the server.only_registered=False parameter is added
Info:HTTP server: You can start additional wuclient2.py scripts with parameters: --server=https://localhost:8001 --certsha1=bf72290763b385cbca4be9a98a7678ec79fe68ec
Info:HTTP server: If you want to start additional clients, remember to add their hosts to server.whitelist
Info:Client Launcher: Starting client id localhost on host localhost
Info:Client Launcher: Running clients: localhost (Host localhost, PID 42957)
Info:Polynomial Selection (size optimized): Starting
Info:Polynomial Selection (size optimized): 0 polynomials in queue from previous run
Info:Polynomial Selection (size optimized): Adding workunit c39_polyselect1_0-5000 to database
Info:Polynomial Selection (size optimized): Adding workunit c39_polyselect1_5000-10000 to database
Info:HTTP server: 127.0.0.1 Sending workunit c39_polyselect1_0-5000 to client localhost
Info:HTTP server: 127.0.0.1 Sending workunit c39_polyselect1_5000-10000 to client localhost
Info:Polynomial Selection (size optimized): Parsed 12 polynomials, added 12 to priority queue (has 12/20)
Info:Polynomial Selection (size optimized): Worst polynomial in queue now has lognorm 14.040000
Info:Polynomial Selection (size optimized): Marking workunit c39_polyselect1_0-5000 as ok
Info:Polynomial Selection (size optimized): Parsed 11 polynomials, added 10 to priority queue (has 20)
Info:Polynomial Selection (size optimized): Worst polynomial in queue now has lognorm 14.030000
Info:Polynomial Selection (size optimized): Marking workunit c39_polyselect1_5000-10000 as ok
Info:Polynomial Selection (size optimized): Finished
Info:Polynomial Selection (root optimized): Starting
Info:Polynomial Selection (root optimized): No polynomial was previously found
Info:Polynomial Selection (root optimized): Adding workunit c39_polyselect2_0 to database
Info:Polynomial Selection (root optimized): Adding workunit c39_polyselect2_5 to database
Info:Polynomial Selection (root optimized): Adding workunit c39_polyselect2_10 to database
Info:Polynomial Selection (root optimized): Adding workunit c39_polyselect2_15 to database
Info:HTTP server: 127.0.0.1 Sending workunit c39_polyselect2_0 to client localhost
Info:Polynomial Selection (root optimized): New best polynomial from file /tmp/cado.7tGd7jOZu9/c39.upload/c39.polyselect2.zb3zq_jg.opt_0: Murphy E = 4.95e-06
Info:Polynomial Selection (root optimized): Marking workunit c39_polyselect2_0 as ok
Info:HTTP server: 127.0.0.1 Sending workunit c39_polyselect2_5 to client localhost
Info:Polynomial Selection (root optimized): Best polynomial from file /tmp/cado.7tGd7jOZu9/c39.upload/c39.polyselect2.be59uo4y.opt_5 with E=3.96e-06 is no better than current best with E=4.95e-06
Info:Polynomial Selection (root optimized): Marking workunit c39_polyselect2_5 as ok
Info:HTTP server: 127.0.0.1 Sending workunit c39_polyselect2_10 to client localhost
Info:Polynomial Selection (root optimized): New best polynomial from file /tmp/cado.7tGd7jOZu9/c39.upload/c39.polyselect2.j_0h8yhf.opt_10: Murphy E = 5.79e-06
Info:Polynomial Selection (root optimized): Marking workunit c39_polyselect2_10 as ok
Info:HTTP server: 127.0.0.1 Sending workunit c39_polyselect2_15 to client localhost
Info:Polynomial Selection (root optimized): Best polynomial from file /tmp/cado.7tGd7jOZu9/c39.upload/c39.polyselect2.ybo7t7p0.opt_15 with E=5.38e-06 is no better than current best with E=5.79e-06
Info:Polynomial Selection (root optimized): Marking workunit c39_polyselect2_15 as ok
Info:Polynomial Selection (root optimized): Finished, best polynomial from file /tmp/cado.7tGd7jOZu9/c39.upload/c39.polyselect2.j_0h8yhf.opt_10 has Murphy_E = 5.79e-06
Info:Polynomial Selection (root optimized): Best overall polynomial was 9-th in list after size optimization
Info:Generate Factor Base: Starting
Info:Generate Factor Base: Finished
Info:Generate Free Relations: Starting
Info:Generate Free Relations: Found 12299 free relations
Info:Generate Free Relations: Finished
Info:Lattice Sieving: Starting
Info:Lattice Sieving: Adding workunit c39_sieving_200000-201000 to database
Info:Lattice Sieving: Adding workunit c39_sieving_201000-202000 to database
Info:Lattice Sieving: Adding workunit c39_sieving_202000-203000 to database
Info:Lattice Sieving: Adding workunit c39_sieving_203000-204000 to database
Info:Lattice Sieving: Adding workunit c39_sieving_204000-205000 to database
Info:Lattice Sieving: Adding workunit c39_sieving_205000-206000 to database
Info:Lattice Sieving: Adding workunit c39_sieving_206000-207000 to database
Info:Lattice Sieving: Adding workunit c39_sieving_207000-208000 to database
Info:Lattice Sieving: Adding workunit c39_sieving_208000-209000 to database
Info:Lattice Sieving: Adding workunit c39_sieving_209000-210000 to database
Info:HTTP server: 127.0.0.1 Sending workunit c39_sieving_200000-201000 to client localhost
Info:Lattice Sieving: Adding workunit c39_sieving_210000-211000 to database
Info:Lattice Sieving: Found 290514 relations in '/tmp/cado.7tGd7jOZu9/c39.upload/c39.sieving.200000-201000.k1ukelos.gz', total is now 290514/222540
Info:Lattice Sieving: Marking workunit c39_sieving_200000-201000 as ok
Info:HTTP server: 127.0.0.1 Sending workunit c39_sieving_201000-202000 to client localhost
Info:Lattice Sieving: Adding workunit c39_sieving_211000-212000 to database
Info:Lattice Sieving: Reached target of 222540 relations, now have 290514
Info:Filtering - Duplicate Removal, splitting pass: Starting
Info:Filtering - Duplicate Removal, splitting pass: Splitting 1 new files
Info:Filtering - Duplicate Removal, splitting pass: Relations per slice: 0: 144987, 1: 145527
Info:Filtering - Duplicate Removal, removal pass: Starting
Info:Filtering - Duplicate Removal, removal pass: 144942 unique relations remain on slice 0
Info:Filtering - Duplicate Removal, removal pass: 145489 unique relations remain on slice 1
Info:Filtering - Duplicate Removal, removal pass: Of 290514 newly added relations 290431 were unique (ratio 0.999714)
Info:Filtering - Duplicate Removal, removal pass: 290431 unique relations remain in total
Info:Filtering - Singleton removal: Starting
Info:Filtering - Singleton removal: Reading 290431 unique and 12299 free relations, total 302730
Info:Filtering - Singleton removal: After purge, 12521 relations with 12361 primes remain with weight 169861 and excess 160
Info:Filtering - Singleton removal: Have enough relations
Info:HTTP server: Got notification to stop serving Workunits
Info:Lattice Sieving: Cancelling remaining workunits
Info:Client Launcher: Stopped client localhost (Host localhost, PID 42957)
Info:Filtering - Merging: Starting
Info:Linear Algebra: Starting
Info:Quadratic Characters: Starting
Info:Square Root: Starting
Info:Square Root: Creating file of (a,b) values
Info:Square Root: Trying dependency 0
Info:Square Root: Trying dependency 1
Info:Square Root: Trying dependency 2
Info:Square Root: finished
Info:Square Root: Factors: 9939430972488238699 18049273274048008379
Info:Polynomial Selection (size optimized): Aggregate statistics:
Info:Polynomial Selection (size optimized): potential collisions: 20.16
Info:Polynomial Selection (size optimized): raw lognorm (nr/min/av/max/std): 24/12.940/13.808/14.390/0.407
Info:Polynomial Selection (size optimized): optimized lognorm (nr/min/av/max/std): 23/12.560/13.646/14.270/0.424
Info:Polynomial Selection (size optimized): 10 best raw logmu: 12.94 13.05 13.25 13.26 13.39 13.4 13.5 13.66 13.75 13.85
Info:Polynomial Selection (size optimized): 10 best opt logmu: 12.56 12.93 12.99 13.19 13.24 13.37 13.4 13.49 13.52 13.71
Info:Polynomial Selection (size optimized): Total time: 0.29
Info:Polynomial Selection (root optimized): Aggregate statistics:
Info:Polynomial Selection (root optimized): Total time: 7.22, rootsieve time: 7.11
Info:Generate Factor Base: Total cpu/real time for makefb: 0.12/0.112941
Info:Generate Free Relations: Total cpu/real time for freerel: 3.25/3.18402
Info:Lattice Sieving: Aggregate statistics:
Info:Lattice Sieving: Total number of relations: 290514
Info:Lattice Sieving: Average J: 965 for 87 special-q, max bucket fill: 0.723788
Info:Lattice Sieving: Total CPU time: 5s
Info:Filtering - Duplicate Removal, splitting pass: Total cpu/real time for dup1: 0.71/3.49601
Info:Filtering - Duplicate Removal, removal pass: Total cpu/real time for dup2: 3.32/7.81877
Info:Filtering - Singleton removal: Total cpu/real time for purge: 2.19/6.07935
Info:Filtering - Merging: Total cpu/real time for merge: 0.25/0.267617
Info:Filtering - Merging: Total cpu/real time for replay: 0.08/0.0859129
Info:Linear Algebra: Total cpu/real time for bwc: 1.75/1.76682
Info:Linear Algebra: Aggregate statistics:
Info:Linear Algebra: Krylov: CPU time 0.03, COMM time 0.02
Info:Linear Algebra: Lingen CPU time 1.49
Info:Linear Algebra: Mksol: CPU time 0.03, COMM time 0.02
Info:Quadratic Characters: Total cpu/real time for characters: 0.1/0.073977
Info:Square Root: Total cpu/real time for sqrt: 0.41/0.401544
Info:HTTP server: Shutting down HTTP server
Info:Complete Factorization: Total cpu/elapsed time for entire factorization: 24.69/402.458
9939430972488238699 18049273274048008379
OK

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

./factor.sh 179399505810976971998364784462504058921 -t 2

Info:root: Command line parameters: /Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor/cadofactor.py /tmp/cado.7tGd7jOZu9/param 'N=179399505810976971998364784462504058921' 'tasks.execpath=/Users/sskaje/Work/cado/cado-nfs-2.1.1/build/sskajedemini' 'tasks.threads=2' 'tasks.workdir=/tmp/cado.7tGd7jOZu9' 'slaves.hostnames=localhost' 'slaves.nrclients=1' 'slaves.scriptpath=/Users/sskaje/Work/cado/cado-nfs-2.1.1/scripts/cadofactor' 'server.address=localhost' 'slaves.basepath=/tmp/cado.7tGd7jOZu9/client/'

Info:Server Launcher: Adding sskajedemini to whitelist to allow clients on localhost to connect

Info:HTTP server: Using non-threaded HTTPS server

Info:HTTP server: Using whitelist: localhost,192.168.0.0/16,localhost,sskajedemini

Warning:HTTP server: Server is listening on the loopback device. Clients on other hosts will not be able to connect.

Info:Complete Factorization: Factoring 179399505810976971998364784462504058921

Info:HTTP server: serving at https://localhost:8001 (127.0.0.1)

Info:HTTP server: For debugging purposes, the URL above can be accessed if the server.only_registered=False parameter is added

Info:HTTP server: You can start additional wuclient2.py scripts with parameters: --server=https://localhost:8001 --certsha1=bf72290763b385cbca4be9a98a7678ec79fe68ec

Info:HTTP server: If you want to start additional clients, remember to add their hosts to server.whitelist

Info:Client Launcher: Starting client id localhost on host localhost

Info:Client Launcher: Running clients: localhost (Host localhost, PID 42957)

Info:Polynomial Selection (size optimized): Starting

Info:Polynomial Selection (size optimized): 0 polynomials in queue from previous run

Info:Polynomial Selection (size optimized): Adding workunit c39_polyselect1_0-5000 to database

Info:Polynomial Selection (size optimized): Adding workunit c39_polyselect1_5000-10000 to database

Info:HTTP server: 127.0.0.1 Sending workunit c39_polyselect1_0-5000 to client localhost

Info:HTTP server: 127.0.0.1 Sending workunit c39_polyselect1_5000-10000 to client localhost

Info:Polynomial Selection (size optimized): Parsed 12 polynomials, added 12 to priority queue (has 12/20)

Info:Polynomial Selection (size optimized): Worst polynomial in queue now has lognorm 14.040000

Info:Polynomial Selection (size optimized): Marking workunit c39_polyselect1_0-5000 as ok

Info:Polynomial Selection (size optimized): Parsed 11 polynomials, added 10 to priority queue (has 20)

Info:Polynomial Selection (size optimized): Worst polynomial in queue now has lognorm 14.030000

Info:Polynomial Selection (size optimized): Marking workunit c39_polyselect1_5000-10000 as ok

Info:Polynomial Selection (size optimized): Finished

Info:Polynomial Selection (root optimized): Starting

Info:Polynomial Selection (root optimized): No polynomial was previously found

Info:Polynomial Selection (root optimized): Adding workunit c39_polyselect2_0 to database

Info:Polynomial Selection (root optimized): Adding workunit c39_polyselect2_5 to database

Info:Polynomial Selection (root optimized): Adding workunit c39_polyselect2_10 to database

Info:Polynomial Selection (root optimized): Adding workunit c39_polyselect2_15 to database

Info:HTTP server: 127.0.0.1 Sending workunit c39_polyselect2_0 to client localhost

Info:Polynomial Selection (root optimized): New best polynomial from file /tmp/cado.7tGd7jOZu9/c39.upload/c39.polyselect2.zb3zq_jg.opt_0: Murphy E = 4.95e-06

Info:Polynomial Selection (root optimized): Marking workunit c39_polyselect2_0 as ok

Info:HTTP server: 127.0.0.1 Sending workunit c39_polyselect2_5 to client localhost

Info:Polynomial Selection (root optimized): Best polynomial from file /tmp/cado.7tGd7jOZu9/c39.upload/c39.polyselect2.be59uo4y.opt_5 with E=3.96e-06 is no better than current best with E=4.95e-06

Info:Polynomial Selection (root optimized): Marking workunit c39_polyselect2_5 as ok

Info:HTTP server: 127.0.0.1 Sending workunit c39_polyselect2_10 to client localhost

Info:Polynomial Selection (root optimized): New best polynomial from file /tmp/cado.7tGd7jOZu9/c39.upload/c39.polyselect2.j_0h8yhf.opt_10: Murphy E = 5.79e-06

Info:Polynomial Selection (root optimized): Marking workunit c39_polyselect2_10 as ok

Info:HTTP server: 127.0.0.1 Sending workunit c39_polyselect2_15 to client localhost

Info:Polynomial Selection (root optimized): Best polynomial from file /tmp/cado.7tGd7jOZu9/c39.upload/c39.polyselect2.ybo7t7p0.opt_15 with E=5.38e-06 is no better than current best with E=5.79e-06

Info:Polynomial Selection (root optimized): Marking workunit c39_polyselect2_15 as ok

Info:Polynomial Selection (root optimized): Finished, best polynomial from file /tmp/cado.7tGd7jOZu9/c39.upload/c39.polyselect2.j_0h8yhf.opt_10 has Murphy_E = 5.79e-06

Info:Polynomial Selection (root optimized): Best overall polynomial was 9-th in list after size optimization

Info:Generate Factor Base: Starting

Info:Generate Factor Base: Finished

Info:Generate Free Relations: Starting

Info:Generate Free Relations: Found 12299 free relations

Info:Generate Free Relations: Finished

Info:Lattice Sieving: Starting

Info:Lattice Sieving: Adding workunit c39_sieving_200000-201000 to database

Info:Lattice Sieving: Adding workunit c39_sieving_201000-202000 to database

Info:Lattice Sieving: Adding workunit c39_sieving_202000-203000 to database

Info:Lattice Sieving: Adding workunit c39_sieving_203000-204000 to database

Info:Lattice Sieving: Adding workunit c39_sieving_204000-205000 to database

Info:Lattice Sieving: Adding workunit c39_sieving_205000-206000 to database

Info:Lattice Sieving: Adding workunit c39_sieving_206000-207000 to database

Info:Lattice Sieving: Adding workunit c39_sieving_207000-208000 to database

Info:Lattice Sieving: Adding workunit c39_sieving_208000-209000 to database

Info:Lattice Sieving: Adding workunit c39_sieving_209000-210000 to database

Info:HTTP server: 127.0.0.1 Sending workunit c39_sieving_200000-201000 to client localhost

Info:Lattice Sieving: Adding workunit c39_sieving_210000-211000 to database

Info:Lattice Sieving: Found 290514 relations in '/tmp/cado.7tGd7jOZu9/c39.upload/c39.sieving.200000-201000.k1ukelos.gz', total is now 290514/222540

Info:Lattice Sieving: Marking workunit c39_sieving_200000-201000 as ok

Info:HTTP server: 127.0.0.1 Sending workunit c39_sieving_201000-202000 to client localhost

Info:Lattice Sieving: Adding workunit c39_sieving_211000-212000 to database

Info:Lattice Sieving: Reached target of 222540 relations, now have 290514

Info:Filtering - Duplicate Removal, splitting pass: Starting

Info:Filtering - Duplicate Removal, splitting pass: Splitting 1 new files

Info:Filtering - Duplicate Removal, splitting pass: Relations per slice: 0: 144987, 1: 145527

Info:Filtering - Duplicate Removal, removal pass: Starting

Info:Filtering - Duplicate Removal, removal pass: 144942 unique relations remain on slice 0

Info:Filtering - Duplicate Removal, removal pass: 145489 unique relations remain on slice 1

Info:Filtering - Duplicate Removal, removal pass: Of 290514 newly added relations 290431 were unique (ratio 0.999714)

Info:Filtering - Duplicate Removal, removal pass: 290431 unique relations remain in total

Info:Filtering - Singleton removal: Starting

Info:Filtering - Singleton removal: Reading 290431 unique and 12299 free relations, total 302730

Info:Filtering - Singleton removal: After purge, 12521 relations with 12361 primes remain with weight 169861 and excess 160

Info:Filtering - Singleton removal: Have enough relations

Info:HTTP server: Got notification to stop serving Workunits

Info:Lattice Sieving: Cancelling remaining workunits

Info:Client Launcher: Stopped client localhost (Host localhost, PID 42957)

Info:Filtering - Merging: Starting

Info:Linear Algebra: Starting

Info:Quadratic Characters: Starting

Info:Square Root: Starting

Info:Square Root: Creating file of (a,b) values

Info:Square Root: Trying dependency 0

Info:Square Root: Trying dependency 1

Info:Square Root: Trying dependency 2

Info:Square Root: finished

Info:Square Root: Factors: 9939430972488238699 18049273274048008379

Info:Polynomial Selection (size optimized): Aggregate statistics:

Info:Polynomial Selection (size optimized): potential collisions: 20.16

Info:Polynomial Selection (size optimized): raw lognorm (nr/min/av/max/std): 24/12.940/13.808/14.390/0.407

Info:Polynomial Selection (size optimized): optimized lognorm (nr/min/av/max/std): 23/12.560/13.646/14.270/0.424

Info:Polynomial Selection (size optimized): 10 best raw logmu: 12.94 13.05 13.25 13.26 13.39 13.4 13.5 13.66 13.75 13.85

Info:Polynomial Selection (size optimized): 10 best opt logmu: 12.56 12.93 12.99 13.19 13.24 13.37 13.4 13.49 13.52 13.71

Info:Polynomial Selection (size optimized): Total time: 0.29

Info:Polynomial Selection (root optimized): Aggregate statistics:

Info:Polynomial Selection (root optimized): Total time: 7.22, rootsieve time: 7.11

Info:Generate Factor Base: Total cpu/real time for makefb: 0.12/0.112941

Info:Generate Free Relations: Total cpu/real time for freerel: 3.25/3.18402

Info:Lattice Sieving: Aggregate statistics:

Info:Lattice Sieving: Total number of relations: 290514

Info:Lattice Sieving: Average J: 965 for 87 special-q, max bucket fill: 0.723788

Info:Lattice Sieving: Total CPU time: 5s

Info:Filtering - Duplicate Removal, splitting pass: Total cpu/real time for dup1: 0.71/3.49601

Info:Filtering - Duplicate Removal, removal pass: Total cpu/real time for dup2: 3.32/7.81877

Info:Filtering - Singleton removal: Total cpu/real time for purge: 2.19/6.07935

Info:Filtering - Merging: Total cpu/real time for merge: 0.25/0.267617

Info:Filtering - Merging: Total cpu/real time for replay: 0.08/0.0859129

Info:Linear Algebra: Total cpu/real time for bwc: 1.75/1.76682

Info:Linear Algebra: Aggregate statistics:

Info:Linear Algebra: Krylov: CPU time 0.03, COMM time 0.02

Info:Linear Algebra: Lingen CPU time 1.49

Info:Linear Algebra: Mksol: CPU time 0.03, COMM time 0.02

Info:Quadratic Characters: Total cpu/real time for characters: 0.1/0.073977

Info:Square Root: Total cpu/real time for sqrt: 0.41/0.401544

Info:HTTP server: Shutting down HTTP server

Info:Complete Factorization: Total cpu/elapsed time for entire factorization: 24.69/402.458

9939430972488238699 18049273274048008379

Maybe CADO-NFS is not really good for small integers.

Factoring Integer on OS X with CADO-NFS by @sskaje: https://sskaje.me/2015/06/factoring-integer-os-cado-nfs/

Tags cado-nfs, cuda, ecm, factor, factorization, ggnfs, gmp, gnfs, integer, integer factorization, msieve, msieve ecm, msieve gmp, NFS, Number Field Sieve, rsa, rsa algorithm, rsa factor, rsa factoring, yafu

环境