Factoring bivariate sparse (lacunary) polynomials
| dc.creator | Avendano, Martin | |
| dc.creator | Krick, Teresa | |
| dc.creator | Sombra, Martin | |
| dc.date | 2006-02-07 | |
| dc.date.accessioned | 2026-07-07T07:03:13Z | |
| dc.date.available | 2026-07-07T07:03:13Z | |
| dc.description | We present a deterministic algorithm for computing all irreducible factors of degree $\le d$ of a given bivariate polynomial $f\in K[x,y]$ over an algebraic number field $K$ and their multiplicities, whose running time is polynomial in the bit length of the sparse encoding of the input and in $d$. Moreover, we show that the factors over $\Qbarra$ of degree $\le d$ which are not binomials can also be computed in time polynomial in the sparse length of the input and in $d$. | |
| dc.description | 20 pp, Latex 2e. We learned on January 23th, 2006, that a multivariate version of Theorem 1 had independently been achieved by Erich Kaltofen and Pascal Koiran | |
| dc.identifier | https://arxiv.org/abs/math/0602145 | |
| dc.identifier | http://arxiv.org/abs/math/0602145 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/108886 | |
| dc.subject | Number Theory | |
| dc.subject | Primary 11Y05; Secondary 11Y16, 11G50 | |
| dc.title | Factoring bivariate sparse (lacunary) polynomials | |
| dc.type | text |