Explaining gnfs to davar55 in words of one sound

[davar55]

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.

[davar55]

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).

[jasonp]

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.

[davar55]

Originally Posted by jasonp

<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.

[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). If you can't find the others, you're not looking hard enough.

[davar55]

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.

[Batalov]

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.

[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.

[R.D. Silverman]

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)

[CRGreathouse]

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).

[Brian Gladman]

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

Brian