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
|
