mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2020-11-18, 06:01   #1
aqua
 
Nov 2020

310 Posts
Default 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
aqua is offline   Reply With Quote
Old 2020-11-18, 06:28   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2·2,239 Posts
Default

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).
VBCurtis is online now   Reply With Quote
Old 2020-11-18, 06:48   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×7×11×29 Posts
Default

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.
LaurV is offline   Reply With Quote
Old 2020-11-18, 12:53   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×32×211 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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.
Dr Sardonicus is online now   Reply With Quote
Old 2020-11-18, 14:27   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13·257 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
bsquared is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 01:04.

Fri Nov 27 01:04:27 UTC 2020 up 77 days, 22:15, 3 users, load averages: 1.59, 1.50, 1.43

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.