Example / Simplified Algorithms

[lducas]

The learning curve by just looking at the implementations of pump.py or work out seems pretty steep. Worse, those are hidden in subfolders, and one may end up looking the CLI scripts to get started, which are quite discouraging with all their argument-passing magic.

A proposed solution would be to have an example folder, that contains very simplified version of the pump, workout, and a few application examples, with increasing variation and complexity on optimization tweaks. All tweakable parameters should end up being examplified with a few words on their role/effect.

[lducas]

Partially addressed in #36 . Leaving it open as I think we could have more examples.

[ManolisDoulgerakis]

Hi Leo,

Thanks for your reply in https://groups.google.com/forum/?utm_medium=email&utm_source=footer#!msg/fplll-devel/r9PucWNydxM/6HFQna-UBgAJ

and your call for suggestions in order to improve the educational value of G6K.

I will try and share my thoughts on this with the hope that they will contribute in this direction. However, I am slightly familiar with G6K which can be both an advantage and a disadvantage in this case. So, please disregard anything stupid that I might say.

What I will try to describe is a line of introducing G6K to somebody that has just started studying papers related to lattice sieving. The first thing that somebody would like to check is if the library actually works on his computer. This part I think is already solved. The next questions are

(i) Which computational tasks can it solve? (ii) By which algorithms does it solve these tasks?

These questions are partially answered in the readme file and the examples directory if I am not wrong. However, it would be nice if they received a compact and short answer, by for example providing a G6K cheat-sheet. This will be just a cheat-sheet, thus no examples included but it would provide a very clear picture for a new user of what he can compute and by what means.

Hence this cheat-sheet could include a list like

Computational tasks tackled by G6K: 1) Exact SVP 2) Approx-SVP 3) Hermite-SVP 4) LWE 5) list-SVP 6) ...

The second list could include the main lattice algorithms implemented in the library and also the ``tricks" used in order to speed them up (with references to the corresponding papers).

Hence the second list could be like:

Implemented algorithms & tweakable parameters 1) Gauss sieve 2) bgj1 3) 3-sieve 4) BKZ 5) ...

 a) dimensions-for-free 
 b) progressive-sieving
 c) nearest neighbor techniques
 d) pop-count
 e) Parallelisation options
 f) ...

Then state for each algorithm which tricks can be used (or are used by default). A nice extra feature would be to include references to G6K files (or even to lines within a file) where the main implementation of each of the above algorithms is included.

Once somebody has read the above cheat-sheet then the next step is to start running his own examples. What should be clear from an educational point of view, is for each example the user runs to know which combination of algorithms was used in order to make the requested computation (if this is possible). Also in a learning process it is important to have in mind that somebody usually starts with studying one algorithm and not an optimised combination of algorithms which gives the best performance. Hence, if G6K provides an option where the building blocks" can be usedindependently" this would be great. In other words, start from the simplest" algorithm available and then build up to morecomplicated" versions.

Then I believe two different series of examples could be made (in python level). The first could be a series of examples where each example deals with an instance of each of the computational tasks mentioned in the first list of the cheat-sheet (I think this is almost already done, but it would be nice to have all the examples collected in the examples directory and maybe also ``cite" them in the cheat-sheet). A second line of examples that could be built is the following (if it is possible). Take one specific lattice, for example by A = IntegerMatrix.from_file(input_file_name)

and then take it for a chronological tour across the evolution of the algorithms. So, the first example could be simply running the Gauss sieve and check which was the shortest vector it outputed, how much time it took, how much memory. Then the second could be running a progressive Gauss sieve and again check the same output. Then on top of that enable the dimensions-for-free algorithm. Of course one can continue in this line by doing the same for the 3-sieve and then play with the combinatorics of all available features. Thus, somehow it could provide a small ``documentary by example" of the evolution of sieving algorithms.

I hope that my suggestions will help in making G6K even easier to use and understand. As I am not aware of how the library was built I am afraid that some of my suggestions might not be practically applicable. However even in these cases I hope they will offer some food for thought.

Best, Manos

[lducas]

Hi Manos, if I understand you correctly you are essentially asking for a user manual of G6K and a survey/tutorial on lattice algorithms. This sounds great but we currently do not have the resources to contribute that. Let me know if misunderstood you suggestions.

[ManolisDoulgerakis]

Hi Leo,

Indeed, you understood correctly the high level idea. I can understand that actually creating what I suggested takes resources. I am glad though that you liked the idea. Maybe at some point in the future it will become possible to create it.

Best, Manos