Software

The use of software is often an integral part of the research activity in the field of computer algebra. It helps to explore and understand mathematical and algorithmic properties, as well as to experiment with prototypes of algorithms being developed. General-purpose computer algebra systems include FriCAS, SageMath, Magma, Maple, Mathematica.

Since 2018, I have chosen to devote a significant part of my time to contribute to the collective development of computer algebra software. Within this activity, I aim to make state-of-the-art algorithms available to their users, both through general code (mostly in SageMath) and through implementations that are thoroughly optimized for performance (mostly in PML, FLINT, and msolve).

PML: Polynomial Matrix Library

This library was created in 2018 by Seung Gyu Hyun, Éric Schost, and myself, and described in an article published in ISSAC 2019 proceedings.

The first, main part of PML is a stable C++ library, based on Victor Shoup’s NTL. It provides numerous additions to the latter, mostly concerning operations on univariate polynomial matrices and functionalities from structured linear algebra, over finite fields. The fastest known algorithms are implemented, leading to the state-of-the-art performance e.g. for multiplying polynomial matrices, computing their Hermite or Popov normal form, finding a minimal basis of Hermite-Padé approximants (PM-Basis algorithm), solving a Hankel-like linear system, etc.

Recently, there has been discussions with colleagues around the use of PML to study the security of symmetric cryptographic primitives. Thanks to PML’s fast implementations of the determinant of a polynomial matrix, this has already enabled them to experimentally validate an important algebraic attack published at CRYPTO 2024 (see Table 5).

The second, work-in-progress part of PML has a similar goal but is based on the C library FLINT (see below), which seems to offer better possibilities of interactions and perspectives. In fact, as of 2024–2025, there is high synergy between work done in PML and in FLINT, and the idea has been mentioned that in the longer term most of the functionalities of PML may be integrated in FLINT. Recently, Gilles Villard has augmented PML with an interface to Maple.

FLINT: Fast Library for Number Theory

This C library provides high performance for a wide range of algebraic computations, currently maintained by Fredrik Johansson and Albin Ahlbäck. I have been contributing to FLINT since 2023. My work therein focuses on basic field arithmetic (in particular for finite fields ℤ/pℤ\mathbb{Z}/p\mathbb{Z}), and on efficient operations on univariate polynomials and matrices over such fields. My past and current projects include:

  • basic arithmetic in ℤ/pℤ\mathbb{Z}/p\mathbb{Z} : for prime numbers pp that fit in a machine word, I work on a more systematic use of Shoup’s precomputations for repeated modular multiplications with a fixed operand (PR#2055 , PR#2432)
  • vectors and matrices: significantly reworked functions based on accelerated dot products, incorporating SIMD vectorized versions (PR#2018)
  • univariate polynomials: more efficient division with remainder for special, sparse operands (PR#2470); a new implementation of the 3-prime FFT (fast Fourier transform) and its use for polynomial multiplication and middle products (PR#2107).

msolve: solving multivariate polynomial systems

The msolve library, which was first announced in ISSAC 2021 Proceedings by Jérémy Berthomieu and Christian Eder and Mohab Safey El Din, focuses on intensive computations related to multivariate polynomial system solving. It calls FLINT for some basic operations, when relevant.

Apart from regular maintenance and enhancements, my main ongoing project in msolve is the acceleration of its Gröbner basis change of ordering. A first task was completed in 2025 (PR#215), speeding up the generation of a linear recurrent sequence which was the bottleneck in the Wiedemann-like algorithm sparse FGLM . Two tasks are ongoing for further accelerations and better multi-threading support: the extension to a block-Wiedemann-like algorithm, and the integration of a recent polynomial matrix-based approach (Proceedings ISSAC 2022) whose prototype in PML shows promising results.

SageMath: computer algebra system

This widely used free mathematical software is based on internal Python/Cython code and on the integration of numerous state-of-the-art libraries that offer optimized code and excellent performance (including NTL and FLINT).

One aspect of my work in SageMath concerns the improvement of linear algebra features by working on the interface with the state-of-the-art library FFLAS-FFPACK / LinBox (C++) and by making more systematic calls to it within SageMath. Apart from that, my main contribution is about the addition of tools for various computations on polynomial matrices. The goal of this work is not so much to obtain computational performance as to lay the foundations of a robust and complete software framework. Many functionalities are already usable today on instances of “everyday size”. Particular attention is paid to design choices and code organization, since the ultimate goal is for the core of the computations to no longer be done directly by SageMath code, but via calls to PML/FLINT, for better efficiency.