Using Yafu to factor a large number

[jibanes]

Hello,

One of my assignment requires me to factor a large number composed of two prime numbers. I've started yafu with a number of thread equal to the number of virutal cores using this executable: http://gilchrist.ca/jeff/factoring/y...n352_win64.zip I have left the other tunables unchanged from the ones distributed within the archive, as such:

B1pm1=100000
B1pp1=20000
B1ecm=11000
rhomax=1000
threads=8
pretest_ratio=0.25
%ggnfs_dir=..\ggnfs-bin\Win32\
ggnfs_dir=../ggnfs-bin/
%ecm_path=..\gmp-ecm\bin\x64\Release\ecm.exe
%ecm_path=../ecm/current/ecm
tune_info= Intel(R) Xeon(R) CPU E5-4650 0 @ 2.70GHz,LINUX64,1.73786e-05,0.200412,0.400046,0.0987873,98.8355,2699.98

I'm using an Intel Core i7-6700HQ CPU @ 2.60Ghz (4 cores, 8 vcores) with 16GB of ram.

My questions:

Do I need to provide a ggnfs-bin binary?
Do I need to change the pretest_ratio?
Do I need to change any other setting?
I am just running yafu-x64.ivybridge.exe with the number as an argument, do I need to encapsulate this in factor()?

The number is ~500 bits long.

[swellman]

Yes you need ggnfs binaries and the paths to each executable. Check here for the most recent to my knowledge.

If you plan on having Yafu run ECM, you’ll need that executable as well.

Much is documented in the Yafu instructions. See https://sites.google.com/site/bbuhrow/ and the sourceforge link contained therein.

Lastly, what is the source of the composite you are attempting to factor? Will you be using SNFS or GNFS?

[chris2be8]

