noob poly questions

[bsquared]

Originally Posted by R.D. Silverman

Obviously, we disagree. I especially disagree about the "forcefeed"
part. We are not forcing anyone. They come to us.

You're right, bad wording on my part - there was no forcefeeding. And I realize they come to us. All I'm saying is that they are not necessarily coming to us fully committed to learning the details of the NFS. As I see it, asking a question doesn't automatically make them a student, it makes them a *potential* student. To get them to become students might require a bit of marketing (coaching, whatever you want to call it).

[R.D. Silverman]

Originally Posted by bsquared

<snip>
As I see it, asking a question doesn't automatically make them a student, it makes them a *potential* student. To get them to become students might require a bit of marketing (coaching, whatever you want to call it).

OK. I agree. But clearly I am not the one to try to do the marketing;
I don't see it as part of my job description.

[bsquared]

Originally Posted by R.D. Silverman

OK. I agree. But clearly I am not the one to try to do the marketing;
I don't see it as part of my job description.

Then we are, as they say, in violent agreement.

cheers!

[R.D. Silverman]

Originally Posted by jasonp

How do you teach matlab to people who have only ever used a computer for email? I found out the hard way: you can't.

So do you agree with me that we can't teach how NFS works to people
without a strong math background? And that one can't learn how it works
just from the code?

BTW, have you ever looked at the GGNFS siever source? I assume so.
To say that it is very dense code and lacking in comments is an understatement.

[c10ck3r]

At the risk of prolonging the ire of Sir Silverman, I would like to ask my own form of the OP's question. There are a nearly infinite number of polynomials for any given number to be factored (lines 139-147 of http://msieve.svn.sourceforge.net/vi...77&view=markup) and they each have differing efficiencies. Polynomials can be selected based on Murphy's E score, or an alpha value. Thus far, I believe I am correct. The polynomial style I am viewing in the same source is a quartic equation (one having a degree of 4). 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? I'll start with these 2 questions and move on once I'm under the impression that I have a grasp on it.
Postscript: Full disclosure should state that I am a senior in a public high school currently in my 13th week of Honors Calculus 1 for credit at college level. So yes, I am literally incapable of having anywhere near RDS's experience. *bows to the masters*

[R.D. Silverman]

Originally Posted by c10ck3r

At the risk of prolonging the ire of Sir Silverman, I would like to ask my own form of the OP's question. There are a nearly infinite number of polynomials for any given number to be factored (lines 139-147 of http://msieve.svn.sourceforge.net/vi...77&view=markup)

??? I don't understand where "almost infinite" comes from. One expects
that there will be at most about N usable polynomials.

Given a polynomial of degree d as : sum a_i x^i ,

the set of all usable a_i along with a possible root M mod N is definitely finite.

We would never take any a_i for which abs(a_i) > N. Given that typically a_i ~ N^(1/(d+2)) and M ~ N^(1/(d+2)), the number of different polynomials is about N^((d+2)/(d+2)) ~~ N

[there are d+1 coefficients whose size is bounded by about N^(1/(d+2)),
which along with M gives d+2 parameter choices]

Please clarify. We want the a_i to be SMALL and there is a limited
supply of such.

and they each have differing efficiencies. Polynomials can be selected based on Murphy's E score, or an alpha value. Thus far, I believe I am correct. The polynomial style I am viewing in the same source is a quartic equation (one having a degree of 4).

I would expect many of the possible polynomials to have the same efficiency.
[or so nearly the same that the difference is lost in the noise].

However, I just don't understand what you mean by "polynomial style".
Also what source do you refer to (i.e. "viewing in the same source")???

Please clarify.

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.

An explanation of the algorithm would take many pages here. I suggest
reading Brian Murphy's paper.

Also, assuming it does involve a real value (x), does the poly multiply out to equal the number?

I don't know what you mean by "multiply out". The polynomial f(x) is
such that it has a known integral root mod N, i.e. there is a known
value of M (which gets computed) such that f(M) = 0 mod N.

