Computational real algebraic geometry, positioned at the interface of mathematics and computer science, addresses algorithmic problems on real solution sets to systems of polynomial constraints with real coefficients.

I will start by showing how fundamental algorithmic subroutines can be combined to solve challenging problems in robotics, such as deciding cuspidality of mechanisms, with potential for further applications in differential equations depending on the audience's interest. Next, I will present recent algorithmic improvements on the most challenging subroutines: answering connectivity queries in real algebraic sets. This introduces the notion of roadmaps, which reduce the problem to studying real algebraic curves, leading us to focus on their connectivity properties, from an algorithmic point of view. Throughout the presentation, I will showcase original implementations leveraging the latest software developments.

This talk gathers joint works with D.Chablat, N.Islam, A.Poteaux, M.Safey El Din, D.Salunkhe, É.Schost and P.Wenger.

Louis Roussel nous présentera ses progrès récents concernant le calcul d'équations intégro-différentielles.

François Boulier nous présentera l'avancée de l'interface Python de sa librairie DifferentialAlgebra . Dépot git de DifferentialAlgebra.

On étudiera la notion de série formelle, en particulier la dualité. On calculera les séries de Laurent qui sont solutions de l'équation Painlevé I : y'' = 6 y^2 + x où y est une fonction de x. Ce calcul effectué par Sofia Kovalevskaïa est à la base de l'intégrabilité au sens de Painlevé.

François Boulier nous présentera l'avancée de l'intégration de sa librairie DifferentialAlgebra dans la bibliothèque SymPy de Python. Dépot git de DifferentialAlgebra.

Considering models with integro-differential equations is motivated by the following reason: on some examples, the introduction of integral equations increases the expressiveness of the models, improves the estimation of parameter values from error-prone measurements, and reduces the size of the intermediate equations.

Reducing the order of derivation of a differential equation can sometimes be achieved by integrating it. An algorithm was designed by the CFHP team for that purpose. However, successfully integrating integro-differential equations is a complex problem. Unfortunately, there are still plenty of differential equations for which the algorithm does not apply. For example, computing an integrating factor might be required.

Rather than integrating the differential equation, we can perform an integral elimination. We are currently working on this technique which also implies some integration problems. To try to overcome these problems, we are also using deep learning techniques with the hope of finding small calculus tips.

This talk overviews recent works done by my PhD students Lin-Xiao Wang and Delaram Talaashrafi, respectively in polyhedral geometry and in the area of polyhedral-model-based automatic parallelization.

In a first part, we present a new algorithm for computing the integer hull of a rational polyhedral set of arbitrary dimension. After a normalization step ensuring that each supporting hyperplane contains integer points, the input polyhedron is partitioned into smaller polyhedra, the integer hulls of which are either given for free or cheap to compute. This partition is obtained by recursively computing integer hulls in lower dimension.

We implemented this algorithm in Maple and in the C programming language. Our results suggest that our algorithm is very efficient comparing to well known software counterparts, especially when the input polyhedral set is large in volume.

In a second part, we introduce a polyhedral-model-based analysis and scheduling algorithm that exposes and utilizes cross-loop parallelization through tasking. This work exploits pipeline patterns between iterations in different loop nests, and it is well suited to handle imbalanced iterations.

Our LLVM/Polly-based prototype performs schedule modifications and code generation targeting a minimal, language agnostic tasking layer. We present results using an implementation of this API with the OpenMP task construct. For different computation patterns, we achieved speed-ups of up to 3.5× on a quad-core processor while LLVM/Polly alone fails to exploit the parallelism.

In this talk, we present algebraic attacks against RD and MR, namely MaxMinors and SupportMinors. These attacks were introduced by Bardet et al. (Eurocrypt and Asiacrypt 2020).

The MaxMinors attack has been devasting against ROLLO and RQC, two cryptosystems which made it to the Second Round of the NIST Post-Quantum Standardization Process; and the SupportMinors attack has been used by Beullens in his cryptanalysis of the Rainbow signature scheme, a 3rd Round Finalist in the aforementioned standardization process.

Keywords:
Post-Quantum Cryptography, Error Correcting Codes, Algebraic Cryptanalysis, Gröbner Basis

Références:
[1] Introduction to the Galois Theory of Linear Differential Equations, M. F. Singer, 2007
[2] Computing the Galois Group of a Linear Differential Equation, E. Hrushovski, 2002
[3] Around the Numeric-Symbolic Computation of Differential Galois Groups, J. van der Hoeven, 2007
[4] Symbolic-Numeric Factorization of Linear Differential Operators, F. Chyzak, A. Goyer, M. Mezzarobba, 2022