Team : PolSys - Polynomial SystemsAxes : SSR (👥👥), TMC (👥👥).
Team leader :
Mohab Safey El Din Campus Pierre et Marie Curie 26-00/321
The PolSys team activity is centered on the design of algorithms based on computer algebra and symbolic computation to solve systems of polynomial constraints, the implementation of these algorithms and their applications.
The fundamental problem of solving systems of polynomial constraints arises in a wide range of areas such as cryptology, computational geometry, program verification in computer science, mathematical conjectures of geometric or combinatorial nature, and in engineering sciences such as robotics, biology, chemistry to cite a few.
The nonlinear nature of these problems and the requirements on exactness and exhaustiveness which arise in some applications make the use of local numerical and approximation methods difficult. Hence, the algorithmic challenges for solving polynomial systems are numerous, especially when considering that this problem is NP-hard. By using methods from computer algebra such as Gröbner bases computations, the PolSys team designs algorithms which allow:
- the solving of polynomial systems with coefficients in a finite field (for applications in e.g. cryptology or error correcting codes) or with exact rational coefficients (for applications in engineering sciences)
- the solving over the reals of systems of polynomial constraints, even when the number of complex solutions is infinite, or depending on parameters (for applications of geometric nature or coming from robotics)
- the solving of quantifier elimination problems over the real or the complex numbers and polynomial optimization problems (for applications in program verification or coming from engineering sciences)
- the determination of topological properties (such as number of connected components) of real solution sets to systems of polynomial constraints.
Also, the team has a regular activity in several application areas such as cryptology and robotics.
Computer Algebra. Polynomial System Solving. Gröbner Bases. Complexity. Real roots. Parametric systems. Cryptology. Algebraic Cryptanalysis. Algebraic Computational Geometry. Applications. Symbolic/Numeric Interaction. Software. High performance Linear Algebra.
No event planned at present.Archives
- J. Berthomieu, Ch. Eder, M. Safey El Din : “msolve: A Library for Solving Polynomial Systems”ISSAC '21: Proceedings of the 2021 on International Symposium on Symbolic and Algebraic Computation, Saint Petersburg, Russian Federation, pp. 51-58[Berthomieu 2021c]
- A. Casanova, J.‑Ch. Faugère, G. Macario‑Rat, J. Patarin, L. Perret, J. Ryckeghem : “GeMSS: A Great Multivariate Short Signature”1-4 pages[Casanova 2017]
- J. Berthomieu, V. Neiger, M. Safey El Din : “Faster change of order algorithm for Gröbner bases under shape and stability assumptions”47th International Symposium on Symbolic and Algebraic Computation, Lille, France[Berthomieu 2022e]
- H. Le, M. Safey El Din : “Solving parametric systems of polynomial equations over the reals through Hermite matrices”Journal of Symbolic Computation, vol. 112, pp. 25-61, (Elsevier)[Le 2022c]
- J. Berthomieu, J.‑Ch. Faugère : “Polynomial-Division-Based Algorithms for Computing Linear Recurrence Relations”Journal of Symbolic Computation, vol. 109, pp. 1-30, (Elsevier)[Berthomieu 2022c]
- J. Berthomieu, B. Boyer, J.‑Ch. Faugère : “Linear Algebra for Computing Gröbner Bases of Linear Recursive Multidimensional Sequences”Journal of Symbolic Computation, vol. 83 (Supplement C), pp. 36-67, (Elsevier)[Berthomieu 2017a]
- J. Berthomieu, B. Boyer, J.‑Ch. Faugère : “Linear Algebra for Computing Gröbner Bases of Linear Recursive Multidimensional Sequences”ISSAC '15: Proceedings of the 2015 on International Symposium on Symbolic and Algebraic Computation, Bath, United Kingdom, pp. 61-68[Berthomieu 2015a]
- L. Bettale, J.‑Ch. Faugère, L. Perret : “Cryptanalysis of Multivariate and Odd-Characteristic HFE Variants”Public Key Cryptography - PKC 2011, vol. 6571, Lecture Notes in Computer Science, Taormina, Italy, pp. 441-458, (Springer Berlin / Heidelberg)[Bettale 2011]
- J.‑Ch. Faugère, A. Otmani, L. Perret, J.‑P. Tillich : “Algebraic Cryptanalysis of McEliece Variants with Compact Keys”Eurocrypt 2010 - 29th International Conference on Cryptology, vol. 6110, Lecture Notes in Computer Science, Monaco, Monaco, pp. 279-298, (Springer Verlag)[Faugère 2010d]
- D. Henrion, S. Naldi, M. Safey El Din : “Exact algorithms for linear matrix inequalities”SIAM Journal on Optimization, vol. 26 (4), pp. 2512–2539, (Society for Industrial and Applied Mathematics)[Henrion 2016a]
- L. Bettale, J.‑Ch. Faugère, L. Perret : “Cryptanalysis of HFE, Multi-HFE and Variants for Odd and Even Characteristic”Designs, Codes and Cryptography, vol. 69 (1), pp. 1-52, (Springer Verlag)[Bettale 2013]
- J.‑Ch. Faugère, M. Safey El Din, P.‑J. Spaenlehauer : “On the Complexity of the Generalized MinRank Problem”Journal of Symbolic Computation, vol. 55, pp. 30-58, (Elsevier)[Faugère 2013b]
- L. Bettale, J.‑Ch. Faugère, L. Perret : “Solving Polynomial Systems over Finite Fields: Improved Analysis of the Hybrid Approach”ISSAC 2012 - 37th International Symposium on Symbolic and Algebraic Computation, Grenoble, France, pp. 67-74, (ACM)[Bettale 2012]
mohab.safey (at) nulllip6.fr