mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-09-29, 17:18   #1
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Question 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?
R.D. Silverman is offline   Reply With Quote
Old 2005-09-29, 18:07   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

10,253 Posts
Default

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.

Last fiddled with by xilman on 2005-09-29 at 18:10
xilman is online now   Reply With Quote
Old 2005-09-29, 18:14   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Thumbs up

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-09-29, 19:02   #4
trilliwig
 
trilliwig's Avatar
 
Oct 2004
tropical Massachusetts

3·23 Posts
Default

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.
trilliwig is offline   Reply With Quote
Old 2005-09-29, 19:25   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A316 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-09-29, 19:31   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Thumbs up

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 is offline   Reply With Quote
Old 2005-09-30, 11:15   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-09-30, 12:57   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

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
akruppa is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 18:32.

Fri Sep 25 18:32:40 UTC 2020 up 15 days, 15:43, 0 users, load averages: 1.65, 1.48, 1.43

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.