[GSOC] LLL Project references

[Bill Hart]

Below are some references and resources for the LLL algorithm:

* By far the best book on the LLL algorithm that I am aware of is:

http://www.springer.com/computer/security+and+cryptology/book/978-3-642-02294-4

In particular, chapter 2 gives the definitions of reduction that we will be using for the project.

N.B: DO ***NOT*** BUY THIS BOOK UNLESS YOUR PROJECT IS ACCEPTED!! YOU WILL NOT NEED IT TO PREPARE YOUR APPLICATION.

However, if you can get it in your library, or on interlibrary loan, by all means get hold of a copy.

* A very nice description of the LLL algorithm (delta reduction only) is here:

http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/lll.pdf

Use this as a starting point.

* Here is another:

http://cseweb.ucsd.edu/classes/wi12/cse206A-a/lec3.pdf

* Section 1.3 of this thesis is also useful:

http://user.math.uzh.ch/dehaye/thesis_students/Karin%20Peter-The_LLL_algorithm_and_its_applications.pdf

The thesis also contains information about various applications of the LLL.

* This set of slides refers to different notions of reduced, including c-reduction, which is one of the parameters we will want our final LLL algorithm to have:

https://cs.uwaterloo.ca/~cbright/LLL.pdf

* The implementation of LLL that is closest to what we are after is fpLLL:

http://perso.ens-lyon.fr/damien.stehle/#software

* Here is a very nice paper describing the delta-epsilon reduction (there are actually three parameters, alpha, delta, epsilon, but one is dependent on the other two), and the floating point LLL. When you understand the basics, this is the paper you want to refer to:

http://perso.ens-lyon.fr/damien.stehle/downloads/LLL25.pdf

It also describes the L^2 algorithm, which we basically want to implement.

* There's a serious implementation of LLL in Victor Shoup's NTL. However whilst there are some good ideas in that, it isn't quite what we want to implement.

http://www.shoup.net/ntl/doc/LLL.txt

* Also see the implementation in flint-1.6:

http://flintlib.org/downloads.html

Start by getting to know the original LLL algorithm and some of its applications. Then start to learn a little bit more about the more sophisticated algorithms.

Here are some questions that need some serious thought:

* What floating point types should we use?

-- GMP's mpf? (see http://gmplib.org) Do we need exact (IEEE) rounding?

-- doubles?

-- MPFR's mpfr_t's? (see http://mpfr.org/)

-- extended precision types? 

N.B: we do NOT want to use long doubles, quad doubles or the like in flint.

* What integer types should we use?

-- flint fmpz's?

-- C longs/unsigned longs?

-- integers represented exactly in floating point?

* What flint modules should be added?

* Eventually we want to also look at LLL with removal, heuristic LLL and ULLL. But I suggest leaving an understanding of these until after the application process, as they are quite involved. But you should mention that implementing these is an aim of the project.

Bill.

[Curtis Bright]

Incidentally, the first time I used flint I made a simple implementation using fmpq_mat (basically as a way of getting acquainted with flint by implementing an algorithm I knew well).  Everything was done naively, but I figure it might make a good reference too: https://github.com/curtisbright/flint2/blob/774c241f360cc8234043469af76be6bfb4390f74/lll/lll.c

Curtis

--
 
---
You received this message because you are subscribed to the Google Groups "flint-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to flint-devel...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Bill Hart]

Thanks Curtis, that's fantastic!

Bill.

[Curtis Bright]

Completely forgot; back when I was learning L^2 I did an implementation using GMP's mpf.  This predates FLINT, but it was no problem to make a FLINT wrapper.  No idea if this will be of use to anyone, but I figure it won't hurt to post it: https://github.com/curtisbright/flint2/blob/naive-lll/lll/ll.c

Curtis