mersenneforum.org [YASQ] Yet Another Stupid Question - Factoring capability ??
 Register FAQ Search Today's Posts Mark Forums Read

 2015-05-05, 14:12 #1 Twh0re   May 2015 48 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 :).
2015-05-05, 14:52   #2
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 Originally Posted by Twh0re 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.
(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.

 2015-05-05, 14:54 #3 VBCurtis     "Curtis" Feb 2005 Riverside, CA 35·19 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 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.
2015-05-05, 15:10   #4
axn

Jun 2003

484410 Posts

Quote:
 Originally Posted by VBCurtis 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.

2015-05-05, 15:19   #5
Twh0re

May 2015

22 Posts

Quote:
 Originally Posted by R.D. Silverman 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 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 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

2015-05-05, 16:27   #6
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by Twh0re 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?

2015-05-05, 16:53   #7
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by Twh0re 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?

2015-05-05, 17:13   #8
bsquared

"Ben"
Feb 2007

3,361 Posts

Quote:
 Originally Posted by R.D. Silverman 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

2015-05-05, 18:36   #9
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

35×19 Posts

Quote:
 Originally Posted by axn 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!

2015-05-05, 18:49   #10
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

35·19 Posts

Quote:
 Originally Posted by R.D. Silverman 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.

2015-05-05, 18:50   #11
bsquared

"Ben"
Feb 2007

3,361 Posts

Quote:
 Originally Posted by VBCurtis 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post JM Montolio A Miscellaneous Math 11 2018-02-28 11:29 LaurV Information & Answers 14 2015-06-18 23:37 Uncwilly Lounge 19 2013-03-07 04:44 Biggles Prime Sierpinski Project 3 2006-02-07 22:50 fropones Math 2 2003-05-28 00:44

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

Fri Jan 22 10:53:54 UTC 2021 up 50 days, 7:05, 0 users, load averages: 1.77, 1.74, 1.76