20110720, 11:02  #12 
Tribal Bullet
Oct 2004
110111000101_{2} 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. 
20110720, 12:44  #13  
Dec 2010
Monticello
5×359 Posts 
Quote:
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? 

20110720, 14:51  #14 
(loop (#_fork))
Feb 2006
Cambridge, England
2·5^{2}·127 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. 
20110720, 15:24  #15  
Nov 2003
2^{5}×233 Posts 
Quote:
AFAIK, we have no software for generating septics. 

20110720, 16:33  #16  
Bamboozled!
May 2003
Down not across
10011101101000_{2} Posts 
Quote:
Paul 

20110720, 16:39  #17 
Tribal Bullet
Oct 2004
3·5^{2}·47 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 highorder 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 20110720 at 16:43 
20110721, 07:12  #18 
May 2011
France
241_{8} 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 
20110721, 07:54  #19 
May 2011
France
161_{10} 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 
20110721, 11:51  #20  
Aug 2004
81_{16} Posts 
Quote:
Chris 

20110721, 13:13  #21 
Tribal Bullet
Oct 2004
3×5^{2}×47 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.

20110721, 13:54  #22  
Nov 2003
1110100100000_{2} Posts 
Quote:
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) sublattice. 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 yingyang 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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Two questions:  Dubslow  GPU Computing  1  20110805 18:22 
Questions about the QS  Carmichael  Factoring  8  20070410 11:30 
Questions  OmbooHankvald  Prime Sierpinski Project  2  20050801 20:18 
LLR questions  OmbooHankvald  Math  6  20050623 11:42 
A few questions :)  xtreme2k  Lounge  59  20021031 06:20 