mersenneforum.org Explaining gnfs to davar55 in words of one sound
 Register FAQ Search Today's Posts Mark Forums Read

2011-01-29, 03:05   #1
davar55

May 2004
New York City

5×7×112 Posts
Explaining gnfs to davar55 in words of one sound

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

2011-01-29, 18:06   #2
davar55

May 2004
New York City

108B16 Posts

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

2011-01-29, 19:37   #3
jasonp
Tribal Bullet

Oct 2004

3·1,181 Posts

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

2011-01-30, 17:34   #4
davar55

May 2004
New York City

5·7·112 Posts

Quote:
 Originally Posted by jasonp 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.
suggesting I haven't read yet. If you provide a link, I'll know
where you think I should start.

 2011-01-30, 18:22 #5 jasonp Tribal Bullet     Oct 2004 3·1,181 Posts 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.
2011-01-31, 03:31   #6
davar55

May 2004
New York City

5·7·112 Posts

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.

2011-01-31, 07:16   #7
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100101100100102 Posts

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

 2011-01-31, 13:02 #8 akruppa     "Nancy" Aug 2002 Alexandria 46438 Posts 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.
2011-01-31, 16:19   #9
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by akruppa 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)

 2011-01-31, 16:52 #10 CRGreathouse     Aug 2006 3·1,993 Posts 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).
 2011-01-31, 17:54 #11 Brian Gladman     May 2008 Worcester, United Kingdom 72×11 Posts And you will have to read four volumes of TAoCP now! Brian

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 Soap Box 80 2017-08-07 00:07 cheesehead Miscellaneous Math 298 2015-04-27 19:13 Mini-Geek Lounge 8 2015-04-10 20:08 davar55 Puzzles 25 2008-06-27 11:46 Uncwilly Puzzles 7 2004-09-15 21:40

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

Mon Dec 6 12:24:23 UTC 2021 up 136 days, 6:53, 0 users, load averages: 1.52, 1.45, 1.38