mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Lattice Sieving Parameters (https://www.mersenneforum.org/showthread.php?t=20673)

 paul0 2015-11-17 22:06

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 [TEX]I[/TEX] and [TEX]J[/TEX]
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?

 R.D. Silverman 2015-11-17 22:50

[QUOTE=paul0;416453]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 [TEX]I[/TEX] and [TEX]J[/TEX]
[/QUOTE]

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
[/QUOTE]

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?[/QUOTE]

 paul0 2015-11-18 14:00

I was reading Franke's siever's readme, it uses this as bound: log(abs(polynomial value))-lambda*log(factor base bound)

As for [TEX]I[/TEX] and [TEX]J[/TEX], I think I have to experiment to find good values, as I doubt anyone has data for small composites.

 henryzz 2015-11-18 15:09

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.

 paul0 2015-11-18 20:43

[STRIKE]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?
[/STRIKE]
EDIT: btw, my lattice siever is operational. I'll upload it to github when I'm satisfied with it :)

 R.D. Silverman 2015-11-18 23:17

[QUOTE=paul0;416577][STRIKE]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?
[/STRIKE]
EDIT: btw, my lattice siever is operational. I'll upload it to github when I'm satisfied with it :)[/QUOTE]

Are you remembering to handle projective roots properly?
Are you handling skew?
What method do you use to split the large primes?

 paul0 2015-11-20 21:12

[QUOTE=R.D. Silverman;416588]Are you remembering to handle projective roots properly?
Are you handling skew?
What method do you use to split the large primes?[/QUOTE]

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.

 All times are UTC. The time now is 16:52.