Joint team with the IMB (CNRS and university Bordeaux 1 et 2).
LFANT
Lithe and fast algorithmic number theory
Andreas Enge
Type :
Project-Team
Team presentation
The LFANT team researches algorithms in number theory and arithmetic geometry. We cover all aspects from complexity theory over optimised implementations up to cryptologic applications.
Research themes
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.
