20050929, 17:18  #1 
Nov 2003
2^{2}·5·373 Posts 
Sieving Discussion
Hi,
For those of you using the Franke/Kleinjung et.al. lattice siever, allow me to ask some questions. (1) Does the siever user specialq's chosen strictly from within the factor base? Or does it also use 'large prime' specialq's? (2) What is the smallest specialq that is typically used? (3) *IF* it uses specialq's only from within the factor base, has anyone ever experienced 'running out' of specialq's before the sieving has finished? My code uses specialq's only from within the factor base. I typically start very small (special_q ~ 25K) and then use each prime in succession as a special_q. My most recent factorizations suggest that as I push my code to do numbers over 700 bits, that I might run out of specialq's before I have collected enough relations. I can alleviate this somewhat by increasing the size of the sieve region for each specialq. The yield rate for each specialq DROPS as they become larger. This is an expected and understood phenomenon. Indeed, if it were not so we could choose values of special_q so large that every instance of the polynomial norm factored completely. If the norm for the other polynomial did not increase as the special_q increases, we would only have to sieve one polynomial; the other one would be essentially 'free'. Suppose we choose special_q for the linear polynomial. Then as the q increases, the norms we need to be smooth decrease with ~1/q. But the norms for the nonlinear polynomial *increase* by "about" q^(d/2) where d is the degree. It is d/2, and not d because the coefficients we get from the *reduced* lattice are near sqrt(q) and not q. This drop in yield rate is not as severe as with linesieving, but it does mean that bigger special q's yield successively fewer relations. On the other hand, the smaller specialq's are more likely to yield duplicate relations...... Here are some yield results for 2,1346L. The number indicates the index of the first specialq within the factor base. Each file has the output from 10,000 special q's. Thus the file, nfsl10000.out has all the relations found between the 10'000 and 20'000 prime in the factor base. Each relation takes about 95 bytes. At 90K, I switched from a 7k x 7K sieve region to 6k x 6k, which explains the sudden drop. 183,852,832 nfsl10001.out 160,617,477 nfsl20001.out 143,707,023 nfsl30001.out 124,602,991 nfsl40001.out 120,071,852 nfsl50001.out 114,123,577 nfsl60001.out 107,210,439 nfsl70001.out 102,815,811 nfsl80001.out 84,965,910 nfsl90001.out 81,367,356 nfsl100001.out 78,394,837 nfsl110001.out 75,541,955 nfsl120001.out 73,820,721 nfsl130001.out 72,279,961 nfsl140001.out 70,855,737 nfsl150001.out 68,620,000 nfsl160001.out 66,308,104 nfsl170001.out 64,808,266 nfsl180001.out 63,225,248 nfsl190001.out 62,912,276 nfsl200001.out 52,918,122 nfsl300001.out 47,607,187 nfsl400001.out 45,695,605 nfsl500001.out 40,250,994 nfsl600001.out 37,939,364 nfsl700001.out Comments? 
20050929, 18:07  #2  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10,253 Posts 
Quote:
(2) The smallest prime greater than the largest prime in the factorbase. (3) Not applicable. Paul (Added in editing session) Yours is the only lattice siever of which I am aware that uses specialq wthin the factor base. Note that this statement is absence of evidence, not evidence of absence. Last fiddled with by xilman on 20050929 at 18:10 

20050929, 18:14  #3  
Nov 2003
2^{2}·5·373 Posts 
Quote:
is higher.......You can see how much higher from the yield data that I presented. 2,1346L used 1.2 million primes. 

20050929, 19:02  #4 
Oct 2004
tropical Massachusetts
3·23 Posts 
Yup, the Franke/Kleinjung lattice siever does not allow you to use special qs within the factor base (it errors out if q0 < rlim or alim, whichever is applicable). But you can circumvent this by adjusting the factorbase limit to MIN (xlim, q0) for each sieve run, and this is what GGNFS does. GGNFS defaults to starting at q0 = xlim/2.

20050929, 19:25  #5 
"Nancy"
Aug 2002
Alexandria
9A3_{16} Posts 
And it's what I do ("dragging fb limit along") when I'm desparate for a small matrix. It produces lots of duplicates, though.
Alex 
20050929, 19:31  #6  
Nov 2003
2^{2}·5·373 Posts 
Quote:
with 2,1346L, approximately 35% were duplicates. OTOH, if we use specialq's outside the factor base, then every one that is entered into the final matrix makes it bigger. Whereas specialq's that are in the factor base does not make it bigger. 

20050930, 11:15  #7  
Nov 2003
2^{2}·5·373 Posts 
Quote:
They produce more duplicates, but have a much higher yield rate. They clearly produce smaller matrices. For very large factorizations, a combination of the two might be best. 

20050930, 12:57  #8 
"Nancy"
Aug 2002
Alexandria
2467_{10} Posts 
One thing I meant to try some time (perhaps with 5,349) is counting how many relations with small sq are later repeated with larger sq. If the shape of the transformed sieve spaces is more or less the same for different sq, a relations with a q sieved as sq should be repeated later iff it contains an ideal of norm p>q so that p will be sieved as an sq value as well. Thus, if one has a reasonable estimate of over which range sq will be sieved, say sq in [l,u], one could estimate the rate of new unique relations found by very small sq by discarding relations with an ideal of norm sq<n<u. Then one could set some threshold dβ€1 and shift the sq range lower so long as the yield/time at the small sq is no worse than d * yield at large sq, where the choice of d depends on how badly you want a small matrix.
Alex 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
S9 and general sieving discussion  Lennart  Conjectures 'R Us  31  20140914 15:14 
Sieving discussion thread  jasong  Twin Prime Search  311  20101022 18:41 
Sieving discussion thread  philmoore  Five or Bust  The Dual Sierpinski Problem  66  20100210 14:34 
Combined sieving discussion  ltd  Prime Sierpinski Project  76  20080725 11:44 
Sieving Discussion  ltd  Prime Sierpinski Project  26  20051101 07:45 