mersenneforum.org > YAFU Using Yafu to factor a large number
 Register FAQ Search Today's Posts Mark Forums Read

 2018-02-03, 14:57 #1 jibanes   Feb 2018 19 Posts Using Yafu to factor a large number 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.
 2018-02-03, 16:43 #2 swellman     Jun 2012 22·23·31 Posts 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?
 2018-02-03, 16:48 #3 chris2be8     Sep 2009 2·33·5·7 Posts 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: Code: 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 Chris
 2018-02-03, 22:15 #4 jibanes   Feb 2018 19 Posts Should I change the other variables? (B1pm1, pretest_ratio, etc...)?
2018-02-04, 03:08   #5
bsquared

"Ben"
Feb 2007

CDA16 Posts

Quote:
 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.

2018-02-04, 15:07   #6
jibanes

Feb 2018

19 Posts

Quote:
 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: Code: 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 Chris
It took me 5h24mns to do this one, is this normal?

 2018-02-04, 16:53 #7 chris2be8     Sep 2009 2×33×5×7 Posts 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
2018-02-04, 17:48   #8
jibanes

Feb 2018

19 Posts

Quote:
 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

Last fiddled with by jibanes on 2018-02-04 at 17:52

 2018-02-05, 01:33 #9 jibanes   Feb 2018 1910 Posts 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.
 2018-02-05, 01:57 #10 VBCurtis     "Curtis" Feb 2005 Riverside, CA 103248 Posts 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.
2018-02-05, 03:27   #11
CRGreathouse

Aug 2006

31×191 Posts

Quote:
 Originally Posted by jibanes ECM hasn't found them with c=50000; something isn't right.
Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post 2147483647 YAFU 3 2016-12-25 21:44 craneduitre Msieve 23 2016-07-10 08:13 al3ndaleeb YAFU 3 2015-05-30 19:54 Zeta-Flux Factoring 96 2007-05-14 16:59 dsouza123 Software 3 2003-12-11 00:48

All times are UTC. The time now is 00:23.

Sat Sep 19 00:23:39 UTC 2020 up 8 days, 21:34, 0 users, load averages: 1.68, 1.61, 1.55