1 | // LLL.h |
---|
2 | |
---|
3 | // This file contains the implementation of two special variants of the |
---|
4 | // LLL-algorithm. |
---|
5 | // For further explainations see the book of Henri Cohen, A Course in |
---|
6 | // Computational Algebraic Number Theory. |
---|
7 | |
---|
8 | // When performing the LLL-algorithm, some coefficients grow very fast. |
---|
9 | // Therefore one should use a data type for arbitrary long integers |
---|
10 | // (called "BigInt" in the code). |
---|
11 | // If no such data type is specified, BigInt is defined to be a long |
---|
12 | // (cf. globals.h). |
---|
13 | |
---|
14 | #ifndef LLL_H |
---|
15 | #define LLL_H |
---|
16 | |
---|
17 | #include "globals.h" |
---|
18 | |
---|
19 | extern short relations(BigInt** b, const short& number_of_vectors, |
---|
20 | const short& vector_dimension, BigInt**& H); |
---|
21 | // Computes the relations of the input vectors stored in b and returns the |
---|
22 | // dimension r of the lattice spanned by these relations. |
---|
23 | // The return value -1 indicates that an error has occurred. |
---|
24 | // A LLL-reduced basis of the relations is written into the two-dimensional |
---|
25 | // array H. Memory allocation for this array is done in the routine; |
---|
26 | // when leaving the routine, the dimension will be vector_columns x r. |
---|
27 | // This routine corresponds to algorithm 2.7.2 in Cohen's book. |
---|
28 | |
---|
29 | extern short integral_LLL(BigInt **b, const short& number_of_vectors, |
---|
30 | const short& vector_dimension); |
---|
31 | // Reduces the input vectors stored in b (in the sense of an LLL-reduction). |
---|
32 | // The input vectors have to be linearly independent. |
---|
33 | // ATTENTION: The input vectors are modified during this algorithm. For |
---|
34 | // efficiency reasons in our application, we do NOT store a transformation |
---|
35 | // matrix! |
---|
36 | // The return value is -1 if an error has occurred, 0 else. |
---|
37 | // This routine corresponds to algorithm 2.6.7 in Cohen's book. |
---|
38 | |
---|
39 | #endif // LLL_H |
---|