mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2011-01-29, 03:05   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

3×1,409 Posts
Default Explaining gnfs to davar55 in words of one sound

Quote:
Originally Posted by davar55 View Post
If by non-linear rational polynomials you mean quadratic and higher
degree polynomials with arbitrary rational coefficients, what's the
problem with GGNFS that makes this not-yet-implemented?

This is just a general intro question.
Just trying to work through this important thread.
davar55 is offline   Reply With Quote
Old 2011-01-29, 18:06   #2
davar55
 
davar55's Avatar
 
May 2004
New York City

3×1,409 Posts
Default

Quote:
Originally Posted by xilman View Post
It's easy enough to find two quadratics --- Peter Montgomery showed how to do that about 15 years ago. The problem is that two quadratics aren't actually of much use in most cases.

As you say, finding pairs (or, multiples in general) of non-linear polynomials with small coefficients and a common root is still an interesting but unsolved problem.
How is PM's method related to aurefillian factoring?
Is there a project for the cases where two quadratics ARE useful?

This is obviously related to x^2-n^2 = (x+n)*(x-n).
davar55 is offline   Reply With Quote
Old 2011-01-29, 19:37   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

67048 Posts
Default

Quote:
Originally Posted by davar55 View Post
This is obviously related to x^2-n^2 = (x+n)*(x-n).
<sigh>

NFS requires that the polynomials be irreducible; if you could find polynomials with a common root that could be factored, just substitute the common root for x and recover the factors directly.

The only thing that's obvious is that you haven't even read the wikipedia page closely, or any of the references that it cites.
jasonp is offline   Reply With Quote
Old 2011-01-30, 17:34   #4
davar55
 
davar55's Avatar
 
May 2004
New York City

422710 Posts
Default

Quote:
Originally Posted by jasonp View Post
<sigh>

NFS requires that the polynomials be irreducible; if you could find polynomials with a common root that could be factored, just substitute the common root for x and recover the factors directly.

The only thing that's obvious is that you haven't even read the wikipedia page closely, or any of the references that it cites.
Perhaps I don't know exactly which wikipedia page you're
suggesting I haven't read yet. If you provide a link, I'll know
where you think I should start.
davar55 is offline   Reply With Quote
Old 2011-01-30, 18:22   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

22×881 Posts
Default

Forget wikipedia. Start here. Come back when you've read the first five or six references (I'll give you a pass on the first one, since it's a fairly expensive book). If you can't find the others, you're not looking hard enough.
jasonp is offline   Reply With Quote
Old 2011-01-31, 03:31   #6
davar55
 
davar55's Avatar
 
May 2004
New York City

108316 Posts
Default

Quote:
Forget wikipedia. Start here. Come back when you've read the first five or six references (I'll give you a pass on the first one, since it's a fairly expensive book). If you can't find the others, you're not looking hard enough.
Thanks. That's a lot to look into. But I won't ignore wikipedia too.

I have to read up on gnfs and snfs and others.
My calculator only does TF and some PRP.
davar55 is offline   Reply With Quote
Old 2011-01-31, 07:16   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

22×3×5×151 Posts
Default

Quote:
Originally Posted by jasonp View Post
Forget wikipedia. Start here. Come back when you've read the first five or six references (I'll give you a pass on the first one, since it's a fairly expensive book)...
C&P is not very expensive. Compared to any (organic or bio-) chemistry textbooks, it isn't. Really.
Batalov is offline   Reply With Quote
Old 2011-01-31, 13:02   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

Considering the amount of content and the quality of the writing, it's a bargain. It covers so much of what people on Mersenneforum indulge in that it's the closest thing to required reading that I can imagine for this forum.
akruppa is offline   Reply With Quote
Old 2011-01-31, 16:19   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

3×13×191 Posts
Default

Quote:
Originally Posted by akruppa View Post
Considering the amount of content and the quality of the writing, it's a bargain. It covers so much of what people on Mersenneforum indulge in that it's the closest thing to required reading that I can imagine for this forum.
The other required reading should be the CS bible: Knuth (especially
volume 2)
R.D. Silverman is offline   Reply With Quote
Old 2011-01-31, 16:52   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·3·977 Posts
Default

I do very much recommend C&P. TAoCP is great, too -- but if you start there it'll be a year or two before you get to the actual NFS reading (assuming you work your way through three volumes then move to C&P).
CRGreathouse is offline   Reply With Quote
Old 2011-01-31, 17:54   #11
Brian Gladman
 
Brian Gladman's Avatar
 
May 2008
Worcester, United Kingdom

523 Posts
Default

And you will have to read four volumes of TAoCP now!

Brian
Brian Gladman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Seven words averted Stargate38 Soap Box 80 2017-08-07 00:07
davar55's cosmo-autohagiography: Worth its weight in Dunning-Kruggerands cheesehead Miscellaneous Math 298 2015-04-27 19:13
words Mini-Geek Lounge 8 2015-04-10 20:08
Prime Words davar55 Puzzles 25 2008-06-27 11:46
A problem of words. Uncwilly Puzzles 7 2004-09-15 21:40

All times are UTC. The time now is 06:24.

Fri Jul 10 06:24:46 UTC 2020 up 107 days, 3:57, 0 users, load averages: 2.01, 1.82, 1.64

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.