mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > NFS@Home

Reply
 
Thread Tools
Old 2015-05-05, 14:12   #1
Twh0re
 
May 2015

416 Posts
Default [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 :).
Twh0re is offline   Reply With Quote
Old 2015-05-05, 14:52   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1C4016 Posts
Default

Quote:
Originally Posted by Twh0re View Post
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 ?
Repeat after me: Google is my friend.

Look up e.g. "Quadratic Sieve, Number Field Sieve, Elliptic Curve Factoring Method"

Quote:
Is this because the factors are conceptually badly chosen ? This can't be only due to the fact that the calcul is distributed.
Huh? Factors are not "chosen". Where did you get this idea?? And your second sentence is gibberish.

Quote:
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) ?
There is no final aim. The goals are:

(1) To encourage research into the algorithms being used.
(2) To promote newer/faster implementations.
(3) For fun.

Quote:

Can we submit our own number to factorize ?
Well, yes. You can submit numbers. But people will want to know the source of the numbers.
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:
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 :).
I don't understand what you are asking. People certainly do not ALL use YAFU or msieve. I use
my own NFS software for example. And msieve just provides NFS post-processing. One also
needs a siever.
R.D. Silverman is offline   Reply With Quote
Old 2015-05-05, 14:54   #3
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

4,493 Posts
Default

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 260-digit 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.
VBCurtis is offline   Reply With Quote
Old 2015-05-05, 15:10   #4
axn
 
axn's Avatar
 
Jun 2003

7·683 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
If the number is small, say under ~100 digits, YAFU calls msieve's Quadratic Sieve (aka MPQS) algorithm.
Minor correction. YAFU has its own SIQS implementation (which uses msieve's matrix solver), so for QS-accessible numbers, YAFU is faster than msieve.
axn is online now   Reply With Quote
Old 2015-05-05, 15:19   #5
Twh0re
 
May 2015

1002 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Repeat after me: Google is my friend.

Look up e.g. "Quadratic Sieve, Number Field Sieve, Elliptic Curve Factoring Method"

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:
Originally Posted by R.D. Silverman View Post
Huh? Factors are not "chosen". Where did you get this idea?? And your second sentence is gibberish.
Not really, juste take a perfect square for example or two factors too close. These are easily recoverable factors.
So it can be a "bad choice" to have a hardly factorizable number.


Quote:
Originally Posted by R.D. Silverman View Post
There is no final aim. The goals are:
(1) To encourage research into the algorithms being used.
(2) To promote newer/faster implementations.
(3) For fun.
Where do you improve algorithm when you are simply using them to factorize "random" numbers .... ?
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 2015-05-05 at 15:22
Twh0re is offline   Reply With Quote
Old 2015-05-05, 16:27   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11100010000002 Posts
Default

Quote:
Originally Posted by Twh0re View Post

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.
Typical. I give a useful, friendly response, and the OP replies with stupidity.

Quote:
Not really, juste take a perfect square for example or two factors too close. These are easily recoverable factors.
So it can be a "bad choice" to have a hardly factorizable number.
The phrase "hardly factorizable number" is gibberish. It isn't English.

And the numbers being factored were not CONSTRUCTED. They are not amenable
to Fermat's Method.



Quote:
Where do you improve algorithm when you are simply using them to factorize "random" numbers .... ?
You asked about the goals of the project(s). One goal is to improve algorithms.
People are NOT using them to factor "random" numbers. None of the numbers being
factored are integers that were chosen at random.

Quote:
I still think that there is a final goal to discovering those factors. But I don't get which one ...
This belief is incorrect. The (value of) factors themselves are really
not important.

Quote:
I want to be part of it but I look first for answers on this ^^.
Answers on WHAT? What is the antecedent of the word "this" in your last sentence?
R.D. Silverman is offline   Reply With Quote
Old 2015-05-05, 16:53   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

723210 Posts
Default

Quote:
Originally Posted by Twh0re View Post

These algorithms are great of course but it should take tremendous time to factorize such a big number.
I'm not sure that I understand this comment. The wording makes it seems that you believe that
it does NOT take a lot of time.

I don't know where you might get this mis-impression. 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?
R.D. Silverman is offline   Reply With Quote
Old 2015-05-05, 17:13   #8
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3·5·223 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I'm not sure that I understand this comment. The wording makes it seems that you believe that
it does NOT take a lot of time.
I interpreted that statement as him being surprised the algorithms are so fast. What he appears to be missing is a good understanding of the difference between the special and general NFS.

Maybe these are worth a read to the OP: current best GNFS and current best SNFS
bsquared is offline   Reply With Quote
Old 2015-05-05, 18:36   #9
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

4,493 Posts
Default

Quote:
Originally Posted by axn View Post
Minor correction. YAFU has its own SIQS implementation (which uses msieve's matrix solver), so for QS-accessible numbers, YAFU is faster than msieve.
Ooh, good to know! I'll play with 90-96 digit QS candidates and see how much faster. Thanks!
VBCurtis is offline   Reply With Quote
Old 2015-05-05, 18:49   #10
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

449310 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Answers on WHAT? What is the antecedent of the word "this" in your last sentence?
The carets are meant to be pointing up at the previous line. The context of the sentence supports that- he wishes to learn what the goal of finding factors is, notwithstanding your literal, precise, and (honestly) best explanation already provided.

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 not-quite-automatic tools to find factors of large numbers. There is a bit of a feeling of accomplishment to factor an input the size of RSA-512, which was the encryption used on PS2 games and TI-89 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 in-between 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.
VBCurtis is offline   Reply With Quote
Old 2015-05-05, 18:50   #11
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

334510 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
Ooh, good to know! I'll play with 90-96 digit QS candidates and see how much faster. Thanks!
In that range I would expect 1.5x to 2x faster. Assuming you are using the SSE4.1 enhanced YAFU versions.
bsquared is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A stupid factoring method JM Montolio A Miscellaneous Math 11 2018-02-28 11:29
Stupid question reloaded LaurV Information & Answers 14 2015-06-18 23:37
There is -no- such thing as a stupid question? Uncwilly Lounge 19 2013-03-07 04:44
Possibly stupid question about PRP. Biggles Prime Sierpinski Project 3 2006-02-07 22:50
Stupid Question fropones Math 2 2003-05-28 00:44

All times are UTC. The time now is 10:54.

Tue Dec 1 10:54:28 UTC 2020 up 82 days, 8:05, 1 user, load averages: 1.35, 1.60, 1.63

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.