LFANT Research team
Lithe and fast algorithmic number theory
- Leader : Andreas Enge
- Type : Project team
- Research center(s) : Bordeaux
- Field : Algorithmics, Programming, Software and Architecture
- Theme : Algorithmics, Computer Algebra and Cryptology
- CNRS,Université de Bordeaux,Institut de Mathématiques de Bordeaux (IMB) (UMR5251)
Team presentationThe LFANT team researches algorithms in number theory and arithmetic geometry. We cover all aspects from complexity theory over optimised implementations up to cryptologic applications.
The Lfant team has the goal of making an inventory of the major number theoretic algorithms, with an emphasis on algebraic number theory and arithmetic geometry, and of carrying out complexity analyses. So far, most of these algorithms have been designed and tested over number fields of small degree and scale badly. A complexity analysis should naturally lead to improvements by identifying bottlenecks, systematically redesigning and incorporating modern asymptotically fast methods.
Reliability of the developed algorithms is a second long term goal of our team. Short of proving the Riemann hypothesis, this could be achieved through the design of specialised, slower algorithms not relying on any unproven assumptions. We would prefer, however, to augment the fastest unproven algorithms with the creation of independently verifiable certificates. Ideally, it should not take longer to check the certificate than to generate it.
All theoretical results are complemented by concrete reference implementations in Pari/Gp, which allow to determine and tune the thresholds where the asymptotic complexity kicks in and help to evaluate practical performances on problem instances provided by the research community. Another important source for algorithmic problems treated by the Lfant team is modern cryptology. Indeed, the security of all practically relevant public key cryptosystems relies on the difficulty of some number theoretic problem; on the other hand, implementing the systems and finding secure parameters require efficient number theoretic algorithms.
International and industrial relations
- France Télécom R&D
- University of Calgary
- University of Waterloo
- Universiteit Leiden
Research teams of the same theme :
- ARIC - Arithmetic and Computing
- CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
- CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
- DATASHAPE - Understanding the Shape of Data
- GALAAD2 - Géométrie , Algèbre, Algorithmes
- GRACE - Geometry, arithmetic, algorithms, codes and encryption
- POLSYS - Polynomial Systems
- SECRET - Security, Cryptology and Transmissions
- SPECFUN - Symbolic Special Functions : Fast and Certified
- VEGAS - Effective Geometric Algorithms for Surfaces and Visibility