mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2018-02-03, 14:57   #1
jibanes
 
Feb 2018

19 Posts
Exclamation 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.
jibanes is offline   Reply With Quote
Old 2018-02-03, 16:43   #2
swellman
 
swellman's Avatar
 
Jun 2012

22·23·31 Posts
Default

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?
swellman is online now   Reply With Quote
Old 2018-02-03, 16:48   #3
chris2be8
 
chris2be8's Avatar
 
Sep 2009

2·33·5·7 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2018-02-03, 22:15   #4
jibanes
 
Feb 2018

19 Posts
Default

Should I change the other variables? (B1pm1, pretest_ratio, etc...)?
jibanes is offline   Reply With Quote
Old 2018-02-04, 03:08   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

CDA16 Posts
Default

Quote:
Originally Posted by jibanes View Post
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.
bsquared is offline   Reply With Quote
Old 2018-02-04, 15:07   #6
jibanes
 
Feb 2018

19 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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?
jibanes is offline   Reply With Quote
Old 2018-02-04, 16:53   #7
chris2be8
 
chris2be8's Avatar
 
Sep 2009

2×33×5×7 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2018-02-04, 17:48   #8
jibanes
 
Feb 2018

19 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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
jibanes is offline   Reply With Quote
Old 2018-02-05, 01:33   #9
jibanes
 
Feb 2018

1910 Posts
Default

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.
jibanes is offline   Reply With Quote
Old 2018-02-05, 01:57   #10
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

103248 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2018-02-05, 03:27   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

31×191 Posts
Default

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

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 2016-12-25 21:44
Help to install and factor large number craneduitre Msieve 23 2016-07-10 08:13
Yafu crash after factoring this number al3ndaleeb YAFU 3 2015-05-30 19:54
Large small factor Zeta-Flux Factoring 96 2007-05-14 16:59
How large a factor can P-1 testing find ? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.