Title Generic LLL and polynomial factorisation Version Française

Location

INRIA, Project CAFÉ
BP 93, 06902 France

Information

Manuel Bronstein

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:

  • the original GMP implementation,
  • the generic Aldor implementation, instantiated over GMP,
  • the generic Aldor implementation, instantiated over the Aldor integers.

    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.

    Manuel.Bronstein@sophia.inria.fr

    May 25, 2005.