mersenneforum.org noob poly questions
 Register FAQ Search Today's Posts Mark Forums Read

 2011-11-13, 15:48 #1 sleigher   Mar 2010 3·17 Posts noob poly questions 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. Code: # 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
 2011-11-14, 01:42 #2 jasonp Tribal Bullet     Oct 2004 353610 Posts 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.
2011-11-14, 01:56   #3
R.D. Silverman

Nov 2003

22×5×373 Posts

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

 2011-11-14, 13:17 #4 sleigher   Mar 2010 3×17 Posts 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...
2011-11-14, 14:02   #5
R.D. Silverman

Nov 2003

22×5×373 Posts

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

2011-11-14, 14:15   #6
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

22·3·887 Posts

Quote:
 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

2011-11-14, 14:50   #7
R.D. Silverman

Nov 2003

22·5·373 Posts

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

2011-11-14, 15:43   #8
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

101001100101002 Posts

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

2011-11-14, 15:56   #9
R.D. Silverman

Nov 2003

22·5·373 Posts

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

 2011-11-14, 16:42 #10 jasonp Tribal Bullet     Oct 2004 24·13·17 Posts 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.
 2011-11-15, 00:25 #11 sleigher   Mar 2010 3·17 Posts 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... Last fiddled with by sleigher on 2011-11-15 at 00:30

 Similar Threads Thread Thread Starter Forum Replies Last Post awholenumber Math 7 2017-06-18 07:25 FlightTribe Information & Answers 13 2012-11-28 19:57 kladner GPU Computing 127 2011-11-04 10:57 nuggetprime Programming 6 2008-08-23 11:09 xago666 Information & Answers 3 2008-03-11 01:35

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

Fri Apr 16 12:16:35 UTC 2021 up 8 days, 6:57, 0 users, load averages: 2.02, 2.17, 2.17