The polynomial coefficients are selected with a number of different properties
in mind. We want lots of small ideals in the factor base. We want lots of
projective roots. We want the norms of ideals of index 1, i.e. the numbers
of the form norm(a + b alpha) where alpha is an irrational root of f(x)
[not a root mod N !!!] to be quite small. We want the probability that
norm(a + b alpha) factors over the factor base to be as large as possible
as a and b range over the lattice..... etc. etc. [note to purists: this isn't
quite correct, but it conveys the idea; it is also a good idea to have a large
variance along with a large mean probability because a large variance means
a fatter tail; relations are found in the tail]. We'd like the polynomial to
have many real roots. Shall I go on?? Read Murphy's paper.

Is this what you are looking for?

To really understand this, one needs to learn some algebraic number theory
[what ideals are, what norms in a number field are, what a ring homomorphism is, Dickman's function for the probabilities, projective roots,
etc. etc. ] Dickman's function is well explained in Knuth Vol II and its
evaluation is the only thing herein that really requires calculus. The number
theory is a separate subject from Calculus

[jasonp]

Originally Posted by R.D. Silverman

So do you agree with me that we can't teach how NFS works to people
without a strong math background? And that one can't learn how it works
just from the code?

BTW, have you ever looked at the GGNFS siever source? I assume so.
To say that it is very dense code and lacking in comments is an understatement.

<sigh>

Bob, I don't have a strong math background. Not strong as in 'mathematics degree' strong. Despite what dozens of commenters on the NYT article you pointed to have said (thanks for that, BTW), the kind of mathematics that makes NFS tick is never even hinted at in an engineering curriculum, even at the PhD level, and I haven't gone to great pains to fix that even years after starting an NFS implementation.

In fact I learned a great deal about the underlying mathematics by carefully auditing the code of others, including you, combined with a lot of background reading that sometimes helped and sometimes did not. Code is another tool to illustrate ideas for me, and one I understand a lot better than abstract algebra to be sure.

It would be very difficult to understand how block Lanczos works by auditing my own code, but Peter's 1995 paper combined with the BL code in GGNFS is exactly how I figured things out, and I wouldn't have managed without Chris Monico's code. To say that it's impossible is overstating things. The polynomial selection code in GGNFS, even with no comments, was the only resource I used to figure out the algorithm, because the low-level details of how it works are not in the literature anywhere. 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.

It's clear to me that you 'think in math', just as it's clear to me that I 'think in digital'. I believe the only hard-and-fast prerequisite to understanding NFS (and doing many other things) is to be persistent as hell.

[jasonp]

c10ck3r:

I kind of regret writing that the supply of polynomials was 'effectively infinite' when what I meant was that the supply was larger than anyone can hope to completely search, for N that are large enough to contemplate using NFS to factor.

The basic method of constructing these kinds of polynomials is analogous to expressing a number in decimal:

143 = 1*100 + 4*10 +3 = x^2 + 4*x + 3 with x = 10

So we could run NFS to factor 143 using polynomials x^2+4x+3 and x-10. In the general case, you can express a number N in 'base M' by determining the number of pieces to break N into and then the value of M which will make some of the resulting polynomial coefficients smaller than average.

For a polynomial of degree d, you can pick a leading coefficient to be something small, then pick a value of M that is near

(N / leading_coefficient)^(1/d)

and expanding round_down(N/leading_coefficient) in base M. We expect that the resulting polynomial coefficients will be of size around M, and a polynomial is nicer than average if some of its coefficients are smaller than that.

Unfortunately there are many details between here and an actual efficient NFS polynomial for N. As Bob suggests, Brian Murphy's thesis on NFS polynomial selection is about the best place to start.

[c10ck3r]

Originally Posted by R.D. Silverman

??? I don't understand where "almost infinite" comes from. One expects that there will be at most about N usable polynomials.

