mersenneforum.org Sieving Discussion
 Register FAQ Search Today's Posts Mark Forums Read

 2005-09-29, 17:18 #1 R.D. Silverman     Nov 2003 22·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 special-q's chosen strictly from within the factor base? Or does it also use 'large prime' special-q's? (2) What is the smallest special-q that is typically used? (3) *IF* it uses special-q's only from within the factor base, has anyone ever experienced 'running out' of special-q's before the sieving has finished? My code uses special-q'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 special-q's before I have collected enough relations. I can alleviate this somewhat by increasing the size of the sieve region for each special-q. The yield rate for each special-q 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 non-linear 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 line-sieving, but it does mean that bigger special q's yield successively fewer relations. On the other hand, the smaller special-q's are more likely to yield duplicate relations...... Here are some yield results for 2,1346L. The number indicates the index of the first special-q 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?
2005-09-29, 18:07   #2
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

73×31 Posts

Quote:
 Originally Posted by R.D. Silverman Hi, For those of you using the Franke/Kleinjung et.al. lattice siever, allow me to ask some questions. (1) Does the siever user special-q's chosen strictly from within the factor base? Or does it also use 'large prime' special-q's? (2) What is the smallest special-q that is typically used? (3) *IF* it uses special-q's only from within the factor base, has anyone ever experienced 'running out' of special-q's before the sieving has finished?
(1) No and yes, respectively.

(2) The smallest prime greater than the largest prime in the factorbase.

(3) Not applicable.

Paul

Yours is the only lattice siever of which I am aware that uses special-q wthin the factor base. Note that this statement is absence of evidence, not evidence of absence.

Last fiddled with by xilman on 2005-09-29 at 18:10

2005-09-29, 18:14   #3
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 Originally Posted by xilman (1) No and yes, respectively. (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 special-q wthin the factor base. Note that this statement is absence of evidence, not evidence of absence.
I use special-q's within the factor base precisely because the yield rate
is higher.......You can see how much higher from the yield data that I
presented. 2,1346L used 1.2 million primes.

 2005-09-29, 19:02 #4 trilliwig     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.
 2005-09-29, 19:25 #5 akruppa     "Nancy" Aug 2002 Alexandria 46438 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
2005-09-29, 19:31   #6
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by akruppa 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
Yes. Indeed. It does produce lots of duplicates. When I was done
with 2,1346L, approximately 35% were duplicates.

OTOH, if we use special-q's outside the factor base, then every one
that is entered into the final matrix makes it bigger. Whereas special-q's
that are in the factor base does not make it bigger.

2005-09-30, 11:15   #7
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by R.D. Silverman Yes. Indeed. It does produce lots of duplicates. When I was done with 2,1346L, approximately 35% were duplicates. OTOH, if we use special-q's outside the factor base, then every one that is entered into the final matrix makes it bigger. Whereas special-q's that are in the factor base does not make it bigger.
So, is it more efficient to use special-q from within the factor base or not?
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.

 2005-09-30, 12:57 #8 akruppa     "Nancy" Aug 2002 Alexandria 2,467 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Lennart Conjectures 'R Us 31 2014-09-14 15:14 jasong Twin Prime Search 311 2010-10-22 18:41 philmoore Five or Bust - The Dual Sierpinski Problem 66 2010-02-10 14:34 ltd Prime Sierpinski Project 76 2008-07-25 11:44 ltd Prime Sierpinski Project 26 2005-11-01 07:45

All times are UTC. The time now is 11:33.

Sat Apr 10 11:33:49 UTC 2021 up 2 days, 6:14, 1 user, load averages: 2.12, 2.12, 1.81