mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2012-01-16, 10:58   #1
ivar
 
Jan 2012

716 Posts
Default 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
ivar is offline   Reply With Quote
Old 2012-01-16, 12:58   #2
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2·17·73 Posts
Default

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 ~3-4 days on an i7
* sqare root. After a few sqrt-attempts 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 64-bit 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 three-digit numbers, you still need quite some amount of sieving. When xx and yy grow to 5- and 6-digit numbers, you are getting close...
Andi47 is offline   Reply With Quote
Old 2012-01-16, 13:01   #3
debrouxl
 
debrouxl's Avatar
 
Sep 2009

2×3×163 Posts
Default

Are you sieving with lpba & lpbr = 28, or lpba & lpbr = 29 ?

~27M relations would be a target indication for a 28-bit large primes task... but if filtering fails that spectacularly, sieving may actually be using a 29-bit large primes task, and therefore require ~60M raw relations.
For a C155 by GNFS, using 29-bit large primes is better than using 28-bit LPs, AFAICT: that's what we used on RSALS for the 512-bit RSA signing keys (154/155-digit semi-primes).
debrouxl is offline   Reply With Quote
Old 2012-01-16, 13:53   #4
ivar
 
Jan 2012

1112 Posts
Default

@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.
ivar is offline   Reply With Quote
Old 2012-01-16, 14:23   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×11×163 Posts
Default

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 55-60M 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.
bsquared is offline   Reply With Quote
Old 2012-01-16, 14:48   #6
ivar
 
Jan 2012

7 Posts
Default

Thank you. I'm using lpba & lpbr = 29.

But if it needs 55-60M relations I think I still need like 1 or 2 weeks of sieving... Ah well, let's keep the cores busy.
ivar is offline   Reply With Quote
Old 2012-01-16, 14:59   #7
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×11×163 Posts
Default

Quote:
Originally Posted by ivar View Post
Hello,

I'm factoring a C155 just for fun and to get a feeling on how much time is needed to do such factorisations.

Quote:
Originally Posted by ivar View Post
I still need like 1 or 2 weeks of sieving... Ah well, let's keep the cores busy.
So... mission accomplished! 512 bit RSA keys nowadays are routine, by still by no means easy. Especially on one PC. To put it in perspective, what you are doing now took 300 computers nearly a third of a year to do in 1999.
bsquared is offline   Reply With Quote
Old 2012-01-16, 15:28   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

1114610 Posts
Default

Quote:
Originally Posted by bsquared View Post
So... mission accomplished! 512 bit RSA keys nowadays are routine, by still by no means easy. Especially on one PC. To put it in perspective, what you are doing now took 300 computers nearly a third of a year to do in 1999.
Ah, nostalgia. Note that several of the people mentioned there are active contributors to Mersenneforum and several others are still active in the factorization arena.

Paul
xilman is offline   Reply With Quote
Old 2012-01-16, 15:52   #9
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

E0216 Posts
Default

Quote:
Originally Posted by xilman View Post
Note that several of the people mentioned there are active contributors to Mersenneforum ...
Paul
I've benefited greatly from that fact - may you continue to do so for years to come . I got started in this game in about '07/'08, IIRC, so I'm still a noob by those standards.

- cheers!
bsquared is offline   Reply With Quote
Old 2012-01-16, 16:15   #10
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×3,169 Posts
Default

Quote:
Originally Posted by bsquared View Post
To put it in perspective, what you are doing now took 300 computers nearly a third of a year to do in 1999.
And it bothers me that it still takes the same amount of time as it did thirteen years ago to boot a new computer.

Perhaps I should just buy bigger boots.
retina is offline   Reply With Quote
Old 2012-01-16, 16:46   #11
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

4,201 Posts
Default

Quote:
Originally Posted by retina View Post
And it bothers me that it still takes the same amount of time as it did thirteen years ago to boot a new computer.

Perhaps I should just buy bigger boots.
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...
EdH is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
RSA Key Factoring using Yafu rxz7545 YAFU 4 2016-12-19 07:54
Factoring 1024-bit number using Yafu Anyone YAFU 30 2015-09-01 13:25
Yafu crash after factoring this number al3ndaleeb YAFU 3 2015-05-30 19:54
Team sieve #39: c155 from 3408:i1311 RichD Aliquot Sequences 46 2013-08-27 17:26
Good enough poly for c155? theuser Msieve 4 2012-10-07 09:00

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


Fri Jan 28 00:30:48 UTC 2022 up 188 days, 18:59, 3 users, load averages: 1.28, 1.27, 1.32

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”