On the Complexity of Computing Gröbner Bases for Quasi-homogeneous Systems

Jean-Charles Faugère 1 Mohab Safey El Din 1 Thibaut Verron 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Résumé : Soit $\K$ un corps et $(f_1,\ldots,f_n) \subset \K[X_1,\ldots,X_n]$ une famille de polynômes quasi-homogènes de degrés respectifs $(d_1,\dots,d_n)$ pour un système de poids $(w_1,\dots,w_n)$. De tels systèmes apparaissent dans de nombreuses applications, issus par exemple de la physique ou de la cryptographie. On donne une stratégie pour calculer la base de Gröbner de systèmes quasi-homogènes, en adaptant les algorithmes qui existent déjà pour les systèmes homogènes, au cas quasi-homogène. Sous des hypothèses de généricité, on montre que pour un système quasi-homogène de dimension nulle, la complexité de la stratégie est polynomiale en la borne de Bézout pondérée $\prod_{i=1}^{n}d_{i} / \prod_{i=1}^{n}w_{i}$. On présente des résultats expérimentaux obtenus pour des systèmes génériques, ainsi que pour des systèmes apparaissant dans un problème issu de la cryptographie. Ces expériences montrent que l'exploitation de la structure quasi-homogène des systèmes nous permet de résoudre des problèmes qui étaient auparavant hors de portée.
Type de document :
Communication dans un congrès
The 38th International Symposium on Symbolic and Algebraic Computation, Jun 2013, Boston, Maine, United States. ACM, ISSAC '13 : Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, pp.189-196, 2013, 〈10.1145/2465506.2465943〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00780388
Contributeur : Thibaut Verron <>
Soumis le : vendredi 3 mai 2013 - 12:27:03
Dernière modification le : mardi 8 décembre 2015 - 14:53:08
Document(s) archivé(s) le : dimanche 4 août 2013 - 04:04:37

Fichiers

issac53p-faugere.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jean-Charles Faugère, Mohab Safey El Din, Thibaut Verron. On the Complexity of Computing Gröbner Bases for Quasi-homogeneous Systems. The 38th International Symposium on Symbolic and Algebraic Computation, Jun 2013, Boston, Maine, United States. ACM, ISSAC '13 : Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, pp.189-196, 2013, 〈10.1145/2465506.2465943〉. 〈hal-00780388v2〉

Partager

Métriques

Consultations de la notice

320

Téléchargements de fichiers

159