  We present a deterministic algorithm which computes the multilinear factors
of multivariate lacunary polynomials over number fields. Its complexity is
polynomial in $\ell^n$ where $\ell$ 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 $\ell$ and $n$.
  Over other fields of characteristic zero and finite fields of large
characteristic, our algorithms compute the multilinear factors having at least
three monomials of multivariate polynomials. Lower bounds are provided to
explain the limitations of our algorithm. As a by-product, we also design
polynomial-time deterministic polynomial identity tests for families of
polynomials which were not known to admit any.
  Our results are based on so-called Gap Theorem which reduce high-degree
factorization to repeated low-degree factorizations. While previous algorithms
used Gap Theorems expressed in terms of the heights of the coefficients, our
Gap Theorems only depend on the exponents of the polynomials. This makes our
algorithms more elementary and general, and faster in most cases.
