LFANT Research team

Lithe and fast algorithmic number theory

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.

International and industrial relations

Industrial partners

  • France Télécom R&D
  • ST-Ericsson
  • Gemalto
  • Cryptolog

International contacts

  • University of Calgary
  • University of Waterloo
  • Universiteit Leiden

Keywords: Algorithmic number theory Number fields Function fields Algebraic curves Cryptology

Research teams of the same theme :

Inria Headquarters and research centres

Direct links

Social