Factoring bivariate lacunary polynomials without heights

Arkadev Chattopadhyay 1 Bruno Grenet 2 Pascal Koiran 2 Natacha Portier 2 Yann Strozecki 3
1 DCS - Department of Computer Science [University of Toronto]
2 LIP - Laboratoire de l'Informatique du Parallélisme
3 LRI - Laboratoire de Recherche en Informatique
Abstract : We present an algorithm which computes the multilinear factors of a bivariate polynomials. It is based on a new Gap theorem which allows to test whether a polynomial of the form P(X,X+1) is identically zero in time polynomial in the number of terms of P(X,Y). The algorithm we obtain is more elementary than the one by Kaltofen and Koiran (ISSAC'05) since it relies on the valuation of polynomials of the previous form instead of the height of the coefficients. As a result, it can be used to find some linear factors of polynomials over a field of large finite characteristic in probabilistic polynomial time.
Type de document :
Communication dans un congrès
38th International Symposium on Symbolic and Algebraic Computation, Boston, United States. p 141-148, 2013, 〈10.1145/2465506.2465932〉
Liste complète des métadonnées
https://hal-ens-lyon.archives-ouvertes.fr/ensl-00738542
Contributeur : Bruno Grenet <>
Soumis le : jeudi 4 octobre 2012 - 15:19:57
Dernière modification le : mercredi 10 octobre 2018 - 21:28:02

Lien texte intégral

arxiv

Identifiants

Collections

ENS-LYON | INRIA | LIP | UMR8623 | UNIV-LYON1

Citation

Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki. Factoring bivariate lacunary polynomials without heights. 38th International Symposium on Symbolic and Algebraic Computation, Boston, United States. p 141-148, 2013, 〈10.1145/2465506.2465932〉. 〈ensl-00738542〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

132

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD