We develop a theory of arithmetic Newton polygons of higherorder, that provides the factorization of a separable polynomial over a p-adic eld, together with relevant arithmetic information about the elds generatedby the irreducible factors. This carries out a program suggested by . Ore.As an application, we obtain fast algorithms to compute discriminants, primeideal decomposition and integral bases of number elds.