File: README

package info (click to toggle)
fplll 2.1.6+20071129-2
  • links: PTS
  • area: main
  • in suites: lenny, squeeze
  • size: 1,680 kB
  • ctags: 537
  • sloc: sh: 8,816; cpp: 5,718; makefile: 57; perl: 46
file content (183 lines) | stat: -rw-r--r-- 5,161 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

OVERALL DESCRIPTION
===================

fpLLL-2.1 is distributed under the GNU General Public License (v2 or
higher) as published by the Free Software Foundation.

fpLLL-2.1  contains different  implementations of the floating-point
LLL  reduction  algorithm,   offering different     speed/guarantees
ratios. It contains a 'wrapper' choosing the estimated best sequence
of  variants in  order to provide  a   guaranteed output as  fast as
possible. In the case of the wrapper,  the succession of variants is
oblivious to the user.

DEPENDENCIES
============

.Absolutely needed:
GNU MP 4.1.0 (or higher):
http://www.swox.com/gmp/
 
.Absolutely needed:
MPFR 2.1.1 (COMPLETE INSTALLATION):
http://www.mpfr.org/

If GMP and/or MPFR include and lib files are not in the default 
directories /usr/include and /usr/lib, you have to set the 
environment variables CFLAGS and LDFLAGS for instance through 
the configure command line 
configure CPPFLAGS="-I/mpfrinclude -I/gmpinclude" LDFLAGS="-L/mpfrlib -L/gmplib"
or   
configure CPPFLAGS="-I/mpfrinclude -I/gmpinclude $CPPFLAGD" LDFLAGS="-L/mpfrlib -L/gmplib $LDFLAGS"
if these variables already exist in your environment. 
This should be modified soon for using standard --with-gmp and 
--with-mpfr package specifications.


INSTALLATION
============

To  install files  'cd'  to the  directory containing the  package's
source code and just type

 configure
 make 
 make install

You can remove the program binaries and object files from the source
code directory  by typing 'make  clean'.  To  also remove  the files
that 'configure'  created (so  you can  compile   the package  for a
different kind of computer), type 'make distclean'.
By default, 'make install' installs the package commands under
'/usr/local/bin', include files under '/usr/local/include', etc.  
You can specify an installation directory name other than 
'/usr/local' by giving 'configure' the option '--prefix=dirname'.
Run 'configure --help' for further details.

CHECK 
=====

'cd' to the src directory, and type 

 make check

This tests the LLL wrapper given dim55_in as input. If nothing is
printed during "diff foo dim55_out", the self-test has succeeded.


HOW TO USE
==========

Executable files fplll and generate are installed in the directory 
bin. In the directory src one also finds the file llldiff.

- generate is an utility for generating matrices (rows form input 
   lattice bases).

The options are :
 r <d> <b> : generates a knapsack style matrix of dimension d,d+1 and b bits.
 s <d> <b> <b2> : generates a simdioph matrix.
 u <d> <b> : generates an uniform matrix.
 n <d> <b> <q> : generates an ntru like matrix.
 m <d> <b> <q> : generates an ntru like matrix.
 a <d> <f> : generates an ajtai style matrix.

The matrix is printed in stdout.

- fplll does LLL on a matrix (considered as a set of row vectors) 
given in stdin.

The options are :

-r <size> : the number of rows, ie, of vectors (required)
-c <size> : the numbers of columns (required)

-d <delta> : delta (default=0.99)
-e <eta> : eta (default=0.51)
-p <precision> : precision of the floating-point arithmetic, works 
                 only with -f mpfr.

-f mpfr : sets the floating-point type to MPFR.
-f dpe : sets the floating-point type to DPE. (default)
-f double : sets the floating-point type to double.
-z int : sets the integer type to int.
-z mpz : sets the integer type to mpz, the integer type of GMP. (default)

-m wrapper : uses the wrapper. (default)
-m fast : uses the fast method, works only with -f double.
-m fastearly : uses the fast method with early reduction, works only 
               with -f double.
-m heuristic : uses the heuristic method.
-m heuristicearly : uses the heuristic method with early reduction.
-m proved : uses the proved version of the algorithm.


- llldiff compares two bases (b1,...,bd) and (c1,...c_d'): they are considered
equal iff d=d' and for any i, bi = +- ci.


EXAMPLES
========

1)
./generate r 10 1000 | ./fplll -r 10 -c 11 


2)
If the file 'matrix' contains 
[[ 10 11]
[11 12]]

Then 
./fplll -r 2 -c 2 < matrix
produces
[[0 1 ]
[1 0 ]
]



DIFFERENCES WITH FPLLL-1.3
==========================

Apart from technical differences (switching to C++, shifting the
matrix indices by 1, dealing automatically with triangular matrices),
the main additional ingredient is the wrapper, which provides an
efficient and guaranteed LLL for any inputs.



DEVELOPERS
===========

David Cade, david.cade@ens.fr
Damien Stehle, damien.stehle@ens-lyon.fr



ACKNOWLEDGEMENTS
================

Patrick Pelissier and Paul Zimmermann for dpe.

Martin Albrecht and Gilles Villard for the "configure/make/make install" packaging
and for the incorporation into SAGE.


Martin Albrecht, John Cannon, Laurent Fousse, Guillaume Hanrot, Willem
Jan Palenstijn, Patrick Pelissier, Allan Steel, Gilles Villard and
Paul Zimmermann for their support and for many suggestions that helped
debugging and improving this code.



NEW RELEASES AND BUG REPORTS
============================

New releases will be announced at the URL:
http://perso.ens-lyon.fr

Bug reports may be sent at:
damien.stehle@ens-lyon.fr
david.cade@ens.fr