Sieving Discussion

R.D. Silverman · 2005-09-29, 17:18

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?

xilman · 2005-09-29, 18:07

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

(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.

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

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.

trilliwig · 2005-09-29, 19:02

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.

akruppa · 2005-09-29, 19:25

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

R.D. Silverman · 2005-09-29, 19:31

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.

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

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.

akruppa · 2005-09-30, 12:57

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

2005-09-29, 17:18	#1
R.D. Silverman Nov 2003 7460₁₀ 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?

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

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 2,467 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-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<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