Motivated by a connection with the factorization of multivariate polynomials, we study integral convex polytopes and their integral decompositions in the sense of the Minkowski sum. We first show that deciding decomposability of integral polygons is NP-complete then present a pseudo-polynomial-time algorithm for decomposing polygons. For higher-dimensional polytopes, we give a heuristic algorithm which is based upon projections and uses randomization. Applications of our algorithms include ab...