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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<title>fplll 4.0</title>
</head>
<body>
<h1>fplll 4.0</h1>
<ul>
<li><a href="#Overall description">Overall description</a>
<li><a href="#Dependencies">Dependencies</a>
<li><a href="#Installation">Installation</a>
<li><a href="#Check">Check</a>
<li><a href="#How to use">How to use</a>
<ul>
<li><a href="#latticegen">latticegen</a>
<li><a href="#fplll">fplll</a>
<li><a href="#llldiff">llldiff</a>
</ul>
<li><a href="#How to use as a library">How to use as a library</a>
<ul>
<li><a href="#Functions">Functions</a>
<ul>
<li><a href="#LLL">LLL</a>
<li><a href="#BKZ">BKZ</a>
<li><a href="#SVP">SVP</a>
</ul>
<li><a href="#Data types">Data types</a>
</ul>
<li><a href="#Examples">Examples</a>
<li><a href="#Developers">Developers</a>
<li><a href="#Acknowledgements">Acknowledgements</a>
<li><a href="#New releases and bug reports">New releases and bug reports</a>
</ul>
<h2 id="Overall description">Overall description</h2>
<p>fplll is distributed under the <a href="COPYING">GNU Lesser General
Public License</a> (either version 2.1 of the License, or, at your option, any later version)
as published by the Free Software Foundation.</p>
<p>fplll contains several algorithms on lattices that rely on
floating-point computations. This includes 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. It also includes
a rigorous floating-point implementation of the Kannan-Fincke-Pohst
algorithm that finds a shortest non-zero lattice vector, and the
BKZ reduction algorithm.</p>
<h2 id="Dependencies">Dependencies</h2>
<p>Absolutely needed:
<ul>
<li>GNU MP 4.2.0 or higher (<a href="http://gmplib.org/">http://gmplib.org/</a>)
<li>MPFR 2.3.0 or higher, COMPLETE INSTALLATION
(<a href="http://www.mpfr.org/">http://www.mpfr.org/</a>)
</ul>
<p>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
<pre>configure CPPFLAGS="-I/mpfrinclude -I/gmpinclude" LDFLAGS="-L/mpfrlib -L/gmplib"</pre>
or
<pre>configure CPPFLAGS="-I/mpfrinclude -I/gmpinclude $CPPFLAGD" LDFLAGS="-L/mpfrlib -L/gmplib $LDFLAGS"</pre>
if these variables already exist in your environment.
This should be modified soon for using standard --with-gmp and
--with-mpfr package specifications.</p>
<h2 id="Installation">Installation</h2>
<p>To install files 'cd' to the directory containing the package's
source code and just type</p>
<pre>
./configure
make
make install # (as root)
</pre>
<p>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.</p>
<h2 id="Check">Check</h2>
'cd' to the src directory, and type
<pre>
make check
</pre>
This tests the LLL wrapper given dim55_in as input. If the error message
'INVALID RESULT' is not printed, the self-test has succeeded.
<h2 id="How to use">How to use</h2>
<p>Executable files fplll and latticegen are installed in the directory
bin. If you type 'make check', it will also generate the file llldiff.
(Note that the programs generated by make in the 'src/' directory are
only wrappers to the programs in 'src/.libs/)</p>
<h3 id="latticegen">latticegen</h3>
<p>latticegen is an utility for generating matrices (rows form input
lattice bases).</p>
<p>The options are :
<ul>
<li>r <d> <b> : generates a knapsack style matrix of dimension d,d+1 and b bits.
<li>s <d> <b> <b2> : generates a simdioph matrix.
<li>u <d> <b> : generates an uniform matrix.
<li>n <d> <b> <q> : generates an ntru like matrix.
<li>N <d> <b> <q> : generates an ntru like matrix.
<li>a <d> <f> : generates an ajtai style matrix.
<li>A <d> : generates an ajtai style matrix. Also requires d coefficients.
</ul></p>
<p>The matrix is printed in stdout.</p>
<p>Note that by default, the random bits always use the same seed,
to ensure reproducibility. You can change the seed with the option
<pre> -randseed <integer></pre>
or use the current time (in seconds)
<pre> -randseed time</pre>
If you use this option, it must be the first one on the command line.</p>
<h3 id="fplll">fplll</h3>
<p>fplll does LLL, BKZ or SVP on a matrix (considered as a set of row
vectors) given in stdin or in a file as parameter.</p>
<p>The options are:</p>
<pre>
-a lll : LLL-reduction (default).
-a bkz : BKZ-reduction.
-a svp : print a shortest vector of the lattice.
-r <size>, -c <size> : ignored, provided for compatibility with previous
versions of fplll.
</pre>
<p>Options for LLL-reduction:</p>
<pre>
-d <delta> : delta (default=0.99)
-e <eta> : eta (default=0.51)
-l <lovasz> : if !=0 Lovasz's condition. Otherwise, Siegel's condition (default: Lovasz)
-p <precision> : precision of the floating-point arithmetic, works
only with -f mpfr.
-f mpfr : sets the floating-point type to MPFR (default if m=proved).
-f dpe : sets the floating-point type to DPE (default if m=heuristic/heuristicearly).
-f double : sets the floating-point type to double (default if m=fast/fastearly).
-f longdouble : sets the floating-point type to long double.
-z int : sets the integer type to int.
-z mpz : sets the integer type to mpz, the integer type of GMP (default).
-z double : sets the integer type to double.
-m wrapper : uses the wrapper. (default if z=mpz)
-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.
With the wrapper or the proved version, it is guaranteed that the basis is
LLL-reduced with delta'=2*delta-1 and eta'=2*eta-1/2. For instance, with the
default options, it is guaranteed that the basis is (0.98,0.52)-LLL-reduced.
</pre>
<p>Options for BKZ-reduction:</p>
<pre>
-b <blocksize> Block size, mandatory, between 2 and the number of rows.
-f <float_type> Same as LLL (-p is required if float_type=mpfr)
-p <precision> Precision of the floating-point arithmetic with -f mpfr
-bkzmaxloops <loops> Maximum number of full loops.
-bkzmaxtime <time> Stop after <i>time</i> seconds (up to loop completion).
-bkzautoabort Heuristic, stop when the average slope of log(||b_i*||)
does not decrease fast enough.
</pre>
<h3 id="llldiff">llldiff</h3>
<p>llldiff compares two bases (b1,...,bd) and (c1,...c_d'): they are considered
equal iff d=d' and for any i, bi = +- ci.</p>
<h2 id="How to use as a library">How to use as a library</h2>
<p>At the beginning of your code, type:
<pre>
#include <fplll.h>
using namespace fplll;
</pre>
</p>
<p>See the example file test.cpp in the src directory.
To compile it, assuming fplll has been installed in /tmp/fplll:</p>
<pre>
bash-3.00$ g++ -static -I /tmp/fplll/include test.cpp -L /tmp/fplll/lib -lfplll -lmpfr -lgmp
bash-3.00$ ./a.out
[[4 3 7]
[3 0 1]
[3 5 3]]
[[3 0 1]
[2 2 -3]
[0 5 2]]
</pre>
All types, functions and constants are wrapped in the <code>fplll</code> namespace, with the exception of the <code>dpe</code> type defined in dpe.h. Preprocessor definitions prefixed by FPLLL_ are reserved for internal use.
<h3 id="Functions">Functions</h3>
<h4 id="LLL">LLL</h4>
<table cellpadding="5">
<tr><td><tt>int lllReduction(ZZ_mat<mpz_t>& b, double delta =
0.99, double eta = 0.51, LLLMethod method = LM_WRAPPER,
FloatType floatType = FT_DEFAULT, int precision = 0, int flags =
LLL_DEFAULT)</tt><br>
<p>LLL-reduces a basis of Z_NR<mpz_t>.</p>
<p>It is guaranteed that the output is (delta', eta')-LLL-reduced with delta'=2×delta-1, eta'=2×eta-1/2 provided that
method=LM_WRAPPER/LM_PROVED, floatType=FT_DEFAULT and precision=0. For instance, with the default parameters, it is
guaranteed that the output basis is (0.98, 0.52)-LLL-reduced.</p>
<p>Parameters:</p>
<blockquote>
<dl>
<dt><code>b</code>
<dd>Input basis. It is reduced in place.</dd>
<dt><code>delta</code>
<dd>Relaxation factor in the Lovász condition. Must be greater than 1/4 and lower than 1.
<dt><code>eta</code>
<dd>Relaxation factor in the size reduction. Must be greater that 1/2 and lower than sqrt(delta).
<dt><code>method</code>
<dd>One of the following values:
<table cellpadding="3">
<tr><td>LM_WRAPPER<td>Tries to reduce the matrix with a combination of the following methods with increasing precision. Then, runs the proved version with the default precision. floatType must be FT_DEFAULT and precision must be 0. The result is guaranteed (see above).
<tr><td>LM_PROVED<td>Proved method. Uses integers to compute dot products. The result is guaranteed if floatType=FT_DEFAULT/FT_MPFR and precision=0 (see above).
<tr><td>LM_HEURISTIC<td>Heuristic method. Uses floating-point numbers to compute dot products. The result is not guaranteed. It is more efficient that the proved version when the coefficients of the input are large (the threshold depends on the floating-point type and precision).
<tr><td>LM_FAST<td>Same as LM_HEURISTIC with floatType=FT_DOUBLE, with a special trick to handle larger inputs.
</table>
<dt><code>floatType</code>
<dd>Possibles values are:
<table cellpadding="3" border style="border-collapse:collapse;">
<tr><td><td>LM_WRAPPER<td>LM_PROVED<td>LM_HEURISTIC<td>LM_FAST
<tr><td>FT_DEFAULT<td>yes<td>yes<br>same as FT_MPFR<td>yes<br>same as FT_DPE<td>yes<br>same as FT_DOUBLE
<tr><td>FT_DOUBLE<td>no<td>yes<td>yes<td>yes
<tr><td>FT_DPE<td>no<td>yes<td>yes<td>no
<tr><td>FT_MPFR<td>no<td>yes<td>yes<td>no
</table>
<dt><code>precision</code>
<dd>If floatType is not FP_MPFR, this parameter must be zero. If floatType is FP_MPFR,
<ul>
<li>if this parameter is zero, the precision of floating-point computation is the one required to ensure that the proved method returns a correct result (note that if the heuristic method is used with this precision, nothing is guaranteed);
<li>if this parameter is larger than or equal to 53, it forces the precision in floating-point computations.
</ul>
<dt><code>flags</code>
<dd>Can be LLL_DEFAULT or a combination of the following values:
<table cellpadding="3">
<tr><td>LLL_VERBOSE<td>Displays information on stderr.
<tr><td>LLL_EARLY_RED<td>Enables early reduction. This might be faster on (nearly) lower triangular matrices. Currently, this flag is not compatible with the proved method.
<tr><td>LLL_SIEGEL<td>Uses Siegel condition instead of Lovász condition.
</table>
</dl>
</blockquote>
<p>Return value:</p>
<blockquote>
<table cellpadding="3">
<tr><td>RED_SUCCESS<td>Success.
<tr><td>RED_BABAI_FAILURE<td>Error.
<tr><td>RED_LLL_FAILURE<td>Error: infinite loop in LLL.
<tr><td>Any other value<td>Error.
</table>
<p>Even if an error occurs, it is guaranteed that <code>b</code> remains a basis of the same lattice.</p>
</blockquote>
<tr><td><tt>int lllReduction(ZZ_mat<long>& b, double delta =
0.99, double eta = 0.51, LLLMethod method = LM_FAST,
FloatType floatType = FT_DEFAULT, int precision = 0, int flags =
LLL_DEFAULT)</tt><br>
LLL-reduces a basis of Z_NR<long>. There is no guarantee and the LM_WRAPPER method is not available.
<tr><td><tt>int lllReduction(ZZ_mat<double>& b, double delta =
0.99, double eta = 0.51, LLLMethod method = LM_FAST,
FloatType floatType = FT_DEFAULT, int precision = 0, int flags =
LLL_DEFAULT)</tt><br>
LLL-reduces a basis of Z_NR<double>. There is no guarantee and the LM_WRAPPER method is not available.
<h4 id="BKZ">BKZ</h4>
<table cellpadding="5">
<tr><td><tt>int bkzReduction(IntMatrix& b, int blockSize, int flags = BKZ_DEFAULT)
</tt><br>
<p>BKZ-reduces a basis of Integers.</p>
<p>Parameters:</p>
<blockquote>
<dl>
<dt><code>b</code>
<dd>Input basis. It is reduced in place.</dd>
<dt><code>blockSize</code>
<dd>Controls the strength of the reduction (as low as LLL if blockSize=2, as high as HKZ when blockSize=b.getRows()).
<dt><code>flags</code>
<dd>Can be BKZ_DEFAULT or a combination of the following values:
<table cellpadding="3">
<tr><td>BKZ_VERBOSE<td>Displays information on stderr.
<tr><td>BKZ_NO_LLL<td>Assumes that the input basis is already LLL-reduced (otherwise, an LLL-reduction is performed with the LLL wrapper to avoid numerical problems)
<!-- <tr><td>BKZ_AUTO_ABORT<td> -->
</table>
</dl>
</blockquote>
<p>Return value:</p>
<blockquote>
<table cellpadding="3">
<tr><td>RED_SUCCESS<td>Success.
<tr><td>RED_BABAI_FAILURE<td>Error in the semi-reduction subroutine.
<tr><td>RED_LLL_FAILURE<td>Error: infinite loop in the LLL subroutine.
<tr><td>RED_ENUM_FAILURE<td>Error in the SVP subroutine.
<tr><td>RED_BKZ_FAILURE<td>Error in BKZ.
<tr><td>RED_BKZ_TIME_LIMIT<td>Time limit exceeded in BKZ.
<tr><td>RED_BKZ_LOOPS_LIMIT<td>Maximum number of loops exceeded in BKZ.
<tr><td>Any other value<td>Error.
</table>
<p>Even if an error occurs, it is guaranteed that <code>b</code> remains a basis of the same lattice.</p>
</blockquote>
<tr><td><tt>int bkzReduction(IntMatrix& b, IntMatrix& u, int blockSize, int flags = BKZ_DEFAULT)</tt><br>
Same as above, but also computes the transform matrix u such that b<sub>new</sub> = u × b<sub>old</sub>.
<tr><td><tt>int bkzReduction(const BKZParam& param)</tt><br>
<p>Same as above with more options.</p>
<p>Fields of BKZParam:</p>
<blockquote>
<pre>
struct BKZParam {
BKZParam() : b(NULL), u(NULL), blockSize(0), delta(LLL_DEF_DELTA),
floatType(FT_DEFAULT), precision(0), flags(BKZ_DEFAULT),
maxLoops(0), maxTime(0) {}
IntMatrix* b;
IntMatrix* u;
int blockSize;
double delta;
FloatType floatType;
int precision;
int flags;
int maxLoops;
double maxTime;
vector<double> pruning;
};
</pre>
<dl>
<dt><code>b</code>
<dd>Pointer to the matrix to reduce in place.</dd>
<dt><code>u</code>
<dd>Pointer to the transform matrix (can be null if not needed).</dd>
<dt><code>blockSize</code>
<dd>Between 2 and b.getRows(), controls the strength of the reduction.
<dt><code>delta</code>
<dd>Used by the LLL subroutine.
<dt><code>floatType</code>
<dd>Internal data type for floating-point computations (FT_DEFAULT, FT_DOUBLE, FT_LONG_DOUBLE, FT_DPE or FT_MPFR). FT_DEFAULT is currently equivalent to FT_DOUBLE.
<dt><code>precision</code>
<dd>Internal precision of floating-point computations when floatType = FT_MPFR.
<dt><code>flags</code>
<dd>Can be BKZ_DEFAULT or a combination of the following values:
<table cellpadding="3">
<tr><td>BKZ_VERBOSE<td>Displays information on stderr.
<tr><td>BKZ_NO_LLL<td>Assumes that the input basis is already LLL-reduced (otherwise, an LLL-reduction is performed with the LLL wrapper to avoid numerical problems)
<tr><td>BKZ_MAX_LOOPS<td>Enable parameter maxLoops.
<tr><td>BKZ_MAX_TIME<td>Enable parameter maxTime.
<!-- <tr><td>BKZ_AUTO_ABORT<td> -->
</table>
<dt><code>maxLoops</code>
<dd>Forced stop after <i>maxLoops</i> loops (enabled by the BKZ_MAX_LOOPS flag).
<dt><code>maxTime</code>
<dd>Forced stop after around maxTime seconds (enabled by the BKZ_MAX_TIME flag, the condition is checked only after each full loop).
<dt><code>pruning</code>
<dd>Vector of size <i>blockSize</i> that enables heuristic speed-up of the enumeration subroutine.
If not empty, it must contain <i>blockSize</i> values in the interval (0,1], starting with 1, in non-increasing order.
</dl>
</blockquote>
<p>Return value: Same as above.</p>
</table>
<h4 id="SVP">SVP</h4>
<table>
<tr><td><tt>int shortestVector(IntMatrix& b, vector<Integer>&
solCoord, SVPMethod method = SVPM_PROVED, int flags = SVP_DEFAULT)</tt><br>
<p>Computes a shortest non-zero vector of a lattice.
The basis must be LLL-reduced with delta = 0.99 and eta = 0.51.
The result is guaranteed if method = SVPM_PROVED.</p>
<p>Parameters</p>
<blockquote>
<dl>
<dt>b
<dd>LLL-reduced input basis.</dd>
<dt>solCoord
<dd>Output: coordinates of a shortest vector non-zero of L(b) in the basis <code>b</code>.
<dt>method
<dd>SVPM_PROVED (the result is guaranteed provided that the basis is (0.99,0.51)-LLL-reduced) or SVPM_FAST (nothing is guaranteed).
<dt>flags
<dd>SVP_DEFAULT or SVP_VERBOSE (displays information on stderr).
</dl>
</blockquote>
<p>Return value:</p>
<blockquote>
<table cellpadding="3">
<tr><td>RED_SUCCESS<td>Success.
<tr><td>RED_ENUM_FAILURE<td>Error: no solution found.
<tr><td>Any other value<td>Error.
</table>
</blockquote>
</table>
<h3 id="Data types">Data types</h3>
<h4>Z_NR<Z></h4>
<p>Z_NR stores integers. This template provides a uniform interface for doing
integer computations with several underlying types (long, double and
mpz_t).</p>
<p>Methods:</p>
<table cellpadding="5">
<tr><td><tt>Z_NR()</tt><br>
Default constructor. The initial value is undefined.
<tr><td><tt>Z_NR(const Z_NR<Z>& x)</tt><br>
Copy constructor.
<tr><td><tt>~Z_NR<Z>()</tt><br>
Destructor.
<tr><td><tt>double get_d() const</tt><br>
Converts this object to a double. If it does not fit in a double, the result is undefined.
<tr><td><tt>double get_d_2exp(long* expo) const</tt><br>
Computes expo such value 2^(expo-1) <= value < 2^expo and returns
value / 2^expo. This means that expo = floor(log2(value)) - 1. If the value of
this object is zero, returns 0 and sets expo = 0.
<tr><td><tt>long get_si() const</tt><br>
Converts this object to a long. If it does not fit in a long, the result is undefined.
<tr><td><tt>template<class F> void set_f(const FP_NR<F>& x)</tt><br>
Sets the value to x. When F=mpfr_t, x is rounded to the nearest integer and if
the fractional part of x is 0.5, the even integer is chosen when. Otherwise,
the rounding direction is undefined.
<tr><td><tt>void set_str(const char* s)</tt><br>
Sets the value to s, signed integer in basis 10.
<tr><td><tt>void operator=(const Z_NR<Z>& x)</tt><br>
<tt>void operator=(long x)</tt><br>
Sets the value to x.
<tr><td><tt>int cmp(const Z_NR<Z>& x) const</tt><br>
3-way comparison. Returns a positive number if *this > x, a negative number if
*this < x or zero is *this == x.
<tr><td><tt>int sgn() const</tt><br>
Sign. Returns a positive number, a negative number or zero if the value of
this object is respectively positive, negative or null.
<tr><td><tt>inline bool operator<(const Z_NR<Z>& x) const</tt><br>
<tt>inline bool operator>(const Z_NR<Z>& x) const</tt><br>
<tt>inline bool operator<=(const Z_NR<Z>& x) const</tt><br>
<tt>inline bool operator>=(const Z_NR<Z>& x) const</tt><br>
<tt>inline bool operator==(const Z_NR<Z>& x) const</tt><br>
<tt>inline bool operator!=(const Z_NR<Z>& x) const</tt><br>
<tt>inline bool operator<(long x) const</tt><br>
<tt>inline bool operator>(long x) const</tt><br>
<tt>inline bool operator<=(long x) const</tt><br>
<tt>inline bool operator>=(long x) const</tt><br>
<tt>inline bool operator==(long x) const</tt><br>
<tt>inline bool operator!=(long x) const</tt><br>
Comparison operators.
<tr><td><tt>void add(const Z_NR<Z>& x, const Z_NR<Z>& y)<br>
void sub(const Z_NR<Z>& x, const Z_NR<Z>& y)<br>
<!--void neg(const Z_NR<Z>& x)<br>-->
void mul(const Z_NR<Z>& x, const Z_NR<Z>& y)<br>
void mul_si(const Z_NR<Z>& x, long y);<br>
void abs(const Z_NR<Z>& x)</tt><br>
Sets the value of this object to x + y, x - y<!--, -x-->, x × y, x × y,
or |x| (respectively).
<tr><td><tt>void addmul(const Z_NR<Z>& x, const Z_NR<Z>& y)</tt><br>
Adds x × y to the current value.
<tr><td><tt>void submul(const Z_NR<Z>& x, const Z_NR<Z>& y)</tt><br>
Subtracts x × y from the current value.
<tr><td><tt>void swap(Z_NR<Z>& a)</tt><br>
Efficiently swaps the values of two Z_NR.
<tr><td><tt>T& getData()</tt><br>
<tt>const T& getData() const</tt><br>
Returns the internal representation of the data.
</table>
<p>Non-member functions:</p>
<table cellpadding="5">
<tr><td><tt>template <class Z><br>ostream& operator<<(ostream& os, const Z_NR<Z>& x)</tt><br>
Prints x on stream <code>os</code>.
<tr><td><tt>template <class Z><br>istream& operator>>(istream& is, Z_NR<Z>& x)</tt><br>
Reads x from stream <code>is</code>.
</table>
<p>Containers:</p>
<p><tt>typedef Z_NR<mpz_t> Integer;</tt><br>
<tt>typedef std::vector<Integer> IntVect;<br>
typedef ZZ_mat<mpz_t> IntMatrix;</tt></p>
<h4>FP_NR<F></h4>
<p>FP_NR stores floating-point numbers. This template provides a uniform
interface for doing floating-point computations with several underlying
types (double, dpe_t and mpfr_t). For all functions, the rounding mode rnd
is ignored unless F=mpfr_t.</p>
<p>Methods:</p>
<table cellpadding="5">
<tr><td><tt>FP_NR()</tt><br>
Default constructor. The initial value is undefined.
<tr><td><tt>FP_NR(const FP_NR<F>& x)</tt><br>
Copy constructor.
<tr><td><tt>~FP_NR<F>()</tt><br>
Destructor.
<tr><td><tt>double get_d() const</tt><br>
Converts this object to a double. If it does not fit in a double, the result is
undefined.
<tr><td><tt>long get_si() const</tt><br>
Converts this object to a long. The rounding direction is undefined. If it does
not fit in a long, the result is undefined.
<tr><td><tt>template<class Z> void set_z(const Z_NR<Z>& x, mp_rnd_t rnd = GMP_RNDN)</tt><br>
Sets the value to x.
<tr><td><tt>void operator=(const FP_NR<F>& x)</tt><br>
<tt>void operator=(double x)</tt><br>
Sets the value to x.
<tr><td><tt>int cmp(const FP_NR<F>& x) const</tt><br>
<tt>int cmp(double x) const</tt><br>
3-way comparison. Returns a positive number if *this > x, a negative number if *this < x or zero is *this == x.
<tr><td><tt>int sgn() const</tt><br>
Sign. Returns a positive number, a negative number or zero if the value of this
object is respectively positive, negative or null.
<tr><td><tt>inline bool operator<(const FP_NR<F>& x) const</tt><br>
<tt>inline bool operator>(const FP_NR<F>& x) const</tt><br>
<tt>inline bool operator<=(const FP_NR<F>& x) const</tt><br>
<tt>inline bool operator>=(const FP_NR<F>& x) const</tt><br>
<tt>inline bool operator<(double x) const</tt><br>
<tt>inline bool operator>(double x) const</tt><br>
<tt>inline bool operator<=(double x) const</tt><br>
<tt>inline bool operator>=(double x) const</tt><br>
Comparison operators.
<tr><td><tt>void add(const FP_NR<F>& x, const FP_NR<F>& y, mp_rnd_t rnd = GMP_RNDN)<br>
void sub(const FP_NR<F>& x, const FP_NR<F>& y, mp_rnd_t rnd = GMP_RNDN)<br>
void neg(const FP_NR<F>& x)<br>
void mul(const FP_NR<F>& x, const FP_NR<F>& y, mp_rnd_t rnd = GMP_RNDN)<br>
void mul_2si(const FP_NR<F>& x, int c);<br>
void div(const FP_NR<F>& x, const FP_NR<F>& y, mp_rnd_t rnd = GMP_RNDN)<br>
void sqrt(const FP_NR<F>& x, mp_rnd_t rnd = GMP_RNDN)<br>
void pow_si(const FP_NR<F>& x, long c, mp_rnd_t rnd = GMP_RNDN)<br>
void exponential(const FP_NR<F>& x, mp_rnd_t rnd = GMP_RNDN)<br>
void log(const FP_NR<F>& x, mp_rnd_t rnd = GMP_RNDN)<br>
void abs(const FP_NR<F>& x)<br>
void rnd(const FP_NR<F>& x);<br>
void floor(const FP_NR<F>& x);</tt><br>
Sets the value of this object to x + y, x - y, -x, x × y, x × 2<sup>c</sup>, x / y, square root of x, x<sup>c</sup>, exponential of x, natural logarithm of x, |x|, x rounded to the nearest integer, largest integer not greater than x (respectively).
<tr><td><tt>void addmul(const FP_NR<F>& x, const FP_NR<F>& y, mp_rnd_t rnd = GMP_RNDN)</tt><br>
Adds x × y to the current value.
<tr><td><tt>void submul(const FP_NR<F>& x, const FP_NR<F>& y, mp_rnd_t rnd = GMP_RNDN)</tt><br>
Subtracts x × y from the current value.
<tr><td><tt>int zero_p() const</tt><br>
Returns non-zero if the current value is zero, 0 otherwise.
<tr><td><tt>void set_nan()</tt><br>
value := NaN.
<tr><td><tt>int is_nan() const</tt><br>
Returns non-zero if the current value is NaN, 0 otherwise.
<tr><td><tt>void swap(FP_NR<F>& x)</tt><br>
Efficiently swaps the values of two FP_NR.
<tr><td><tt>T& getData()</tt><br>
<tt>const T& getData() const</tt><br>
Returns the internal representation of the data.
</table>
<p>Static members:</p>
<table cellpadding="5">
<tr><td><tt>static unsigned int getprec()</tt><br>
Returns the current precision for new FP_NR<F> objects.
<tr><td><tt>static inline unsigned int setprec(unsigned int prec)</tt><br>
Sets the precision of new FP_NR<F> objects. Returns the previous value.
This has no effect is F != mpfr_t.
</table>
<p>Non-member functions:</p>
<table cellpadding="5">
<tr><td><tt>template <class F><br>ostream& operator<<(ostream& os, const FP_NR<F>& x)</tt><br>
Prints x on stream os.
</table>
<p>Containers:</p>
<p><tt>typedef FP_NR<mpfr_t> Float;</tt><br>
<tt>typedef std::vector<Float> FloatVect;<br>
typedef FP_mat<mpfr_t> FloatMatrix;</tt></p>
<h4>Matrix<T></h4>
<p>Methods:</p>
<table cellpadding="5">
<tr><td><tt>Matrix()</tt><br>
Creates an empty matrix (0 × 0).
<tr><td><tt>Matrix(int rows, int cols)</tt><br>
Creates a matrix of dimensions rows × cols. All elements are initialized with the default constructor of T.
<tr><td><tt>void clear()</tt><br>
Sets number of rows and the number of columns to 0.
<tr><td><tt>void resize(int rows, int cols)</tt><br>
Sets the dimensions of the matrix, preserving as much as possible of the content. The content of new cells is undefined.
<tr><td><tt>void setRows(int rows)</tt><br>
Sets the number of rows (content is not erased except for deleted rows).
<tr><td><tt>void setCols(int cols)</tt><br>
Sets the number of columns (content is not erased except for deleted columns).
<tr><td><tt>template<class U> void fill(U value)</tt><br>
Fills the matrix with a given value.
<tr><td><tt>void swap(Matrix<T>& m)</tt><br>
Efficiently swaps two matrices.
<tr><td><tt>int getRows() const</tt><br>
Returns the number of rows.
<tr><td><tt>int getCols() const</tt><br>
Returns the number of columns.
<tr><td><tt>T& operator()(int i, int j)</tt><br>
<tt>const T& operator()(int i, int j)</tt><br>
Returns a reference to a coefficient of the matrix.
<tr><td><tt>MatrixRow<T> operator[](int i)</tt><br>
<tt>const MatrixRow<T> operator[](int i) const</tt><br>
Returns a MatrixRow object pointing to the i-th row of the matrix.
</table>
<p>Non-member functions:</p>
<table cellpadding="5">
<tr><td><tt>template<class T> ostream& operator<<(ostream& os, const Matrix<T>& m)</tt><br>
Prints matrix m on stream <code>os</code>.
<tr><td><tt>template<class T> istream& operator>>(istream& is, Matrix<T>& m)</tt><br>
Reads matrix m from stream <code>is</code>.
</table>
<p>Note: a call to <tt>clear</tt>, <tt>resize</tt>, <tt>setRows</tt>,
<tt>setCols</tt> or <tt>swap</tt> invalidates all references returned by
operator() and MatrixRow objects returned by operator[].</p>
<h4>MatrixRow<T></h4>
<p>MatrixRow stores a reference to a row of a Matrix. It supports a subset
of operations available on vectors.</p>
<p>Methods:</p>
<table cellpadding="5">
<tr><td><tt>T& operator[](int i)</tt><br>
<tt>const T& operator[](int i) const</tt><br>
Returns a reference to the i-th element of this row.
<tr><td><tt>int size() const</tt><br>
Returns the number of columns.
</table>
<p>Non-member functions:</p>
<table cellpadding="5">
<tr><td><tt>template<class T> ostream& operator<<(ostream& os, const MatrixRow<T>& mr)</tt><br>
Prints mr on stream os.
</table>
<h4>ZZ_mat<ZT></h4>
<p>Base class: Matrix<Z_NR<ZT>></p>
<p>Matrix of integers. Same constructors as Matrix.</p>
<h4>FP_mat<FT></h4>
<p>Base class: Matrix<FP_NR<FT>></p>
<p>Matrix of floating-point nubmers. Same constructors as Matrix.</p>
<h3>See also</h3>
<a href="http://www.sgi.com/tech/stl/Vector.html">Documentation of std::vector</a>
<h2 id="Examples">Examples</h2>
<pre>
1)
./latticegen r 10 1000 | ./fplll
2)
If the file 'matrix' contains
[[ 10 11]
[11 12]]
Then
./fplll matrix
produces
[[0 1 ]
[1 0 ]
]
3) Random generator
./latticegen -randseed 1234 r 10 1000 | ./fplll
./latticegen -randseed time u 10 16 | ./fplll
4) Solving SVP
./latticegen r 30 3000 | ./fplll -a svp
</pre>
<h2 id="Developers">Developers</h2>
<p><b>Current developer:</b><br />
Damien Stehle, damien.stehle@gmail.com</p>
<p><b>Former developers:</b><br />
David Cade, david.cade@ens.fr <br>
Xavier Pujol, xavier.pujol@ens-lyon.org<br />
<h2 id="Acknowledgements">Acknowledgements</h2>
<p>Patrick Pelissier and Paul Zimmermann for dpe.</p>
<p>Martin Albrecht, Sylvain Chevillard, Christoph
Lauter and Gilles Villard for the
"configure/make/make install" packaging.</p>
<p>Martin Albrecht for the incorporation into SAGE.</p>
<p>Timothy Abbott, Michael Abshoff, Martin Albrecht, Bill Allombert,
John Cannon, Sylvain Chevillard, Julien Clement, Andreas Enge,
Jean-Pierre Flori, Laurent Fousse, Guillaume Hanrot, Jens Hermans,
Jerry James, Christoph Lauter, Andrew Novocin, Willem Jan Palenstijn,
Patrick Pelissier, Michael Schneider, Thiemo Seufer, Allan Steel,
Gilles Villard and Paul Zimmermann for their support and for many
suggestions that helped debugging and improving this code.</p>
<h2 id="New releases and bug reports">New releases and bug reports</h2>
<p>New releases will be announced at the URL:
<a href="http://perso.ens-lyon.fr/damien.stehle/fplll/">http://perso.ens-lyon.fr/damien.stehle/fplll/</a>
<p>Bug reports may be sent at:
<ul>
<li><a href="mailto:damien.stehle@gmail.com">damien.stehle@gmail.com</a>
</ul></p>
|
