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

 2015-11-17, 22:06 #1 paul0   Sep 2011 3×19 Posts Lattice Sieving Parameters Now that I can generate a sublattice basis and reduce it, I think I'm ready to write a lattice siever. However, there seems to be more parameters I don't know how to set: 1) the sieving region $I$ and $J$ 2) the threshold for sieving point values before checking it for smoothness 3) how do I choose special q's? outside the factor base? 4) (I'll probably think of more as I go along) How do I set these parameters? Last fiddled with by paul0 on 2015-11-17 at 22:09
2015-11-17, 22:50   #2
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by paul0 Now that I can generate a sublattice basis and reduce it, I think I'm ready to write a lattice siever. However, there seems to be more parameters I don't know how to set: 1) the sieving region $I$ and $J$

These depend on the size of the composite, the size of the factor base, and the number
of large primes.

Quote:
 2) the threshold for sieving point values before checking it for smoothness
Depends on the number and size of the large primes.

Quote:
 3) how do I choose special q's? outside the factor base? GGNFS does. I don't. 4) (I'll probably think of more as I go along) How do I set these parameters?

 2015-11-18, 14:00 #3 paul0   Sep 2011 1110012 Posts I was reading Franke's siever's readme, it uses this as bound: log(abs(polynomial value))-lambda*log(factor base bound) As for $I$ and $J$, I think I have to experiment to find good values, as I doubt anyone has data for small composites. Last fiddled with by paul0 on 2015-11-18 at 14:12
 2015-11-18, 15:09 #4 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 587010 Posts For I and J powers of 2 are often convenient. Ideally you would select special qs from within and outside the factorbase. Yield decreases as the special q gets larger. Composite special qs have been experimented with.
 2015-11-18, 20:43 #5 paul0   Sep 2011 718 Posts In gnfs-lasieve, why is there two parameters (for rational and algebraic) for the sieving bound? Is the sieve checked twice? If so, what is the advantage instead just checking it once? The sieve adds the logarithms anyway, right? EDIT: btw, my lattice siever is operational. I'll upload it to github when I'm satisfied with it :) Last fiddled with by paul0 on 2015-11-18 at 21:31
2015-11-18, 23:17   #6
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by paul0 In gnfs-lasieve, why is there two parameters (for rational and algebraic) for the sieving bound? Is the sieve checked twice? If so, what is the advantage instead just checking it once? The sieve adds the logarithms anyway, right? EDIT: btw, my lattice siever is operational. I'll upload it to github when I'm satisfied with it :)
Are you remembering to handle projective roots properly?
Are you handling skew?
What method do you use to split the large primes?

Last fiddled with by R.D. Silverman on 2015-11-18 at 23:18

2015-11-20, 21:12   #7
paul0

Sep 2011

3·19 Posts

Quote:
 Originally Posted by R.D. Silverman Are you remembering to handle projective roots properly? Are you handling skew? What method do you use to split the large primes?
I'll research about all of those and implement them eventually. I'll probably abandon the python lattice siever and move to C since I can control lots things there, like the sieve and factor base data type, data access patterns and code size for cache. It seems fun to try & squeeze as much performance as possible.

But for now, I'm trying to finish my undergraduate degree, I'm swamped.

 Similar Threads Thread Thread Starter Forum Replies Last Post Hailstone YAFU 30 2018-05-23 19:33 paul0 Factoring 3 2015-03-09 13:54 JHansen NFSNET Discussion 9 2010-06-09 19:25 joral Factoring 5 2008-04-03 08:01 jasonp Factoring 16 2006-01-12 22:53

All times are UTC. The time now is 19:41.

Sun May 9 19:41:04 UTC 2021 up 31 days, 14:21, 1 user, load averages: 2.11, 2.51, 2.86