mersenneforum.org > YAFU hi there, and a question
 Register FAQ Search Today's Posts Mark Forums Read

 2020-11-18, 06:01 #1 aqua   Nov 2020 3 Posts hi there, and a question Hi, I recently found this site with a lot of old-school enthusiasts. Glad to great you all! My primary goal was to factor a 512-bit number, but during the process I revealed a whole and interesting mathematical universe :) With different small programs that like optimization, authors that publish their findings and knowledge, constantly improved algorithms etc. Probably a portion of my enthusiasm will spill on the tools too. I'm a system programmer on Windows and used to program in x64 bit asm with all modern extensions. So, yafu worked well on a 256-bit key. With a 384-bit key it starts to food with numbers like : 4752 13239466028743 882405501769571690163767 4524 20577102057791 893319195611906354590837 save 7.244624e-014 -4.8911 4724113.50 9.246223e-009 rroots 2 9522397161563954881537604020 8087755128263 920091041457194254691175 7788 6938120111755 9516 35989004298241 741777587812416893280037 What could it be ? Can it be suppressed, I think the output slows down the calculation. "silent" option in .ini doesn't help
 2020-11-18, 06:28 #2 VBCurtis     "Curtis" Feb 2005 Riverside, CA 22×1,151 Posts Welcome! 256-bit inputs are small, and YAFU will run the quadratic sieve to factor them. This method is faster for inputs below about 100 decimal digits, but the time to factor scales more steeply than the Number Field Sieve (NFS). 384 bits is well above that 100 digits, so YAFU is running NFS. What you see on screen is the output of the first phase of NFS algorithm- polynomial selection. That phase will run for roughly 5% of the total factorization time. Sieving takes 80-85% of the total time, and the linear algebra takes 10-15% at the end. A 384-bit input on a desktop quad-core should take a couple hours to factor. Difficulty doubles every 5 decimal digits or so, so a 512-bit number will take 5-10 days (depending on the speed of your hardware).
 2020-11-18, 06:48 #3 LaurV Romulan Interpreter     Jun 2011 Thailand 3×17×179 Posts Welcome to the fry. You are on track, don't worry about the numbers you see on screen. As I remember, they can be disabled, yes, but it is a bit tricky. Please have a look in yafu readme file. Yafu uses different algorithms to factor numbers, according with the number size. It starts "small", with trial factoring and Pollard algorithms, and if your number "survives", it moves "higher", to ecm, siqs, (s/g)nfs. For "higher" part, it used third party tools, external or incorporated inside, and messages you see may come from these "external" tools (in case, poly select, msieve). The reason you don't see them for a 256-bit number (about 70 something digits) is the fact that this number is always factored by ecm or siqs, it never reaches nfs stage. The situation changes for composites over (about) 106 digits. Run a "tune" to your system to see where exactly is the cutting point (it is system-dependent). Sys-programmer here too, btw.
2020-11-18, 12:53   #4
Dr Sardonicus

Feb 2017
Nowhere

2·33·7·11 Posts

Quote:
 Originally Posted by VBCurtis Welcome! 256-bit inputs are small, and YAFU will run the quadratic sieve to factor them. This method is faster for inputs below about 100 decimal digits, but the time to factor scales more steeply than the Number Field Sieve (NFS). 384 bits is well above that 100 digits, so YAFU is running NFS. What you see on screen is the output of the first phase of NFS algorithm- polynomial selection. That phase will run for roughly 5% of the total factorization time. Sieving takes 80-85% of the total time, and the linear algebra takes 10-15% at the end. A 384-bit input on a desktop quad-core should take a couple hours to factor. Difficulty doubles every 5 decimal digits or so, so a 512-bit number will take 5-10 days (depending on the speed of your hardware).
Boom!

The performance info above should be pasted into any FAQ or README file that's supposed to tell would-be users what to expect.

2020-11-18, 14:27   #5
bsquared

"Ben"
Feb 2007

25·3·5·7 Posts

Quote:
 Originally Posted by Dr Sardonicus Boom! The performance info above should be pasted into any FAQ or README file that's supposed to tell would-be users what to expect.
Lots of stuff probably should have been put into a FAQ or README. Fortunately for me and my lazy documentation efforts, this entire subject is so niche that for the most part people either already know what they're doing or are focused enough to learn more and figure it out themselves. At least that's what I tell myself

As LaurV mentioned, the endless lines of numbers come from 3rd party software (msieve) and have annoyed me before too... mostly when I want to see something output to the screen from earlier in the day but which has long ago been shoved out the back of the terminal's screen buffer. However from a performance standpoint I believe they are Mostly Harmless.