[6ba162] | 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 |
---|