noob poly questions

[sleigher]

Hi Guys,

I was hoping someone could take a second and help me understand the differences in the following outputs.

These are both from RSA-154

The first one the c0: is - and the second one is not. It seems all the fields are reversed in terms of a leading - and the c5: line
is very different. Any insight would be very helpful. Or is there a doc somewhere that can help me understand each line?

Also the first one was from msieve version 1.42 I think and the second from 1.49. Both from the same GPU but different N's.

# norm 5.537956e-15 alpha -6.828280 e 3.009e-12
skew: 10062842.74
c0: -77511246416842652782947827243153982720
c1:  52845910196937376909035045081456
c2:  64530037137566250198775404
c3: -6266879667492455540
c4: -604994336743
c5:  3300
Y0: -1156038696359091884229749817581
Y1:  193522735996815187


norm 6.077880e-15 alpha -6.591518 e 3.228e-12 rroots 5
skew: 14813998.57
c0: 271830330224374546052564805914266259840
c1: -928034253578711160424890240906
c2: -26681915219460396213323881
c3: 680113183828316262
c4: 141225440666
c5: 84
Y0: -2521959333809067094313594330127
Y1: 53520081350873741

[jasonp]

See the section on NFS polynomial selection in this document and ask further questions if you need to.

The numbers are polynomial coefficients, either positive or negative. They look random but are not; each collection of numbers can be used for NFS sieving, but some will complete the sieving faster than others.

[R.D. Silverman]

Originally Posted by sleigher

Hi Guys,

I was hoping someone could take a second and help me understand the differences in the following outputs.

These are both from RSA-154

The first one the c0: is - and the second one is not. It seems all the fields are reversed in terms of a leading - and the c5: line
is very different. Any insight would be very helpful. Or is there a doc somewhere that can help me understand each line?

You might try learning about the algorithm first. It should be the
first step before even trying to use the software.

[sleigher]

Jason, Thanks for that.

RD, I am trying to understand these things. That's what I ask those who know
to point me in the right direction. Unfortunately I don't have a math degree, or any degree for that matter. But I do like to learn about things that interest me.
I learn best by doing, so I do...

[R.D. Silverman]

Originally Posted by sleigher

Jason, Thanks for that.

RD, I am trying to understand these things. That's what I ask those who know
to point me in the right direction. Unfortunately I don't have a math degree, or any degree for that matter. But I do like to learn about things that interest me.
I learn best by doing, so I do...

Except that one can not learn about NFS by blindly running the
software written by others. There are many elementary
expositions of NFS available on the Web. Repeat after me: "Google is
my friend".

And while I don't want to be personally rude, one has no hope of
understanding NFS without first learning some mathematics. One does
not need a math degree. One does need what is known as 'mathematical
maturity' as well as a SOLID grounding in high school math and a
willingness to learn.

Go READ. I will be happy to answer any questions you might have.
You should start by understanding how QS works.

[xilman]

Originally Posted by R.D. Silverman

Except that one can not learn about NFS by blindly running the software written by others. There are many elementary expositions of NFS available on the Web. Repeat after me: "Google is my friend".

And while I don't want to be personally rude, one has no hope of understanding NFS without first learning some mathematics. One does not need a math degree. One does need what is known as 'mathematical maturity' as well as a SOLID grounding in high school math and a willingness to learn.

Go READ. I will be happy to answer any questions you might have. You should start by understanding how QS works.

While I agree with what Bob says, I'd rephrase his first sentence. I'd add the word "only" after "NFS" and emphasise the word "blindly".

In my experience, reading and attempting to understand pieces of software (necessarily small pieces of something as large and complex as a top-line NFS implementation) can be very helpful in understanding an algorithm. You still need the mathematics to understand why an algorithm works.

Like most non-trivial intellectual constructs, having the same document written in two or more languages can aid comprehension more more easily than either monolingual version individually. The Behistun inscriptions are a classical (in both meanings of the word) example of this phenomenon.


Paul

[R.D. Silverman]

Originally Posted by xilman

While I agree with what Bob says, I'd rephrase his first sentence. I'd add the word "only" after "NFS" and emphasise the word "blindly".

In my experience, reading and attempting to understand pieces of software (necessarily small pieces of something as large and complex as a top-line NFS implementation) can be very helpful in understanding an algorithm. You still need the mathematics to understand why an algorithm works.

Like most non-trivial intellectual constructs, having the same document written in two or more languages can aid comprehension more more easily than either monolingual version individually. The Behistun inscriptions are a classical (in both meanings of the word) example of this phenomenon.


Paul

More or less. But one needs to start with a high level description of
what the algorithm is trying to do. In this case, construct instances of
A^2 = B^2 mod N by building up A and B through all of the individual
relations. They are created by sieving. One needs to
understand the role of the two polynomials, how they are used so that
candidate norms are made as small as possible (and why small norms
are desirable). One needs to understand how a sieve works and how one
builds A^2 = B^2 mod N via linear algebra.

THEN one can dive into the details of how each computation works.

[xilman]

Originally Posted by R.D. Silverman

More or less. But one needs to start with a high level description of
what the algorithm is trying to do. In this case, construct instances of
A^2 = B^2 mod N by building up A and B through all of the individual
relations. They are created by sieving. One needs to
understand the role of the two polynomials, how they are used so that
candidate norms are made as small as possible (and why small norms
are desirable). One needs to understand how a sieve works and how one
builds A^2 = B^2 mod N via linear algebra.

THEN one can dive into the details of how each computation works.

I think we're in violent agreement.

[R.D. Silverman]

Originally Posted by xilman

I think we're in violent agreement.

But it seems (this could be wrong) that the O.P. doesn't want to
be bothered.

[jasonp]

Incidentally, the first few NFS references near the bottom of this document give just about all the introductory NFS papers, most of which are accessible online.

[sleigher]

It's not that I don't want to be bothered. I am a Sr. Level Systems Architect for a large healthcare company and have 3 kids. Although I do want to be bothered to learn whatever I can, with only 24 hours a day it's just not as easy to find the time that I used to. I am trying to understand the math as well as the software. I have gone down this road before with msieve.

Large HPC clusters is another item of interest and because parts of this can be run in parallel, there is a match there from my perspective. Using MPI and LSF with things like msieve and ggnfs is something I tinker with in my spare time on compute clusters, and although I am not a math master like you guys, I am technical and will learn the underlying theory to some of this as I go along.

The paper Jason posted I read three times today. As well as some other docs about gnfs so that I can understand how it works and why.

Actually, why are you attacking me? I just asked a question. How do you know I am not reviewing the code and understanding what I can and learning from that.
You don't. You just assume that because I ask a question that seems trivial to you, that I must be some kid trying to hack his girlfriends email right?

ho ho ho...