NFS questions - Page 2

jasonp · 2011-07-20, 11:02

NFS does not use a base of primes, it uses a base of 'ideals'. These look like prime numbers, but are more general. They help determine whether the algebraic 'thing' I mentioned is a square; it is actually the product of ideals.

I'm not sure what you're asking, but theory gives an estimate of how big the base of ideals and the size of the matrix should be to minimize the running time of NFS. We use experiments and guesswork to improve that estimate.

Christenson · 2011-07-20, 12:44

Quote:

Originally Posted by jasonp

Actually for a polynomial of degree d the algebraic part of the relation is b^d * AlgebraicPoly(a/b). d just happens to be 6 here.

I have no time to read Socrates in the original French, being in the middle of reading Shakespeare in the original Klingon.

Damn! I was just in the middle of reading Sartre in the original sanskrit!

You guys work way too hard at optimisation for the degree to "just happen" to be six....for example, six is two more than the degree of the largest polynomial with an algebraic formula in the coefficients for the roots. Or does finding and calculating with 7th degree polys carry a high cost that was found experimentally?

fivemack · 2011-07-20, 14:51

Yes; you can just experiment with the degree of the polynomial.

Degree 5 is pretty much OK from 110 digits to 200 digits GNFS; degree 4 is better for smaller numbers, degree 6 is a bit better for bigger ones.

R.D. Silverman · 2011-07-20, 15:24

Quote:

Originally Posted by fivemack

Yes; you can just experiment with the degree of the polynomial.

Degree 5 is pretty much OK from 110 digits to 200 digits GNFS; degree 4 is better for smaller numbers, degree 6 is a bit better for bigger ones.

And for RSA1024, it is likely/possible that a septic will be better than a sextic.
AFAIK, we have no software for generating septics.

xilman · 2011-07-20, 16:33

Quote:

Originally Posted by R.D. Silverman

And for RSA1024, it is likely/possible that a septic will be better than a sextic.
AFAIK, we have no software for generating septics.

To be more precise: AFAIK, we have no software for generating good septics. It's really really easy to generate bad ones.

Paul

jasonp · 2011-07-20, 16:39

It's true that nobody does GNFS with degree 7, but there is nothing special about degree 7 compared to degree 6. The first stage runs identically for any degree, you just have to find a target norm to shoot for. But the first stage only finds an algebraic polynomial whose top three coefficients obey the bound on the norm, and as the degree goes up the coefficients in the middle of the algebraic polynomial need to be forced to be smaller and smaller.

This is what stage 2 does; almost every degree 4 polynomial passes automatically and most degree 5 polynomials obey the bound after some fiddling. It starts to get difficult for degree 6, and doing the same with degree 7 and large amounts of skew means you'll have to go through millions of stage 1 candidates to find just one whose norm is decent. It might be so much work that it would be faster to modify stage 1 to directly generate candidates with more small high-order algebraic coefficients.

Brian Murphy's dissertation on polynomial selection has a pretty nice derivation of the formula for the NFS polynomial degree that is asymptotically optimal given the size of the number to be factored.

JohnFullspeed · 2011-07-21, 07:12

Always with stupid questions

The goal of the polynomial is to get a maximum of relations
smooth with b
How the degree changes this probability

John

JohnFullspeed · 2011-07-21, 07:54

make this computation

64 334 489 730 relations computed in 1500 years
1500 * 365 = 547 500 days
547 500 * 24 = 13 140 000 hours
13140000 * 60 = 788 400 000 minutes
64334489730 / 788400000= 81/mn
less one second to compute f(x) ,factories
and remove bad. It' impossible !!!! (for me....)

I think that 1500 years is not good: it's more!!!!!!!!
The total time must be compute by T* 64334489730 where T is this average time between the find of two relations
You surely have this time to distribute the code;
or you distribute the code using time or using the number of relation
i/e the PrimeGrid code search by segments of X minutes
or search Y relations

John

Chris Card · 2011-07-21, 11:51

Quote:

Originally Posted by JohnFullspeed

Always with stupid questions

The goal of the polynomial is to get a maximum of relations
smooth with b
How the degree changes this probability

John

One factor is that polynomials with smaller coefficients can be found if the degree is higher. Then the relation norms are smaller (on average), and so they are more likely to be smooth.

Chris

jasonp · 2011-07-21, 13:13

The smaller coefficients make it easier to find smooth numbers, but as (a,b) gets larger the higher degree will force the norm to increase more quickly (x^6 vs x^5). So you get a boost for small (a,b) but pay for it with large (a,b). The optimal degree is a compromise between these two forces.

R.D. Silverman · 2011-07-21, 13:54

Quote:

Originally Posted by jasonp

The smaller coefficients make it easier to find smooth numbers, but as (a,b) gets larger the higher degree will force the norm to increase more quickly (x^6 vs x^5). So you get a boost for small (a,b) but pay for it with large (a,b). The optimal degree is a compromise between these two forces.

