  We develop a theory of arithmetic Newton polygons of higher order, that
provides the factorization of a separable polynomial over a $p$-adic field,
together with relevant arithmetic information about the fields generated by the
irreducible factors. This carries out a program suggested by \O{}. Ore. As an
application, we obtain fast algorithms to compute discriminants, prime ideal
decomposition and integral bases of number fields.
