Abstract

Let p be a rational prime and Z( x ) be a monic irreducible polynomial in Z p [ x ]. Based on the work of Ore on Newton polygons (Ore, 1928) and MacLane's characterization of polynomial valuations (MacLane, 1936), Montes described an algorithm for the decomposition of the ideal [Special characters omitted.] over an algebraic number field (Montes, 1999). We give a simplified version of the Montes algorithm with a full MAPLE implementation which tests the irreducibility of Z( x ) over Q p . We derive an estimate of the complexity of this simplified algorithm in the worst case, when Z( x ) is irreducible over Q p . We show that in this case the algorithm terminates in at most[Special characters omitted.] bit operations. Lastly, we compare the "one-element" and "two-element" variations of the Zassenhaus "Round Four" algorithm with the Montes algorithm