Given a polynomial of degree d as : sum a_i x^i ,
the set of all usable a_i along with a possible root M mod N is definitely finite.

We would never take any a_i for which abs(a_i) > N. Given that typically a_i ~ N^(1/(d+2)) and M ~ N^(1/(d+2)), the number of different polynomials is about N^((d+2)/(d+2)) ~~ N
[there are d+1 coefficients whose size is bounded by about N^(1/(d+2)),
which along with M gives d+2 parameter choices]

Please clarify. We want the a_i to be SMALL and there is a limited
supply of such.

I would expect many of the possible polynomials to have the same efficiency.
[or so nearly the same that the difference is lost in the noise].

However, I just don't understand what you mean by "polynomial style".
Also what source do you refer to (i.e. "viewing in the same source")???

Please clarify.

An explanation of the algorithm would take many pages here. I suggest
reading Brian Murphy's paper.

I don't know what you mean by "multiply out". The polynomial f(x) is
such that it has a known integral root mod N, i.e. there is a known
value of M (which gets computed) such that f(M) = 0 mod N.

The polynomial coefficients are selected with a number of different properties in mind. We want lots of small ideals in the factor base. We want lots of projective roots. We want the norms of ideals of index 1, i.e. the numbers of the form norm(a + b alpha) where alpha is an irrational root of f(x)
[not a root mod N !!!] to be quite small. We want the probability that
norm(a + b alpha) factors over the factor base to be as large as possible
as a and b range over the lattice..... etc. etc. [note to purists: this isn't
quite correct, but it conveys the idea; it is also a good idea to have a large variance along with a large mean probability because a large variance means a fatter tail; relations are found in the tail].
We'd like the polynomial to have many real roots. Shall I go on?? Read Murphy's paper.

Is this what you are looking for?

To really understand this, one needs to learn some algebraic number theory [what ideals are, what norms in a number field are, what a ring homomorphism is, Dickman's function for the probabilities, projective roots, etc. etc. ] Dickman's function is well explained in Knuth Vol II and its evaluation is the only thing herein that really requires calculus. The number theory is a separate subject from Calculus

To make sure I am understanding your advice on "Murphy's Paper", are you referring to "On quadratic polynomials for the number field sieve"? I just found this and will begin reading it stat. After this I will try to acquire a copy or source for the information in Knuth's Second Volume.

Am I correct in understanding that f(M) is a multiple of N, the number to be factored, if f(M)=0 mod N?

The "same source" that I referred to was the same SourceForge website found in the link on the second post of this thread. That is where I found the "almost infinite" number of polynomials that fit a number.

I took the suggestion in this link to compare polynomials for 3-5% of the sieve time as an indication of differing efficiencies.

By polynomial "style", I was differing between quadratics, quartics, etc.

I will continue to work on this in any spare time. (Doesn't exist with 20 hours/week of work and 47.5 hours/week of schooling, not including homework, but will make room) Thanks for the recommendations on reading materials and the explanation of what we are looking for in a polynomial.

As one last point of clarification, does this mean that the OP's original polys are equally fit to factor the number (RSA-154 IIRC)?

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

The OPs polynomials are both quite good, but their scores are close enough to each other that it's not clear which would be better at the actual sieving.

[c10ck3r]

Thanks Jason!
I will find that paper in the morrow, but for now I need some shuteye. Thanks for the wording clarification as well.
As an aside, I truly do like RDS's method of teaching, as it seems to mirror my father's methods for "learning me stuff" (his grammar, not mine) after his Russian parents' discipline methods. Though it may scare some, it DOES push those who desire to excel to find any ways possible to do so (mainly to shove it in his face that we did). And Robert, using "et cetera" twice in a row is improper grammar, as I'm sure my English Comp professor would emphasize.

Ex Post Facto:
I get the polynomials now! Thanks for showing the example with 3 digits (base 10) and explaining the value of x!