mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2011-11-13, 15:48   #1
sleigher
 
Mar 2010

3·17 Posts
Default 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
sleigher is offline   Reply With Quote
Old 2011-11-14, 01:42   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

353610 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2011-11-14, 01:56   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by sleigher View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-11-14, 13:17   #4
sleigher
 
Mar 2010

3×17 Posts
Default

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...
sleigher is offline   Reply With Quote
Old 2011-11-14, 14:02   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by sleigher View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-11-14, 14:15   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22·3·887 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
xilman is offline   Reply With Quote
Old 2011-11-14, 14:50   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-11-14, 15:43   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

101001100101002 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
xilman is offline   Reply With Quote
Old 2011-11-14, 15:56   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by xilman View Post
I think we're in violent agreement.
But it seems (this could be wrong) that the O.P. doesn't want to
be bothered.
R.D. Silverman is offline   Reply With Quote
Old 2011-11-14, 16:42   #10
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

24·13·17 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2011-11-15, 00:25   #11
sleigher
 
Mar 2010

3·17 Posts
Default

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
sleigher is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Some noob questions about differential equation ? awholenumber Math 7 2017-06-18 07:25
2 Noob questions FlightTribe Information & Answers 13 2012-11-28 19:57
GPU Noob-Experiences/Questions kladner GPU Computing 127 2011-11-04 10:57
Noob C question nuggetprime Programming 6 2008-08-23 11:09
Noob question 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.