20120116, 10:58  #1 
Jan 2012
7_{16} Posts 
Factoring a C155 with Yafu
Hello,
I'm factoring a C155 just for fun and to get a feeling on how much time is needed to do such factorisations. I'm using the nfs() function from yafu. It's currently in the sieving stage. Yafu predicted it requires somewhere around 27 million relations. I'm now around 30 million relations so I thought I could end the sieving and proceed to the next stage. However, when I run yafu it starts with singleton removal (several times) and finally ends with the message: max relations containing the same ideal: 0 After that message it restarts sieving. Am I doing something wrong or is the amount of relations still too low? I can't find a good reference on the several stages of factoring and what to expect from yafu. Can someone shed some light on this? Thanks, Ivar 
20120116, 12:58  #2 
Oct 2004
Austria
2·17·73 Posts 
The estimation of how many relations are needed is too low in many cases, so no reason to worry. It is normal, that yafu (and also other programs, like the pearl script) start with singleton removal etc. ("filtering stage") when it thinks that it might have got enough relations  and then continues sieving when it turns out that the amount of relations is not yet enough.
IIRC, you are more than halfway through sieving. The next steps after filtering (when having enough relations) are * linear algebra (needs very much RAM, see below), might take ~34 days on an i7 * sqare root. After a few sqrtattempts you should get the factors. How much RAM does your computer have? For numbers of this size, 2 GB might just be not enough on 32 bit windows systems, while 2 GB on 64bit systems should barely suffice  at least on linux systems. This behaviour seems to come from how windows and linux (re)allocate memory when dealing with huge amount of data. BTW: The last line before "max relations containing the same ideal: 0" says something like "reduce to xx relations and yy ideals". As long as xx and/or yy are two or threedigit numbers, you still need quite some amount of sieving. When xx and yy grow to 5 and 6digit numbers, you are getting close... 
20120116, 13:01  #3 
Sep 2009
2×3×163 Posts 
Are you sieving with lpba & lpbr = 28, or lpba & lpbr = 29 ?
~27M relations would be a target indication for a 28bit large primes task... but if filtering fails that spectacularly, sieving may actually be using a 29bit large primes task, and therefore require ~60M raw relations. For a C155 by GNFS, using 29bit large primes is better than using 28bit LPs, AFAICT: that's what we used on RSALS for the 512bit RSA signing keys (154/155digit semiprimes). 
20120116, 13:53  #4 
Jan 2012
111_{2} Posts 
@Andi: Thanks for your reply. I'm on a xeon 64 bit system with 6 GB of ram. That should do the trick :) I'm glad it's no error from my side. I compiled the gnfs executables myself and thought I made a error there. I'll let my computer sieve a bit more.
@debrouxl: I really have no idea. I got the modulus from an RSA key I created. I guess that means strong primes. I'm using standard 64 bit yafu with the latest gnfs compiled with the core2 optimizations. 
20120116, 14:23  #5 
"Ben"
Feb 2007
2×11×163 Posts 
ivar,
debrouxl is referring to a details inside of a file called nfs.job that was created by yafu as part of this factorization. For C155's, yafu will pick 29 bit large primes, so it will need to gather 5560M relations before the job will finish. The fact that it is attempting filtering so early is annoying (and something that a future version of yafu will try to do better), but harmless. It will continue sieving/filtering until the number is factored. 
20120116, 14:48  #6 
Jan 2012
7 Posts 
Thank you. I'm using lpba & lpbr = 29.
But if it needs 5560M relations I think I still need like 1 or 2 weeks of sieving... Ah well, let's keep the cores busy. 
20120116, 14:59  #7  
"Ben"
Feb 2007
2×11×163 Posts 
Quote:
Quote:


20120116, 15:28  #8  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
11146_{10} Posts 
Quote:
Paul 

20120116, 15:52  #9  
"Ben"
Feb 2007
E02_{16} Posts 
Quote:
 cheers! 

20120116, 16:15  #10  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2×3,169 Posts 
Quote:
Perhaps I should just buy bigger boots. 

20120116, 16:46  #11 
"Ed Hall"
Dec 2009
Adirondack Mtns
4,201 Posts 
Have you tried a solid state boot drive? Actually, every computer I'm running currently (none with SSDs), takes far longer than the ones thirteen years ago...

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
RSA Key Factoring using Yafu  rxz7545  YAFU  4  20161219 07:54 
Factoring 1024bit number using Yafu  Anyone  YAFU  30  20150901 13:25 
Yafu crash after factoring this number  al3ndaleeb  YAFU  3  20150530 19:54 
Team sieve #39: c155 from 3408:i1311  RichD  Aliquot Sequences  46  20130827 17:26 
Good enough poly for c155?  theuser  Msieve  4  20121007 09:00 