A 500 bit number (about 150 decimal digits) will need the General Number Field sieve (GNFS) to factor in a reasonable time. So you will need the GGNFS lattice sievers and msieve (see YAFU's README file for instructions).

I suggest you start by factoring RSA100 with GNFS (it should not take very long on your system). When you have that working point yafu at your C150 (it will take about 1000 times as long). This saves spending a week sieving only to find the final stages don't work so you have to start again.

Here's RSA100:

1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139

Chris

[jibanes]

Should I change the other variables? (B1pm1, pretest_ratio, etc...)?

[bsquared]

Originally Posted by jibanes

Should I change the other variables? (B1pm1, pretest_ratio, etc...)?

No, you can leave all those at the defaults. The .ini file is another way to set command line switches. docfile.txt has information on the supported switches and what they do.

[jibanes]

Originally Posted by chris2be8

A 500 bit number (about 150 decimal digits) will need the General Number Field sieve (GNFS) to factor in a reasonable time. So you will need the GGNFS lattice sievers and msieve (see YAFU's README file for instructions).

I suggest you start by factoring RSA100 with GNFS (it should not take very long on your system). When you have that working point yafu at your C150 (it will take about 1000 times as long). This saves spending a week sieving only to find the final stages don't work so you have to start again.

Here's RSA100:

1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139

Chris

It took me 5h24mns to do this one, is this normal?

[chris2be8]

My last test run on that number took 3:37:47 on a Intel(R) Pentium(R) 4 CPU 3.06GHz (that was in 2011, and that CPU was pretty old then).

A later run on another c100 took 01:33:27 on 1 core of a 2800GHz |AMD Athlon(tm) II X2 240 Processor.

Your CPU should be about 4 times faster than that (slower clock but newer CPU). Are you sure it's using all 4 cores on your CPU?

Could you post the log from that run? I might be able to see why it took so long.

Chris

[jibanes]

Originally Posted by chris2be8

Could you post the log from that run? I might be able to see why it took so long.

Hello Chris,

My test run was using a single core (out of 4 cores/8 vcores) running windows (Intel Core i7-6700HQ CPU @ 2.60Ghz), I'm doing another test on linux (Intel(R) Core(TM) i5-3470 CPU @ 3.20GHz) with 8 threads to compare it against.

This is what I'm using on linux, please correct me if there is a better way, especially regarding the parameter I'm passing to -c
echo 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 | /usr/bin/time -v ./ecm.py -c 50000 -one -maxmem 500 -threads 8 -out all_out.txt 1000000

[jibanes]

ECM hasn't found them with c=50000; something isn't right.

$ echo 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 | /usr/bin/time -v ./ecm.py -c 50000 -one -maxmem 500 -threads 8 -out all_out.txt 1000000
-> ___________________________________________________________________
-> | Running ecm.py, a Python driver for distributing GMP-ECM work |
-> | on a single machine. It is copyright, 2011-2016, David Cleaver |
-> | and is a conversion of factmsieve.py that is Copyright, 2010, |
-> | Brian Gladman. Version 0.41 (Python 2.6 or later) 3rd Sep 2016 |
-> |_________________________________________________________________|

-> Number(s) to factor:
-> 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 (100 digits)
->=============================================================================
-> Working on number: 152260502792253336...654000350692006139 (100 digits)
-> Currently working on: job0210.txt
-> Starting 8 instances of GMP-ECM...
-> ecm -one -c 6250 -maxmem 62 1000000 < job0210.txt > job0210_t00.txt
-> ecm -one -c 6250 -maxmem 62 1000000 < job0210.txt > job0210_t01.txt
-> ecm -one -c 6250 -maxmem 62 1000000 < job0210.txt > job0210_t02.txt
-> ecm -one -c 6250 -maxmem 62 1000000 < job0210.txt > job0210_t03.txt
-> ecm -one -c 6250 -maxmem 62 1000000 < job0210.txt > job0210_t04.txt
-> ecm -one -c 6250 -maxmem 62 1000000 < job0210.txt > job0210_t05.txt
-> ecm -one -c 6250 -maxmem 62 1000000 < job0210.txt > job0210_t06.txt
-> ecm -one -c 6250 -maxmem 62 1000000 < job0210.txt > job0210_t07.txt

GMP-ECM 6.4.4 [configured with GMP 6.0.0, --enable-asm-redc] [ECM]
Using B1=1000000, B2=1045563762, polynomial Dickson(6), 8 threads
____________________________________________________________________________
Curves Complete | Average seconds/curve | Runtime | ETA
-----------------|---------------------------|---------------|--------------
50000 of 50000 | Stg1 1.537s | Stg2 0.897s | 0d 09:21:49 | 0d 00:00:00

-> *** No factor found.

[VBCurtis]

Why would you run 50,000 curves with B1 = 1M?
What is it you are trying to achieve? 50,000 curves has roughly 50% chance to find a 45-digit factor, while taking three or four times as long to run as GNFS would. Since this is an RSA number, you already know it splits as p50*p50, and you would need 1.5 million curves at this size to expect to find a 50-digit factor. Since there are two such factors, perhaps 750,000 curves would do the trick; of course, you might get lucky or unlucky, as "expected" is definitely NOT "guaranteed".

This is why we don't use ECM as our only factorization tool, and secondarily illustrates why B1 bounds are increased as we continue to try ECM.

[CRGreathouse]

Originally Posted by jibanes

ECM hasn't found them with c=50000; something isn't right.

Originally Posted by jibanes

GMP-ECM 6.4.4 [configured with GMP 6.0.0, --enable-asm-redc] [ECM]
Using B1=1000000, B2=1045563762, polynomial Dickson(6), 8 threads

Since we know the factorization of RSA100, we know that (without Brent-Suyama) you need B1 = 3263521422991, B2 = 865417043661324529. You are off by a factor of 3 million on the former and 1 billion on the latter. With a good polynomial and B-S, you could find it with smaller parameters... if you're lucky. But it will almost take longer than NFS (as VBCurtis mentioned) or SIQS.