Name
Abstract | ||
|---|---|---|
We present an algorithm which computes the multilinear factors of bivariate lacunary polynomials. It is based on a new Gap theorem which allows to test whether P(X)=∑kj=1 αjXαj(1+X)βjis identically zero in polynomial time. 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 bivariate lacunary polynomials over a field of large finite characteristic in probabilistic polynomial time. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2465506.2465932 | international symposium on symbolic and algebraic computation |
Keywords | DocType | Volume |
linear factor,previous form,jis identically zero,probabilistic polynomial time,multilinear factor,polynomial time,large finite characteristic,bivariate lacunary polynomial,factoring bivariate lacunary polynomial,new gap theorem,finite fields,polynomial factorization,wronskian determinant | Conference | abs/1206.4224 |
ISSN | Citations | PageRank |
Proceedings of the 38th International Symposium on Symbolic and
Algebraic Computation (ISSAC'13), pp 141-148, ACM, 2013 | 6 | 0.44 |
References | Authors | |
19 | 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 |