Looks like we will have a very good LLL implementation sooner rather than later.
Cheers, Martin ---------- Forwarded Message ---------- Subject: Re: fpLLL Date: Thursday 04 October 2007 From: Damien STEHLE <[EMAIL PROTECTED]> To: Martin Albrecht <[EMAIL PROTECTED]> Dear Martin, Thanks for your interest in fplll. I did not know it was in the progress of being integrated to SAGE, but I am very happy of these good news. However, there are some more recent news about fplll... it has been updated this Summer into fplll-2.0, with significant changes. You have been too quick, or I have been too slow. I had a Summer internship student work on it for three months this Summer, whose name is David Cade. I am very satisfied of what he did, and fplll-2.0 is now easier to use than fplll-1.*. It is not public yet, since I am checking it these days. I was planning to have it on my webpage tomorrow :-). I attach the current tgz to this email. Here is a summary of the changes: - the major algorithmic improvement is the so-called wrapper, which chooses for the user a guess of the right sequence of variants to use, in order to finish as quick as possible, but in a reliable way. This is similar to the way the variants are chosen in Magma for the default LLL: it is oblivious to the user. - the early-reduction strategy of Allan Steel has been integrated. It consists in size-reducing vectors earlier than what would be done in the standard LLL. It corresponds to the EarlyReduction option in Magma. This is not integrated into the wrapper yet (I still do not know exactly when it is interesting to do it and when it is not). - we switched from C to C++, to simplify our lives with the wrapper. It is extremely convenient for the use of the underlying arrithmetics (integers and floating-point numbers) - we translated the matrix indices by 1: the first matrix entry is B[0][0] instead of B[1][1]... It was a bit stupid to do it with ones, and hard to correct afterwards since I was using the unused entries for other things... - automatised triangular option: the code looks at the matrix and decides how triangular it is. Some things are however missing compared to fplll-1.3: - no LLLGram anymore (by lack of time) - no llldiff anymore (same thing) - no deep insertion strategy anymore. I do not know if I will have it back, since it is not very useful. I plan to have strong lattice reduction at some point (like BKZ in NTL), and then it will be completely useless. - no LLLCheck anymore (running the default wrapper on the output provides a LLLcheck). I would like you to tell me what I should modify in fplll-2.0 to make it easier for SAGE. I plan to work on it (I do not know when, I am overloaded these days). The things I plan to do in it are the following, but it is going to take quite a while: - LLLGram and llldiff (like in fplll-1.3) - Gram-Schmidt orthogonalisation relying on Householder's algorithm rather than Cholesky's - stronger lattice reduction (in a BKZ fashion) Best regards, Damien On Thu, Oct 04, 2007 at 07:51:40AM -0400, Martin Albrecht wrote: > Damien, > > I am a developer of the GPL'd mathematics software SAGE. I am writing you > because we are incorporating your amazing fpLLL package to SAGE. That is, we > are going to ship fpLLL with SAGE and use it to compute reduced lattices. To > make this happen, I had to modify your source a bit such that we can link > against it conveniently (e.g., I separated the implementations from the main > functions, took care of symbol clashes, etc.) If you find the time, I would > appreciate if you'd consider accepting my changes (or something in the same > spirit) upstream. I have uploaded my modified package to > > http://sage.math.washington.edu/home/malb/pkgs/fplll.tar.gz > > (it needs some clean up, but should give you an idea). If you are interested > in our integration and LLL efforts, the progress can be monitored at > > http://trac.sagemath.org/sage_trac/ticket/723 > > and we have some notes at > > http://wiki.sagemath.org/days5/proj/lll > > on stuff we need to do. So far we lack any heuristic which LLL to choose which > we want to change eventually. If you have any comments about this, please > feel very welcome to make them. > > Thank you very much for writing this amazing piece of software! If you have > any comments, questions or objections about our integration please feel > encouraged to share them with us! You can do this either by replying to me/us > or by writing yo [email protected] . Btw. the SAGE website is at > http://www.sagemath.org . > > Best, > Martin ------------------------------------------------------- -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _www: http://www.informatik.uni-bremen.de/~malb _jab: [EMAIL PROTECTED] --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
