LFANT

Team presentation

The Lfant project-team works on algorithms in number theory and arithmetic geometry. We cover all aspects from complexity theory over optimised implementations up to cryptologic applications. The team is joint between INRIA and Institut de Mathématiques de Bordeaux, the mathematics institute of CNRS, Université de Bordeaux and Bordeaux INP.

Research themes

Lfant 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.