Abstract | ||
---|---|---|
We present a deterministic algorithm which computes the multilinear factors of multivariate lacunary polynomials over number fields. Its complexity is polynomial in ℓn where ℓ is the lacunary size of the input polynomial and n its number of variables, that is in particular polynomial in the logarithm of its degree. We also provide a randomized algorithm for the same problem of complexity polynomial in ℓ and n. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1016/j.jsc.2020.04.013 | Journal of Symbolic Computation |
Keywords | Field | DocType |
Multivariate lacunary polynomials,Polynomial factorization,Polynomial-time complexity,Number fields,Finite fields,Wronskian determinant | Discrete mathematics,Combinatorics,Polynomial,Multivariate statistics,Time complexity,Lacunary function,Gap theorem,Multilinear map,Mathematics | Journal |
Volume | ISSN | Citations |
104 | 0747-7171 | 3 |
PageRank | References | Authors |
0.37 | 17 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Arkadev Chattopadhyay | 1 | 150 | 19.93 |
Bruno Grenet | 2 | 33 | 6.56 |
Pascal Koiran | 3 | 919 | 113.85 |
Natacha Portier | 4 | 96 | 11.49 |
Yann Strozecki | 5 | 70 | 7.56 |