Équipe : PolSys - Systemes Polynomiaux

Axes : SSR (👥👥), TMC (👥👥).

Responsable :

Mohab Safey El Din Campus Pierre et Marie Curie 26-00/317

Contact

Site Web
mohab.safey (at) nulllip6.fr

Effectif

Quatre permanents, neuf doctorants.

Présentation

L’équipe PolSys se concentre sur la conception d'algorithmes relevant du calcul formel (méthodes algébriques) pour la résolution de systèmes polynomiaux, ainsi que sur l'implantation et les applications de ces algorithmes.

Le problème fondamental de la résolution des systèmes polynomiaux apparaît dans un grand nombre de domaines comme la cryptologie, la géométrie algorithmique, ou la vérification de programmes dans les sciences du numérique ; dans des conjectures de nature géométrique ou combinatoire en mathématiques ; ou bien dans certaines sciences de l'ingénieur comme la robotique, la biologie et la chimie. La nature non-linéaire de ces problèmes, c’est-à-dire le caractère exact, exhaustif ou global des solutions calculées requis par certaines applications, rend l'usage de méthodes purement numériques, ou de méthodes d'approximation, délicat. Les défis algorithmiques posés par la résolution de systèmes polynomiaux sont donc considérables, et ce d'autant que ce problème est NP-dur.

En s'appuyant sur des méthodes de calcul formel, et notamment le calcul de bases de Gröbner, l'équipe PolSys conçoit des algorithmes qui permettent :

la résolution de systèmes polynomiaux à coefficients dans un corps fini (pour des applications en cryptologie ou théorie des codes correcteurs) ou à coefficients rationnels exacts (pour des applications dans les sciences de l'ingénieur) ;

la résolution de systèmes sur les nombres réels même lorsque le nombre de solutions complexes est infini, ou dépendant de paramètres (pour des applications de nature géométrique ou provenant de la robotique) ;

la résolution de problèmes d'élimination des quantificateurs sur les nombres réels ou complexes, et notamment les problèmes d'optimisation polynomiale (pour des applications en vérification de programmes ou dans des sciences de l'ingénieur) ;

la détermination de propriétés topologiques aux ensembles de solutions réelles (notamment la détermination du nombre de composantes connexes).

Pour résoudre cette large gamme de problèmes, l'équipe développe plusieurs logiciels dédiés, dont notamment la bibliothèque msolve qui est utilisée par des systèmes de calcul formel largement diffusés comme SageMath et OSCAR (voir aussi d'autres logiciels développés par l'équipe).

Enfin, l'équipe développe une activité régulière dans plusieurs domaines d'applications, notamment la cryptologie et la robotique.

Auto-évaluation Archives Soutenances de thèse

Mots-clés

Calcul formel Algorithmes Calcul haute performance Cryptologie Applications robotiques

Quatorze invités ces 12 derniers mois

Adrien TAYLOR, Alin BOSTAN, Christian EDER, Rafael MOHR, Hugo PASSE, Simone NALDI, Rémi PRÉBET, Yoann LODAY, Alaa IBRAHIM, Rekha THOMAS, Ludovic PERRET, Matthew BAKER, Hadrien NOTARANTONIO, Frédéric CHYZAK.

Sélection de publications

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” 47^th 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 - 29^th 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 - 37^th International Symposium on Symbolic and Algebraic Computation, Grenoble, France, pp. 67-74, (ACM)[Bettale 2012]

Toutes…