Mes travaux

• Mon rapport de stage

• The subject of my thesis:

  Solving multivariate polynomial systems is a significant challenge in various fields such as robotics or cryptography. Computing Gröbner bases is one of the primary methods for solving multivariate polynomial systems. Indeed, in the generic case, this provides a system with the same solutions and whose resolution is straightforward as it reduces to the case of a single variable and a single equation. The first algorithm to compute Gröbner bases was introduced by Buchberger in 1965. In 1983, Lazard's algorithm used Gaussian elimination on Macaulay matrices. In 1998, Faugère invented an algorithm called F4, which combines the ideas of the two previous algorithms and is significantly faster in practice. Finally, in 2002, Faugère proposed an algorithm called F5, which is more efficient because it manipulates smaller matrices, thanks to a new criterion for detecting redundant rows in the Macaulay matrices. One of the fundamental aspects in designing fast algorithms like those of Lazard and Faugère is the study of vector spaces generated by the rows of the involved matrices. The approach of this thesis is to work with matrices whose entries are univariate polynomials and to study the spaces generated by the rows of such matrices. On one hand, the matrices contain single-variable polynomials, which complicates the calculations compared to the mentioned algorithms, where the matrices are constant. However, since the size of the matrices is also reduced, it is expected that this approach will improve the complexity of Gröbner basis computation, which is the main objective of the thesis. The first year will be dedicated to adapting Lazard's algorithm. The second year will focus on the F4 algorithm, and the third year on the F5 algorithm. For each algorithm, the goal will be to adapt it to univariate polynomial matrices, study the theoretical complexity, implement it in Julia, and compare it in practice to classical algorithms that are optimized for this language.

Mes enseignements

• LU1IN011 - Elément de programmation 1 (Sciences Formelles) - S1-23 2023-2024
• LU1IN002 - Eléments de programmation 2 - S2-23 2023-2024
• LU2IN006 - Structures de données - S2-23 2023-2024

Me contacter