Remove the sieve?

[Joe Rowell]

Hi all,

As some of you may have noticed, there has been an issue open since May last year (#369 on the repository) about whether to remove the Gauss sieve (which can be found in https://github.com/fplll/fplll/tree/master/fplll/sieve) to a separate branch. 

The outcome of this discussion was to ask the mailing list for their opinions and go from there.

The main open question is: with G6K being a thing, does anyone actually use this? 

Cheers,

Joe

[Emmanouil Doulgerakis]

Hi everyone,

As Joe posed the question:

``The main open question is: with G6K being a thing, does anyone actually use this? "

I would like to share my opinion on this. Well, I am actually using the Gauss sieve as I am

interested in its output set specifically. Hence, I am not using it to solve SVP but instead

in order to study a specific set of lattice vectors. But, that is just me and somebody could

very well argue that a similar computational task can be performed by G6K.

My opinion is that the Gauss sieve should not be completely removed due to educational reasons.

As far as I understand the fplll library does not aim in being just a tool in the hands of researchers but

also for ``researchers in the making". Hence serve an educational purpose as well.

Even though G6K is the state of the art implementation which everybody should use (i.e. if one wants to

solve SVP in dimension 100) it might not be the easier for a ``hands-on" experience for somebody

just introduced to lattice sieving. On the other hand, as the Gauss sieve in fplll just includes ``the basics"

of sieving, it is easier to be used for an introductory ``hands-on" experience to lattice sieving.

I must admitt that I have not dived deep into the G6K code so I may be mistaken on this and

G6K can indeed be used as an educational tool as well. In this case please just

disregard my claim. My intend was just to point out this educational aspect.

Maybe somebody in the fplll development team who is familiar with both implementations

could evaluate if there is a point in my claim.

Best regards,

Manos

[Joe Rowell]

Hi,

I agree that we should not remove the sieve in its entirety. The discussion in the github issue reached the consensus that, if it were to be removed, then it should be moved to a separate branch in the repository. This is for exactly the reason you mentioned - some people may still wish to read the code alongside the original paper, and certainly it uses more "traditional" sieving techniques than G6K (i.e Klein sampling vs Babai's). The point of this email was more to discover if anyone was using this sieve in practice for something other than education.

With regards to g6k - there is indeed an open issue about providing examples to make it easier to use (see https://github.com/fplll/g6k/issues/35). So, certainly on that issue you have a point.

Cheers,

Joe

--
You received this message because you are subscribed to the Google Groups "fplll-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to fplll-devel...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/fplll-devel/51fbf02d-ab88-4370-aa98-6a0921ff4773o%40googlegroups.com.

[Leo Ducas]

Hi Manos,

I would like to share my opinion on this. Well, I am actually using the Gauss sieve as I am

interested in its output set specifically. Hence, I am not using it to solve SVP but instead

in order to study a specific set of lattice vectors. But, that is just me and somebody could

very well argue that a similar computational task can be performed by G6K.

Indeed, G6K is designed so that this particular data can be extracted, and more. Furthermore, we mean for all potentiality useful information be accessible easily from the python layer, check for example:

https://github.com/fplll/g6k/blob/master/examples/all_short_vectors.py

Currently, the examples subfolder doesn't have that many examples, because I quickly ran out of idea for things to exemplify. If you have suggestions to improve the educational value of G6K, I would be glad to attempt to implement them, but maybe this is a discussion to have on :

https://github.com/fplll/g6k/issues/35

All the best
-- Leo

[Emmanouil Doulgerakis]

Hi Joe,

Thank you for your reply and for sharing what is the state of affairs.

I am glad that you will not remove the sieve in its entirety.

Best,

Manos

To unsubscribe from this group and stop receiving emails from it, send an email to fplll...@googlegroups.com.