mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2015-11-17, 22:06   #1
paul0
 
Sep 2011

3916 Posts
Default 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
paul0 is offline   Reply With Quote
Old 2015-11-17, 22:50   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by paul0 View Post
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?
R.D. Silverman is offline   Reply With Quote
Old 2015-11-18, 14:00   #3
paul0
 
Sep 2011

718 Posts
Default

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
paul0 is offline   Reply With Quote
Old 2015-11-18, 15:09   #4
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

585310 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2015-11-18, 20:43   #5
paul0
 
Sep 2011

1110012 Posts
Default

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
paul0 is offline   Reply With Quote
Old 2015-11-18, 23:17   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by paul0 View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2015-11-20, 21:12   #7
paul0
 
Sep 2011

1110012 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
paul0 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
I'm getting an error when yafu wants to start lattice sieving Hailstone YAFU 30 2018-05-23 19:33
Lattice Sieving - where do I start? paul0 Factoring 3 2015-03-09 13:54
Line sieving vs. lattice sieving JHansen NFSNET Discussion 9 2010-06-09 19:25
A question on lattice sieving joral Factoring 5 2008-04-03 08:01
Initialization for lattice sieving jasonp Factoring 16 2006-01-12 22:53

All times are UTC. The time now is 00:03.

Mon Apr 12 00:03:59 UTC 2021 up 3 days, 18:44, 1 user, load averages: 1.67, 1.50, 1.55

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.