20180203, 14:57  #1 
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=..\ggnfsbin\Win32\ ggnfs_dir=../ggnfsbin/ %ecm_path=..\gmpecm\bin\x64\Release\ecm.exe %ecm_path=../ecm/current/ecm tune_info= Intel(R) Xeon(R) CPU E54650 0 @ 2.70GHz,LINUX64,1.73786e05,0.200412,0.400046,0.0987873,98.8355,2699.98 I'm using an Intel Core i76700HQ CPU @ 2.60Ghz (4 cores, 8 vcores) with 16GB of ram. My questions: Do I need to provide a ggnfsbin binary? Do I need to change the pretest_ratio? Do I need to change any other setting? I am just running yafux64.ivybridge.exe with the number as an argument, do I need to encapsulate this in factor()? The number is ~500 bits long. 
20180203, 16:43  #2 
Jun 2012
2976_{10} 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? 
20180203, 16:48  #3 
Sep 2009
2,027 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 
20180203, 22:15  #4 
Feb 2018
19 Posts 
Should I change the other variables? (B1pm1, pretest_ratio, etc...)?

20180204, 03:08  #5 
"Ben"
Feb 2007
2^{2}×23×37 Posts 

20180204, 15:07  #6  
Feb 2018
19 Posts 
Quote:


20180204, 16:53  #7 
Sep 2009
2,027 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 
20180204, 17:48  #8  
Feb 2018
23_{8} Posts 
Quote:
My test run was using a single core (out of 4 cores/8 vcores) running windows (Intel Core i76700HQ CPU @ 2.60Ghz), I'm doing another test on linux (Intel(R) Core(TM) i53470 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 20180204 at 17:52 

20180205, 01:33  #9 
Feb 2018
19 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 GMPECM work  >  on a single machine. It is copyright, 20112016, 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 GMPECM... > 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 GMPECM 6.4.4 [configured with GMP 6.0.0, enableasmredc] [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. 
20180205, 01:57  #10 
"Curtis"
Feb 2005
Riverside, CA
2^{2}×7×13^{2} 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 45digit 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 50digit 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. 
20180205, 03:27  #11 
Aug 2006
13541_{8} Posts 
Since we know the factorization of RSA100, we know that (without BrentSuyama) 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 BS, you could find it with smaller parameters... if you're lucky. But it will almost take longer than NFS (as VBCurtis mentioned) or SIQS.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Inefficient behaviour in yafu when doing large NFS with lots of threads  2147483647  YAFU  3  20161225 21:44 
Help to install and factor large number  craneduitre  Msieve  23  20160710 08:13 
Yafu crash after factoring this number  al3ndaleeb  YAFU  3  20150530 19:54 
Large small factor  ZetaFlux  Factoring  96  20070514 16:59 
How large a factor can P1 testing find ?  dsouza123  Software  3  20031211 00:48 