Lattice Sieving Parameters

[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 and
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]

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 and

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

2) the threshold for sieving point values before checking it for smoothness

Depends on the number and size of the large primes.

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?

[paul0]

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

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

[henryzz]

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]

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 :)

[R.D. Silverman]

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?

[paul0]

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.