Newton polygons of higher order in algebraic number theory

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