20150505, 14:12  #1 
May 2015
4_{16} Posts 
[YASQ] Yet Another Stupid Question  Factoring capability ??
Hi guys, as you can see i'm new here.
I discovered this forum through the factoring topic, namely thanks to this thread: http://www.mersenneforum.org/showthread.php?t=12388 It is really impressive that you are able to factor a 260 digit number (http://www.mersenneforum.org/showthr...12388&page=152), but how is that possible ? Is this because the factors are conceptually badly chosen ? This can't be only due to the fact that the calcul is distributed. I guess the different nominations: "GC_6_307", "GC_9_250", "L1286", etc ... are linked to this project http://escatter11.fullerton.edu/nfs/crunching.php But what is the final aim of this project (except to discover factors for fun) ? Can we submit our own number to factorize ? Last but not least, everyone on this topic use msieve, but AFAIK yafu (which i'm using) is faster, right ? Why then ? Thanks for your attention :). 
20150505, 14:52  #2  
Nov 2003
1C40_{16} Posts 
Quote:
Look up e.g. "Quadratic Sieve, Number Field Sieve, Elliptic Curve Factoring Method" Quote:
Quote:
(1) To encourage research into the algorithms being used. (2) To promote newer/faster implementations. (3) For fun. Quote:
You should also not expect that people will actually try your numbers when there are so many existing projects to work on. You will need to tell us why your particular numbers are interesting.... Quote:
my own NFS software for example. And msieve just provides NFS postprocessing. One also needs a siever. 

20150505, 14:54  #3 
"Curtis"
Feb 2005
Riverside, CA
4,493 Posts 
YAFU is a wrapper for the real factoring engines. If the number is small, say under ~100 digits, YAFU calls msieve's Quadratic Sieve (aka MPQS) algorithm. If larger, YAFU manages the steps of the number field sieve (NFS). Yafu will call msieve to do the polynomial selection, then GGNFS to do the sieve step, then msieve again for the processing tasks.
So, it is nonsensical to ask if YAFU is faster than msieve. "badly chosen" also is not relevant nobody chose the factors of these numbers. If a number has a special form (usually but not always a large power plus or minus a small amount, e.g. 3^200+1), a faster version of NFS can be used. No 260digit number has yet been factored without such a special form and the faster "special" NFS. This may be helpful, though it's more a guide for how to do each step than a full explanation of what happens: http://gilchrist.ca/jeff/factoring/n...ers_guide.html Note that YAFU does most or all of these individual steps for you. 
20150505, 15:10  #4 
Jun 2003
7·683 Posts 

20150505, 15:19  #5  
May 2015
100_{2} Posts 
Quote:
These algorithms are great of course but it should take tremendous time to factorize such a big number. So I don't need sarcasm here if you don't know how to use it. Quote:
So it can be a "bad choice" to have a hardly factorizable number. Quote:
I still think that there is a final goal to discovering those factors. But I don't get which one ... I want to be part of it but I look first for answers on this ^^. @VBCurtis thanks for the explaination . However i think you are partly wrong on YAFU it does wrap some engines (GGNFS) but it also has its own improved algorithms (otherwise YAFU wouldn't be more efficient than msieve on ~100 digit numbers ) PS: I warned you that it was "stupid question" Last fiddled with by Twh0re on 20150505 at 15:22 

20150505, 16:27  #6  
Nov 2003
1110001000000_{2} Posts 
Quote:
Quote:
And the numbers being factored were not CONSTRUCTED. They are not amenable to Fermat's Method. Quote:
People are NOT using them to factor "random" numbers. None of the numbers being factored are integers that were chosen at random. Quote:
not important. Quote:


20150505, 16:53  #7  
Nov 2003
7232_{10} Posts 
Quote:
it does NOT take a lot of time. I don't know where you might get this misimpression. Of course it takes a long time even with the best current algorithms. For example, I am currently factoring 11^218 + 3^218. Total sieving time will be about 8400 CPU hours. Is this not a 'lot' by your definition? 

20150505, 17:13  #8  
"Ben"
Feb 2007
3·5·223 Posts 
Quote:
Maybe these are worth a read to the OP: current best GNFS and current best SNFS 

20150505, 18:36  #9 
"Curtis"
Feb 2005
Riverside, CA
4,493 Posts 

20150505, 18:49  #10  
"Curtis"
Feb 2005
Riverside, CA
4493_{10} Posts 
Quote:
OP Mr Silverman does not do sarcasm; if he wishes to berate you, he'll do it directly. Mr Silverman's response about the goals of the big factoring projects are quite accurate; the only one missing from your grasp as his reply is that many people find it fun to learn how to use the notquiteautomatic tools to find factors of large numbers. There is a bit of a feeling of accomplishment to factor an input the size of RSA512, which was the encryption used on PS2 games and TI89 calculator programs; so, some folks enjoy that. His reply to read papers on the actual algos would also clear up your confusion about SNFS vs GNFS. You have more than once expressed disbelief at the size of number we can factor, reflecting a total lack of grasp of the properties of the numbers we are factoring with SNFS. So, some factor on their own for their recreation. Some contribute to the big coordinated projects, who push the software and algorithms so hard that bugs are found, optimizations made, and the set of solvable problems grows as a result. Others of us form small teams to tackle inbetween factorizations of historical interest or other curiosity (such as aliquot sequences), too big to do alone (in weeks rather than months) but too small to improve the state of the art. 

20150505, 18:50  #11 
"Ben"
Feb 2007
3345_{10} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A stupid factoring method  JM Montolio A  Miscellaneous Math  11  20180228 11:29 
Stupid question reloaded  LaurV  Information & Answers  14  20150618 23:37 
There is no such thing as a stupid question?  Uncwilly  Lounge  19  20130307 04:44 
Possibly stupid question about PRP.  Biggles  Prime Sierpinski Project  3  20060207 22:50 
Stupid Question  fropones  Math  2  20030528 00:44 