Title Generic LLL and polynomial factorisation | Version Française |
Location
INRIA, Project
CAFÉ
BP 93, 06902 France
Information
Description
The lattice reduction algorithm LLL plays a fundamental role in cryptology, number theory and computer algebra (polynomial factorisation, see [2]). 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 [1], which should significantly improve its efficiency.
[1] M.van Hoeij, Factoring polynomials and the knapsack problem, Journal of Number Theory, 95, 167-189, (2002)
[2] V.V.Prasolov, Polynomials, Chapter 8, Algorithms and Computations in Mathematics, Vol.11 Springer, Heidelberg.
Tools
Unix workstation, the Aldor programming language, with the algebra library.
Duration
3-4 months.