mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   NFSNET Discussion (https://www.mersenneforum.org/forumdisplay.php?f=17)
-   -   What traits make a number a good choice for NFSNET? (https://www.mersenneforum.org/showthread.php?t=650)

wblipp 2003-06-07 23:06

What traits make a number a good choice for NFSNET?
 
What traits make a number a good choice for NFSNET? Is the size of the base number (227 digits for 10^227-1) important? Is ths size of the composite cofactor (212 digits for 10^227-1) important? How big is "too big to be interesting?" How much previous work should have been done by other methods?

xilman 2003-06-08 17:01

[i]What traits make a number a good choice for NFSNET? Is the size of the base number (227 digits for 10^227-1) important? Is ths size of the composite cofactor (212 digits for 10^227-1) important? How big is "too big to be interesting?" How much previous work should have been done by other methods?[/i]

Several characteristics are taken into account. Perhaps the most important is that it should not be too hard (or we'd never get it finished with the resources we have) or too easy (or we'd spend more time on administration than computation. For SNFS, the range is about 180 to 240 digits. For GNFS the range is perhaps 135 digits to 165 digits.

For the time being we want to do numbers which are of some mathematical interest, which means in practice they come from a number of well know tables of factorizations associated with various projects. Almost all so far have come from the Cunningham project.

We don't want to spend a great deal of effort finding a factor which could have been found much more easily with the Elliptic Curve Method, so we generally require that a NFSNET candidate have had enough ECM work done on it that it's unlikely to have a factor below 50 digits or so.


Paul

wblipp 2003-08-07 22:04

[quote="xilman"]For SNFS, the range is about 180 to 240 digits. For GNFS the range is perhaps 135 digits to 165 digits.[/quote]
So looking at the 195 digit cofactor from 2^1188+1, it's not a good candidate.

1. The 195 digit cofactor is bigger than the 165 digit limit for GNFS.

2. The 358 digit 2^1188+1 is bigger than the 240 digit limit for SNFS.

3. The primitive polynomial is only 217 digits, but

(x^33+1)*(x+1)/((x^11+1)*(x^3+1))

isn't special enough for SNFS to take advantage of.

Is that all correct?

xilman 2003-08-08 11:46

[quote="wblipp"][quote="xilman"]For SNFS, the range is about 180 to 240 digits. For GNFS the range is perhaps 135 digits to 165 digits.[/quote]
So looking at the 195 digit cofactor from 2^1188+1, it's not a good candidate.

1. The 195 digit cofactor is bigger than the 165 digit limit for GNFS.

2. The 358 digit 2^1188+1 is bigger than the 240 digit limit for SNFS.

3. The primitive polynomial is only 217 digits, but

(x^33+1)*(x+1)/((x^11+1)*(x^3+1))

isn't special enough for SNFS to take advantage of.

Is that all correct?[/quote]

Sounds like a good summary to me.

If you can find a polynomial of degree at most 7 with coefficients all of which are smaller than, say, 9 digits and a corresponding root modulo N (where N is the 217-digit number) then we could run SNFS on it. I haven't found any such polynomial.


Paul

wblipp 2003-08-08 15:17

[quote="xilman"][quote="wblipp"]So looking at the 195 digit cofactor from 2^1188+1, it's not a good candidate.

1. The 195 digit cofactor ...

2. The 358 digit 2^1188+1 ....

3. The primitive polynomial is only 217 digits ...
[/quote]

If you can find a polynomial of degree at most 7 with coefficients all of which are smaller than, say, 9 digits and a corresponding root modulo N (where N is the 217-digit number) then we could run SNFS on it. I haven't found any such polynomial.[/quote]

Is it sufficient for the root to be modulo the C195 cofactor, or does the root really need to be modulo the C217 primitive factor?

xilman 2003-08-10 10:28

[quote="wblipp"][quote="xilman"][quote="wblipp"]So looking at the 195 digit cofactor from 2^1188+1, it's not a good candidate.

1. The 195 digit cofactor ...

2. The 358 digit 2^1188+1 ....

3. The primitive polynomial is only 217 digits ...
[/quote]

If you can find a polynomial of degree at most 7 with coefficients all of which are smaller than, say, 9 digits and a corresponding root modulo N (where N is the 217-digit number) then we could run SNFS on it. I haven't found any such polynomial.[/quote]

Is it sufficient for the root to be modulo the C195 cofactor, or does the root really need to be modulo the C217 primitive factor?[/quote]

Modulo the C195 is fine. Oh, I forgot: the polynomial has to have degree at least 4.

Paul

wblipp 2004-02-23 17:44

[QUOTE=xilman]For SNFS, the range is about 180 to 240 digits. For GNFS the range is perhaps 135 digits to 165 digits.
...
If you can find a polynomial of degree at most 7 (and at least 4) with coefficients all of which are smaller than, say, 9 digits and a corresponding root modulo N (where N is the 217-digit number (or the 195-digit number)) then we could run SNFS on it.[/QUOTE]

For cases where we can find such a polynomial, is the feasible range then same 180-240 digits quoted above? Or would such a "found" polynomial be less effective, so that the practical range is something between these ranges?

William

xilman 2004-02-24 09:11

[QUOTE=wblipp]For cases where we can find such a polynomial, is the feasible range then same 180-240 digits quoted above? Or would such a "found" polynomial be less effective, so that the practical range is something between these ranges?

William[/QUOTE]
The range 180-240 remains the same.

Paul

nfortino 2004-02-24 11:43

Could someone point me to a good paper on the SNFS? I was able to find one on the GNFS, but I haven’t found one detailing the differences.

TauCeti 2004-02-24 13:48

[QUOTE=nfortino]Could someone point me to a good paper on the SNFS? I was able to find one on the GNFS, but I haven’t found one detailing the differences.[/QUOTE]

An excellent and freely available 142-page paper (diploma thesis) with an explanation of the general ideas behind NFS and a GNFS/SNFS comparison can be found [URL=http://www.informatik.tu-darmstadt.de/KP/staff/samoa/NFS.pdf]here[/URL]. But AFAIK it's only available in german language.

There are also large sections about GNFS and SNFS in the book 'Prime Numbers" from Crandall and Pomerance.

So far i have not looked into 'The Development of the Number Field Sieve' from Lenstra but maybe i should if i ever want to succeed understanding the SNFS ;)

junky 2004-02-24 14:44

[QUOTE=nfortino]Could someone point me to a good paper on the SNFS? I was able to find one on the GNFS, but I haven’t found one detailing the differences.[/QUOTE]

really good question, if ya find something before me, feel free to post it, so I and a lot a ppl would have the possibility to take a look on it.

im sure we could find such papers somewhere in US' universities. Maybe Jeff would knows :)

later

R.D. Silverman 2004-02-25 17:48

"Quote:
Originally Posted by nfortino
Could someone point me to a good paper on the SNFS? I was able to find one on the GNFS, but I haven’t found one detailing the differences.


really good question, if ya find something before me, feel free to post it, so I and a lot a ppl would have the possibility to take a look on it.

im sure we could find such papers somewhere in US' universities. Maybe Jeff would knows :)"

If you will send me a private note, with your email address, I will send
a paper (Postscript) describing details of SNFS.

junky 2004-03-01 12:53

hey bob, im still waiting for your papers :)

thanks.

wpolly 2004-03-02 12:45

What about the C228 cofactor of 12^256+1?

R.D. Silverman 2004-03-02 13:18

[QUOTE=wpolly]What about the C228 cofactor of 12^256+1?[/QUOTE]

It is too big. The C277 for 12,256+ is too big for SNFS and the C228 is
too big for GNFS.

wblipp 2004-03-03 14:34

[QUOTE=xilman]If you can find a polynomial of degree at most 7 with coefficients all of which are smaller than, say, 9 digits and a corresponding root modulo N (where N is the 217-digit number) then we could run SNFS on it.[/QUOTE]

Does the root need to be small, too? If yes, then it's probably rare for such a polynomial and root to exist because there are only 10^81 combinations of coefficients and roots versus 10^217 possibe modulo values. If the root can be as large as N, then there are probably many such polynomials although it may be difficult to find one of them.

wblipp 2004-03-03 16:21

[QUOTE=wblipp]Does the root need to be small, too?[/QUOTE]

A bit more musing shows me the root can probably be large. It not, then the highest possible value for the polynomial is about 10[sup]72[/sup]. so the only way to make the modular value zero would be to make the polynomial value zero, which would mean that (x-r) is a factor of the polynomial. Since it's trivial to create such polynomials as (x-r) times anything, it's unlikely such polynomials are of any use.

xilman 2004-03-04 09:29

[QUOTE=wblipp]A bit more musing shows me the root can probably be large. It not, then the highest possible value for the polynomial is about 10[sup]72[/sup]. so the only way to make the modular value zero would be to make the polynomial value zero, which would mean that (x-r) is a factor of the polynomial. Since it's trivial to create such polynomials as (x-r) times anything, it's unlikely such polynomials are of any use.[/QUOTE]
The root can be any size you like. What's important is the size of the coefficients of the polynomials.

Actually, that's an oversimplification, but it's a good first cut. If you want more details, dig out Brian Murphy's thesis.

An example may help. NFSNET is currently sieving the 201-digit composite cofactor of 10^223+1. We are using the polynomials x^6+10 and 1 - (10^37)*x which share a root 10^(-37) modulo 10^223+1. The latter value is a 201-digit number.


Paul

R.D. Silverman 2004-03-09 16:24

[QUOTE=xilman]The root can be any size you like. What's important is the size of the coefficients of the polynomials.

Actually, that's an oversimplification, but it's a good first cut. If you want more details, dig out Brian Murphy's thesis.

An example may help. NFSNET is currently sieving the 201-digit composite cofactor of 10^223+1. We are using the polynomials x^6+10 and 1 - (10^37)*x which share a root 10^(-37) modulo 10^223+1. The latter value is a 201-digit number.


Paul[/QUOTE]

Actually Paul, the size of the root does matter. Let's use your example
and look at a 'typical' lattice point. (say (3x10^6, 3x10^6)) (choose
another if you like)

We have two polynomials. The corresponding norms at lattice point (b,a)
are a + 10^37 b and a^6 + 10b^6. For our typical point, the norms are
about 3x10^43 and 7x10^39. Note that the linear norm is larger. The
product is about 2x10^82

If we were to use a quintic, the linear norm becomes about 3 x 10^51
while the algebraic norm shrinks to 2 x 10^33. The product is now about
6 x 10^84, i.e. larger.

A septic would yield norms of about 3x10^38 and 2 x 10^46.

Having equal norms would be optimal.

The size of the root affects the norm of the linear polynomial. There is a
ying-yang effect. Reducing one norm increases the other and vice versa.
We want the product to be as small as possible averaged over the sieve
region.

See my recent paper for a more detailed analysis.

xilman 2004-03-10 15:48

[QUOTE=Bob Silverman]Actually Paul, the size of the root does matter. Let's use your example
and look at a 'typical' lattice point. (say (3x10^6, 3x10^6)) (choose
another if you like)

We have two polynomials. The corresponding norms at lattice point (b,a)
are a + 10^37 b and a^6 + 10b^6. For our typical point, the norms are
about 3x10^43 and 7x10^39. Note that the linear norm is larger. The
product is about 2x10^82

If we were to use a quintic, the linear norm becomes about 3 x 10^51
while the algebraic norm shrinks to 2 x 10^33. The product is now about
6 x 10^84, i.e. larger.

A septic would yield norms of about 3x10^38 and 2 x 10^46.

Having equal norms would be optimal.

The size of the root affects the norm of the linear polynomial. There is a
ying-yang effect. Reducing one norm increases the other and vice versa.
We want the product to be as small as possible averaged over the sieve
region.

See my recent paper for a more detailed analysis.[/QUOTE]


Bob, I agree with you (with the reservations noted in my original about the analysis only being a first cut) [B]if[/B] the linear polynomial is of the form x-m where m is the root.

Note there is nothing in the NFS which requires a polynomial to be linear, though a linear polynomial is very frequently used because of the difficulty in finding good polynomials of higher degree which share a common root with other polynomial(s) in use.

Neither is there any requirement that a linear polynomial by x-m. I gave an explicit example where the root m is very large but the poynomial norms are quite small. That polynomial was x/m - 1.

I further note that Kleinjung's method of finding quintics for GNFS finds linear polynomials of the form ax+b where neither a nor b are equal to the value of the common root.

I stand by my claim that (subject to the agreed disclaimer) that the size of the coefficients of the polynomials are much more important than the size of the root. By taking x-m as your linear polynomial you are implicitly agreeing with me as in this particular case the root [B]is[/B] a coefficient of a polynomial.

I do, of course, agree that ideally the degrees and coefficients of the polynomials should be chosen that the norms are as close to each other as possible and as small as possible (again, subject to considerations which can be found in Murphy's thesis).


Paul

jasong 2005-05-05 02:34

Somewhat off-topic: Would this Brian Murphy you keep mentioning happen to be a dark-haired fat dude with a winning smile? I knew a Brian Murphy that went to college here in Conway, AR, but I don't know his major. Could he be the same guy?


All times are UTC. The time now is 23:28.

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