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 |
---|