|Title Generic LLL and polynomial factorisation||Version Franšaise|
BP 93, 06902 France
The lattice reduction algorithm LLL plays a fundamental role in cryptology, number theory and computer algebra (polynomial factorisation, see ). There are several implementations over the integers or floating point numbers. The objective of this internship is to port the existing GMP implementation of LLL by Paul Zimmermann into a generic Aldor implementation. It will then be used to compare the performances of:
Those comparisons should yield evaluations of the eventual efficiency losses due to genericity and due to the different integer implementations.
In a second stage, the univariate polynomial factorisation code in the algebra library will be modified to use LLL in the recombination phase, as explained in , which should significantly improve its efficiency.
 M.van Hoeij, Factoring polynomials and the knapsack problem, Journal of Number Theory, 95, 167-189, (2002)
 V.V.Prasolov, Polynomials, Chapter 8, Algorithms and Computations in Mathematics, Vol.11 Springer, Heidelberg.
Unix workstation, the Aldor programming language, with the algebra library.