Gruppo di ricerca : PolSys - Polynomial Systems
Axes : SSR (👥👥), TMC (👥👥).Responsabile del gruppo di ricerca :
Mohab Safey El Din Campus Pierre et Marie Curie 26-00/321
Presentazione breve
POLSYS/SALSA is a joint team between INRIA and University Pierre and Marie Curie. Our group is internationally recognized as one of the leading group in the area of solving systems of polynomial equations/inequalities (non-linear systems) using exact methods. Our goal is to develop efficient algorithms for computing the complex solutions and/or the real ones or in a finite field. Our group has developed several fundamental algorithms, in particular algorithms for computing Gröbner bases and algorithms based on the so-called critical point method. Complexity issues are also investigated and recently our group has obtained results for structured polynomial systems (systems with symmetries, overdetermined or bilinear systems,…) enabling to identify some classes of problems that can be solved in polynomial time.
The practical efficiency of our algorithms relies on highly efficient linear algebra libraries. Hence, our group is involved in the development of parallel high performance linear algebra packages. Algorithms and software developed by our group are validated by solving challenging applications arising in scientific computing. Beyond the wide range of studied applications, the group focuses on:
- Applications in Cryptology and, in particular, the emerging topic Algebraic Cryptanalysis. The goal is to evaluate the security of a cryptosystem by reducing its study to the solving of an algebraic system with coefficients in a finite field.
- Computational Geometry: a new trend in this area is to substitute the manipulation of points and lines with algebraic curves. Intersecting such objects is equivalent to solve an algebraic system.
- Global optimizations problems of algebraic functions leading to new applications in scientific computing.
- Software and algorithms developed by the group have been successfully used in several applications fields: Biology, Robotics and Signal Theory.
Our software are devoted to be used in real life applications and teaching. The valorization of this software activity is ensured by their integration in recent releases of the Computer Algebra system Maple (distributed by the WMI Canadian Company)
As a prospective subject, we investigate a new research direction which consists in exploiting interactions between symbolic and numeric computing.
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.
Attualmente non è previsto nessun evento
Archivio
Selected publications
- T. Zhao, D. Wang, H. Hong : “Solution Formulas for Cubic Equations Without or With Constraints”, Journal of Symbolic Computation, vol. 46 (8), pp. 904-918 [Zhao 2011]
- M. Safey El Din, É. Schost : “A baby steps/giant steps Monte Carlo algorithm for computing roadmaps in smooth compact real hypersurfaces”, Discrete and Computational Geometry, vol. 45 (1), pp. 181-220, (ISBN: 0179-5376) [Safey El Din 2011]
- H. Everett, D. Lazard, S. Lazard, M. Safey El Din : “The Voronoi diagram of three lines”, Discrete and Computational Geometry, vol. 42 (1), pp. 94-130, (ISBN: 0179-5376) [Everett 2009b]
- M. Bardet, J.‑Ch. Faugère, B. Salvy, P.‑J. Spaenlehauer : “On the Complexity of Solving Quadratic Boolean Systems”, Journal of Complexity, vol. 29 (1), pp. 53-75 [Bardet 2013]
- J.‑Ch. Faugère, L. Perret, Ch. Petit, G. Renault : “Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Fields”, EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, vol. 7237, Lecture Notes in Computer Science, D. Pointcheval, Th. Johansson (Eds.), Cambridge, United Kingdom, pp. 27-44, (Springer Berlin / Heidelberg), (ISBN: 978-3-642-29010-7) [Faugère 2012c]
- 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]
- J.‑Ch. Faugère, M. Safey El Din, P.‑J. Spaenlehauer : “Computing Loci of Rank Defects of Linear Matrices using Grobner Bases and Applications to Cryptology”, ISSAC 2010 - 35th International Symposium on Symbolic and Algebraic Computation, Munich, Germany, pp. 257-264, (ACM), (ISBN: 978-1-4503-0150-3) [Faugère 2010j]
- J.‑Ch. Faugère, M. Safey El Din, P.‑J. Spaenlehauer : “Gröbner Bases of Bihomogeneous Ideals Generated by Polynomials of Bidegree (1,1): Algorithms and Complexity”, Journal of Symbolic Computation, vol. 46 (4), Duluth, MN, USA, pp. 406-437, (Academic Press, Inc.), (ISBN: 0747-7171) [Faugère 2011e]
- M. Jin, X. Li, D. Wang : “A New Algorithmic Scheme for Computing Characteristic Sets”, Journal of Symbolic Computation, vol. 50, pp. 431-449 [Jin 2013]
- A. Strzebonski, Elias P. Tsigaridas : “Univariate Real Root Isolation in Multiple Extension Fields”, ISSAC 2012 - 37th ACM International Symposium on Symbolic and Algebraic Computation, Grenoble, France, pp. 343-350, (ACM), (ISBN: 978-1-4503-1269) [Strzebonski 2012]
Tutti…
Contatti
Jean-Charles.Faugere (at) nulllip6.fr
LIP6 » Ricerca » Gruppi di ricerca » PolSys
