noob poly questions

[R.D. Silverman]

Originally Posted by jasonp

(He meant Murphy's "Polynomial Selection for the Number Field Sieve Integer Factorisation Algorithm")

And instead of 'polynomial style' the more common terminology is 'polynomial degree'.

This sort of thing bothers me. The poster touted his math background
as currently taking calculus. But he hasn't even mastered simple
stuff from high school algebra: i.e. polynomials and polynomial algebra.
He should know what the degree of a polynomial is!
Where does one get the phrase "polynomial style"????
Does he know the difference between 'reducible' and 'irreducible'?
Does he know what the product form of a polynomial is? Does
he know that the constant term is the product of the roots?
etc. etc. etc. Basic high school pre-calculus stuff.

How will such a person understand what the norm (of an element) is, without knowing what conjugate roots of a polynomial are? The explanation
that the norm is the product of all of the conjugates will be a total mystery.

I mean no offense to the OP.

[jrk]

Originally Posted by c10ck3r

The part I am curious on, however, is how the polynomials are generated. Is there a set value of x that is used to generate polynomials, or does this vary? I was unable to find this answered so I thought I should ask for insight. Also, assuming it does involve a real value (x), does the poly multiply out to equal the number?

The polynomial-pair used by NFS does represent (a multiple of) the input number N. If the two generated polynomials are:

f(x) = a_d*x^d + a_{d-1}*x^{d-1} + ... + a_0
g(x) = p*x - m

then the sum

a_d*m^d + a_{d-1}*p*m^{d-1} + ... + a_0*p^d

must be a multiple of N. In fact, with the algorithm used by msieve, the above sum is exactly equal to N.

I've tried to find a lay-man's explanation for the polynomial selection algorithm used, and this is what I have found:

As Jason pointed out, if we make a polynomial by letting p=1 and picking an m near (but larger than) the real root (N/a_d)^(1/d), then we expect a_{d-2} through a_0 to be on the order of m, and a_{d-1} will be on the order of d*a_d*(m - real root). But we also desire (at least) to make a_{d-2} small. We could just pick a bunch of different a_d,m pairs until we find a poly with small a_{d-2} by chance. But Kleinjung's algorithm is much more efficient, and here's what it does:

- choose a_d
- translate N and m, hereafter named N~ and m~ respectively, so that the translated a_d=1 and a_{d-1}=0
- find a suitably small p such that (p, N~) is 1 and that there exists an integer root m~ of N~ modulo p^2 which is suitably near to the real root of N~
- translate the produced polynomials back to the original values of a_d and a_{d-1}

Finding p in the third step is the computationally difficult part, and there's more than one way to do it. Generally, we need to generate many different small factors of p (and their roots) and quickly combine them to determine when the third step is satisfied.

[jasonp]

American secondary education treats integers and polynomials as mutually incompatible things, one has all these x's and the other is...just a number. The fact that integer arithmetic and polynomial arithmetic are very similar, and that you can derive one from the other, is never made clear unless you step back from the rote learning ('this is how you divide polynomials') and recognize the patterns on your own ('hey, this looks like integer division!')

[bdodson]

Originally Posted by jasonp

American secondary education treats integers and polynomials as mutually incompatible things, one has all these x's and the other is...just a number. The fact that integer arithmetic and polynomial arithmetic are very similar, and that you can derive one from the other, is never made clear unless you step back from the rote learning ('this is how you divide polynomials') and recognize the patterns on your own ('hey, this looks like integer division!')

Toss in modular arithmetic (integers, resp. polyn, resp. polyn with mod p
coef) and you've got our undergrad algebra --- and/or intro cryto. Let's
not encourage too much of this "discovering patterns on your own" stuff!

-Bruce

[xilman]

Originally Posted by jasonp

American secondary education treats integers and polynomials as mutually incompatible things, one has all these x's and the other is...just a number. The fact that integer arithmetic and polynomial arithmetic are very similar, and that you can derive one from the other, is never made clear unless you step back from the rote learning ('this is how you divide polynomials') and recognize the patterns on your own ('hey, this looks like integer division!')

The same was true of British secondary education when I was exposed to it. I doubt very much that things have changes.

[Random Poster]

Originally Posted by R.D. Silverman

How will such a person understand what the norm (of an element) is, without knowing what conjugate roots of a polynomial are? The explanation that the norm is the product of all of the conjugates will be a total mystery.

But it's not necessary to know about conjugates to define or understand the norm. Suppose we have a polynomial f(x) of degree d. Every equivalence class of polynomials modulo f(x) has a unique polynomial of degree < d, so take its coefficients to form a vector of length d. Consideration of multiplication of polynomials modulo f(x) leads to the conclusion that each of these vectors is actually a column of a d*d matrix which is completely determined by the vector. Define the norm of a polynomial as the determinant of the corresponding matrix; since the determinant of a matrix product is the product of determinants of the matrices, it follows that the norm of a product of polynomials is the product of the norms of the polynomials. Finally, deduce from the matrix representation that the norm of ax-b is a^d*f(b/a), and you know just about everything about the norm that is relevant to NFS.

[R.D. Silverman]

Originally Posted by Random Poster

But it's not necessary to know about conjugates to define or understand the norm. Suppose we have a polynomial f(x) of degree d. Every equivalence class of polynomials modulo f(x) has a unique polynomial of degree < d, so take its coefficients to form a vector of length d. Consideration of multiplication of polynomials modulo f(x) leads to the conclusion that each of these vectors is actually a column of a d*d matrix which is completely determined by the vector. Define the norm of a polynomial as the determinant of the corresponding matrix; since the determinant of a matrix product is the product of determinants of the matrices, it follows that the norm of a product of polynomials is the product of the norms of the polynomials. Finally, deduce from the matrix representation that the norm of ax-b is a^d*f(b/a), and you know just about everything about the norm that is relevant to NFS.

Do you really see this as a simpler explanation of what a
norm is???? This explanation involves concepts from linear algebra
(determinants) and concepts from modern algebra (equivalence classes)
which are not encountered until well into undergraduate math studies.

OTOH, the concept of conjugates is something that is taught in high
school during the study of polynomial algebra, and the definition of norm
as the product of the conjugates is (at least to me) conceptually simpler.

And someone who does not understand conjugates is very likely not going
to understand determinants and equivalence classes of polynomials.

And I find it much easier to show that norm(a + b alpha) = (-b)^d f(-a/b)
simply by writing the polynomial in product form, applying the definition
of norm as the product of conjugates, then just factoring out b^d...

i.e. f(x) = (x - r1)(x - r2)......(x-rn)

Now, (-b)^d f(-a/b) = (-b)^d (-a/b - r1)(-a/b - r2) ...... (-a/b - rn)

Multiply through by b^d via multiplying each individual linear polynomial
by b, and lo and behold! You get the norm of the element (a + b alpha) from its definition as the product of its conjugates.

Opinions?

[chris2be8]

Originally Posted by jasonp

The lasieve source in GGNFS is indeed a mystery to me, and I've gone through it and understand it around the edges. One of the reasons it's a hard slog is because the lasieve source in GGNFS is the output of a preprocessor that strips out TeX-like comments, and the original source is quite well documented by all accounts.

Does anyone know where the original source is? I managed to find out what parameters it takes, but I still don't know what they all do. The comments might help!

Chris K

[Robert Holmes]

You can find the CWEB-generated documentation in GGNFS's sources:

http://ggnfs.svn.sourceforge.net/vie...f?revision=409

[xilman]

Originally Posted by R.D. Silverman

And I find it much easier to show that norm(a + b alpha) = (-b)^d f(-a/b) simply by writing the polynomial in product form, applying the definition of norm as the product of conjugates, then just factoring out b^d...

i.e. f(x) = (x - r1)(x - r2)......(x-rn)

Now, (-b)^d f(-a/b) = (-b)^d (-a/b - r1)(-a/b - r2) ...... (-a/b - rn)

Multiply through by b^d via multiplying each individual linear polynomial by b, and lo and behold! You get the norm of the element (a + b alpha) from its definition as the product of its conjugates.

Opinions?

I'm with you here.

Bruce's description is clever but, personally, I find it harder to understand.

[Random Poster]

Originally Posted by R.D. Silverman

Do you really see this as a simpler explanation of what a norm is????

I didn't claim it's simpler, just possible; that's how I figured out what norms are when I was trying to understand NFS. I'm not saying that you should explain norms that way, but it is an alternative point of view which may help other people to grasp the concept.