It isn't quite this simple. Larger degrees also result in the rational
norm being smaller because the polynomial root becomes smaller.

Note also, that lattice sieving on the rational side ameliorates somewhat
the (effect of) degree increase on the algebraic.

Consider the rational side norm. We want norm(a + b N)/special_q
to be smooth. This suggests that the rational norms decrease with q.
They do, but only with sqrt(q) and not q itself.

The way lattice sieving works is by finding a reduced
lattice for the special_q. The average coefficient size of this reduced
lattice is about sqrt(q). Let [(a1, b1), (a2, b2)] be the reduced lattice.
The sieve works over the norms: i *(a1,b1) + j *(a2,b2) as i,j vary over a
(rectangular) sub-lattice. The norms depend on (a1, a2, b1, b2) and these
are roughly proportional to sqrt(q).

OTOH, while this reduces the effectiveness of special_q on the rational
side [norms we want smooth reduce by sqrt(q) instead of by q as q
increases]

This HELPS on the algebraic side. There is what I call a ying-yang effect in NFS.

Push the norms down on one side and it increases on the other. Optimum
is found when the norms are as nearly equal as possible. Normally,
if one pushes the rational norm down by a factor k, it pushes the
algebraic norm up by k^d. But since special_q on the rational
only pushes the norm down by sqrt(q) instead of q, it only pushes
the algebraic norm up by q^(d/2) instead of q^d.

2011-07-20, 16:39	#17
jasonp Tribal Bullet Oct 2004 3,541 Posts	It's true that nobody does GNFS with degree 7, but there is nothing special about degree 7 compared to degree 6. The first stage runs identically for any degree, you just have to find a target norm to shoot for. But the first stage only finds an algebraic polynomial whose top three coefficients obey the bound on the norm, and as the degree goes up the coefficients in the middle of the algebraic polynomial need to be forced to be smaller and smaller. This is what stage 2 does; almost every degree 4 polynomial passes automatically and most degree 5 polynomials obey the bound after some fiddling. It starts to get difficult for degree 6, and doing the same with degree 7 and large amounts of skew means you'll have to go through millions of stage 1 candidates to find just one whose norm is decent. It might be so much work that it would be faster to modify stage 1 to directly generate candidates with more small high-order algebraic coefficients. Brian Murphy's dissertation on polynomial selection has a pretty nice derivation of the formula for the NFS polynomial degree that is asymptotically optimal given the size of the number to be factored. Last fiddled with by jasonp on 2011-07-20 at 16:43

2011-07-21, 07:12	#18
JohnFullspeed May 2011 France A1₁₆ Posts	degree 7 Always with stupid questions The goal of the polynomial is to get a maximum of relations smooth with b How the degree changes this probability John

2011-07-21, 07:54	#19
JohnFullspeed May 2011 France A1₁₆ Posts	1500 years? make this computation 64 334 489 730 relations computed in 1500 years 1500 * 365 = 547 500 days 547 500 * 24 = 13 140 000 hours 13140000 * 60 = 788 400 000 minutes 64334489730 / 788400000= 81/mn less one second to compute f(x) ,factories and remove bad. It' impossible !!!! (for me....) I think that 1500 years is not good: it's more!!!!!!!! The total time must be compute by T* 64334489730 where T is this average time between the find of two relations You surely have this time to distribute the code; or you distribute the code using time or using the number of relation i/e the PrimeGrid code search by segments of X minutes or search Y relations John

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Two questions:	Dubslow	GPU Computing	1	2011-08-05 18:22
Questions about the QS	Carmichael	Factoring	8	2007-04-10 11:30
Questions	OmbooHankvald	Prime Sierpinski Project	2	2005-08-01 20:18
LLR questions	OmbooHankvald	Math	6	2005-06-23 11:42
A few questions :)	xtreme2k	Lounge	59	2002-10-31 06:20

2011-07-20, 11:02	#12
jasonp Tribal Bullet Oct 2004 3,541 Posts	NFS does not use a base of primes, it uses a base of 'ideals'. These look like prime numbers, but are more general. They help determine whether the algebraic 'thing' I mentioned is a square; it is actually the product of ideals. I'm not sure what you're asking, but theory gives an estimate of how big the base of ideals and the size of the matrix should be to minimize the running time of NFS. We use experiments and guesswork to improve that estimate.

2011-07-20, 14:51	#14
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²×131 Posts	Yes; you can just experiment with the degree of the polynomial. Degree 5 is pretty much OK from 110 digits to 200 digits GNFS; degree 4 is better for smaller numbers, degree 6 is a bit better for bigger ones.

2011-07-21, 13:13	#21
jasonp Tribal Bullet Oct 2004 3,541 Posts	The smaller coefficients make it easier to find smooth numbers, but as (a,b) gets larger the higher degree will force the norm to increase more quickly (x^6 vs x^5). So you get a boost for small (a,b) but pay for it with large (a,b). The optimal degree is a compromise between these two forces.