> <\body> of germs of plane curves>|<\doc-note> This paper is part of a project that has received funding from the French \PAgence de l'innovation de défense\Q. ||<\author-affiliation> CNRS, École polytechnique, Institut Polytechnique de Paris Laboratoire d'informatique de l'École polytechnique (LIX, UMR 7161) Bâtiment Alan Turing, CS35003 1, rue Honoré d'Estienne d'Orves 91120 Palaiseau, France |>>||<\author-affiliation> CNRS, École polytechnique, Institut Polytechnique de Paris Laboratoire d'informatique de l'École polytechnique (LIX, UMR 7161) Bâtiment Alan Turing, CS35003 1, rue Honoré d'Estienne d'Orves 91120 Palaiseau, France |>>|>||<\doc-note> > Given an algebraic germ of a plane curve at the origin, in terms of a bivariate polynomial, we analyze the complexity of computing an irreducible decomposition up to any given truncation order. With a suitable representation of the irreducible components, and whenever the characteristic of the ground field is zero or larger than the degree of the germ, we design a new algorithm that involves a nearly linear number of arithmetic operations in the ground field plus a small amount of irreducible univariate polynomial factorizations. |> Algebraic curves play a central role in algebraic geometry and various applications in effective algebra. In particular, efficient algorithms are needed to compute topological or analytic invariants, arithmetic genus, desingularized models, integral closures, Riemann\URoch spaces, etc. Usual applications in computer algebra concern the irreducible factorization of multivariate polynomials, the integration of rational functions, the construction of algebraic geometry error correcting codes, the bi-linear complexity of polynomial multiplication, etc. In the present paper, we are interested in computing the irreducible factorization of any given polynomial \|]>>, where > denotes an field. Here \Peffective\Q means that algorithms are at our disposal for the arithmetic operations and the zero test in>. Let |)>> denote the fraction field of |]>> of Laurent series in . The field <\equation*> \||z|\>|\>\1>\|)>|)> of power series with fractional exponents is called the field of (or ) over >. Let |\>> denote the algebraic closure of>. If> has characteristic zero, then |\>||z|\>|\>> is the algebraic closure of |)>>. In other words, any polynomial in |)>> splits into linear factors in |\>||z|\>|\>>. Computations of Puiseux expansions of roots of go back to Newton, and were rediscovered by Puiseux; see198> and. The well known turns out to be effective whenever |\>> is effective. When adopting a suitable algebraic complexity model (in which running times are measured in terms of the required number of arithmetic operations in > or |\>>), the complexity is easily seen to be polynomial in the degree of and in the required precision. However, at present time, we are not aware of an algorithm with a softly linear cost for any precision (especially below the valuation of discriminant of ). For the design of such a quasi-optimal algorithm, it is important to carefully state the problem that needs to be solved. In particular, one has to pay attention to the ways in which algebraic numbers and fractional power series are represented. It turns out that the computation of Puiseux expansions is closely related to the computation of irreducible factorizations in |]>> and that representation issues are more straightforward for the latter problem. In this paper, we therefore focus on the computation of irreducible factorizations. Our main goal is the design of an efficient algorithm for factoring apolynomial \|]>> that is given modulo >|)>> for a finite precision \\>, assuming that we already have an algorithm for decomposing polynomials in > into irreducible factors. For complexity analyses, we consider algebraic complexity models (such as computation trees). In other words we simply count numbers of arithmetic operations and zero tests in specified algebraic structures. Until the end of the paper, \0> is a fixed rational number that can be taken arbitrarily close to zero. For complexity estimates we often use the notation: >(g(n))> means that |)>>>>>; see25, section7> for technical details. The least integer larger or equal to is written |x|\>>; the largest one smaller or equal to is written|x|\>>. For randomized algorithms over a finite effective ring >, we assume a special instruction that uniformly generates random elements in > with constant cost. For agiven input, the cost of a randomized algorithm is thus a random variable. The for input size is defined as the maximum of the averages of these random variables over all possible inputs of size s>. For a finite field > of characteristic and with elements, the usual primitive element representation will be used, so elements in > will be regarded in /|)>>> where > is an irreducible polynomial of degree . We use > as a notation for the cost of multiplying two polynomials of degree d>, in terms of the number of operations in the coefficient ring. We assume that /d> is anon-decreasing function in . It is known that one can take =O>. For rings of positive characteristic, one even has =O>, modulo a plausible number-theoretic conjecture. We will also denote <\equation*> d>>|polynomials in > of degree d>>>\d>\\\deg P\d|}>. A of > of height is a sequence |)>t>> with =\> and <\equation*> \=\|]>/|)>|)> for a separable irreducible monic polynomial \\|]>> and ,t>. We set <\equation*> s\deg \. Products and inversions in > take *\*s|)>>|)>> operations in >. This was first proved in in the case when > is a field and \*\*s|2>>. The result was extended to more general algebraic towers in. Whenever \*\*s|2>>, we may work in an algebraic extension > of degree *\*s|)>|)>> such that =card \\*\*s|2>>. The computation of such an extension can be done using *>|)>=*\*s|)>> operations in the prime subfield > of >, thanks to4.1>. For a fixed field>, this can be regarded as a precomputation, whereas computations with elements in > instead of > induce only a logarithmic overhead *\*s|)>|)>>. We define >,\,s|)>> to be an upper bound for the cost (expected or not) of irreducible factorization of a polynomial in n>>. It is convenient to introduce <\equation*> |\>>>|cost function for univariate polynomial factorization>>|\>>\m*max*\*s\m> >,\,s|)>|n*s*\*s>, so |\>>/m> is a non-decreasing function in . For example, if > is the finite field >, then a well known probabilistic algorithm due to Cantor and Zassenhaus factors univariate polynomials in n>> using an expected number of *log q|)>> bit operations. The currently best known algorithm is obtained as a combination of results due to von zur Gathen, Kaltofen and Shoup, and Kedlaya and Umans: it takes an expected number of <\equation*> >=O*log q*log p|)>>|)> bit operations; see5.1>. The case of a tower |)>t>> over =\> (with the above notation) reduces to the case of *\*s>>> by means of the fast change of representation of1.2>, that applies whenever <\equation> p\s*\*s*. In terms of bit complexity, and for a \Prandom access memory\Q computational model, this yields <\equation*> >,\,s|)>=O*s*\*s*log q*log p|)>>|)>. Details can be found in5.3>. Whenever condition is satisfied, we may then use the expected bit complexity bound <\equation*> |\>>=O*log q*log p|)>>|)>. When the tower has small degrees >, optimized factorization procedures can be found in. In particular, if is smooth, then polynomials of small degree can even be factored in quasi-optimal time. Note that these optimizations do not depend on Kedlaya\UUmans' algorithm for modular composition. For an abstract effective field >, there does not exist a general algorithm to factor polynomials in> into irreducible ones. Throughout this paper, we will therefore need to assume that such an algorithm is provided by the computational model: <\description> |assumption that irreducible factorization is available in >>Irreducible factorization in > is available within the computational model. In practice, this property holds whenever > is effectively finitely generated over its prime subfield. Once factorization is available in >, it is also available in >, with a complexity that depends on those of resultants and gcds. Let > still denote an effective field, let \\|]>> be monic as a polynomial in, and assume that =0>. So > defines a germ of curve at the origin. In practice, we always truncate at a finite order in . For the discussion in the following paragraphs, we therefore take \> and assume that is monic, primitive, and separable in, of total degree d>, and of partial degrees d> in and d> in . If the characteristic of > is zero or sufficiently large, then Puiseux expansions to any given precision can be computed in polynomial time when considering an algebraic complexity model over |\>>\Vthis result belongs to the folklore. Consider a Puiseux series > that is a root of . The shortest truncation of this series which is different from any truncation of a distinct Puiseux series root of is called the of >. In 1978, Kung and Traub showed that the Puiseux expansion of > can be computed efficiently using Newton's method, once its singular part is known. The complexity of the computation of singular parts started to be studied in the eighties. In, Henry and Merle showed that the embedded resolution of an irreducible germ of curve defined by =0> at the origin can be computed with |)>> operations in|\>>. In, Duval introduced the notion of , that allowed computations over |\>> to be replaced by computations over >. She adapted the usual Newton polygon algorithm to such a rational representation, and made use of to handle algebraic extensions without polynomial factorization. She achieved a total cost of |)>> operations in >, whenever the characteristic is zero or sufficiently large. This analysis was based on slow arithmetic for polynomials and series. In his PhD thesis, Poteaux showed that Duval's algorithm takes at most *d|)>> operations in > in order to obtain all the singular parts of the Puiseux expansions. In, Poteaux and Rybowicz also proved that the singular parts of the rational Puiseux expansions centered at a single point can be computed using *d+d*log q|)>> operations in>, in the case when =\>; this bound relies on fast polynomial arithmetic. In, Poteaux and Weimann finally gave a probabilistic algorithm that allows singular parts to be computed with * P|)>+1|)>|)>> operations in >, assuming that the characteristic of > is zero or sufficiently large. This bound is quasi-optimal in worst cases, when we need order about P|)>> before root separation takes place8.1>. Their algorithm makes use of dynamic evaluation and the singular parts are represented by truncations of rational Puiseux expansions. These algorithms by Poteaux also extend efficiently to obtain the collection of all singular parts at each of the singularities of the algebraic curve defined by =0>. As a byproduct, Poteaux and Weimann proved the expected complexity bound * P|)>+\|)>|)>+>|)>> for the irreducible factors of at precision >|)>>, still under the assumption that the characteristic of > isd>; see1.6>. When =\>, a polynomial bit complexity for Puiseux series was first achieved by Chistov. The complexity bound for this case was subsequently detailed and improved by Walsh>. Since the complexity exponents are rather large, multi-modular approaches turn out to be of practical interest. Once singular parts are known, we have already mentioned that Puiseux expansions can be extended by means of the Newton operator, as described in; see also for recent optimizations. For small and moderate expansion orders, it is often more efficient to use lazy or relaxed arithmetic to expand algebraic power series. For very large expansion orders, yet another method is to compute a differential operator that annihilates the expansions; see for complexity bounds. It is also worth mentioning that individual terms of algebraic Puiseux series over a finite field can be computed even faster than with the Newton iteration. In positive characteristic, the field of Puiseux series no longer coincides with the algebraic closure of |)>>; see for instance. Hamburger\UNoether expansions constitute a natural extension of Puiseux series in positive characteristic. In his 1989 article, Abhyankar addressed a question from Kuo about an algorithm to decide the irreducibility of a germ of curve, without using blowups or Puiseux series. In characteristic zero, Abhyankar gave a positive answer to this question, by using expansions of the defining polynomial of the germ with respect to so-called . These approximate roots can be determined recursively by means of a generalized Newton polygon, previously introduced in. They generalize Tschirnhaus transforms. Complexity analyses can be found in: in favorable cases irreducibility tests take softly linear time (plus a justifiable amount of irreducibility tests in >). Abhyankar's work has been completed and extended to arbitrary characteristic by Cossart and Moreno-Socías in, where they present an alternative construction based on valuation theory. The mathematical relationship between approximate roots, Puiseux expansions, and Hamburger\UNoether expansions can be found in. Whenever > is a local ring different from |]>>, factorization in > is a more difficult problem, for which Puiseux expansions cannot be used. The first interesting case is when > is the field > of the -adic numbers. Let be a monic primitive square-free polynomial in >. A first series of contributions concern the algorithm due to Zassenhaus, and dedicated to the construction of integral bases modulo; see for instance. The first polynomial time algorithm for factoring over> was given by Chistov, and then improved by Cantor and Gordon in. After that, Pauli designed a factorization algorithm over an algebraic extension of degree of > with bit complexity <\equation> *val*|)>*log p|)>>. Since 1999, Montes has been designing different algorithms; his irreducibility test of has been shown in to have a complexity similar to. The next improvements are due to Guàrdia, Montes, and Nart. They exploit previous ideas by MacLane and Okutsu in order to compute so-called (as a shorthand for \POkutsu\UMontes factorizations\Q); see for a survey. In, Bauch, Nart, and Stainsby proved the bit complexity bound <\equation*> O+d*val+d*val*log p|)>>|)> for an algebraic extension of degree of >. Further refinements and applications, including the computation of integral closures, can be found in. In Poteaux and Weimann recently improved the latter complexity bound to <\equation*> O*log p|)>>|)> (discarding factorization costs in >) whenever d>: they made use of the natural \Pdivide and conquer\Q extension of the generalized Hensel lifting of and also applied the same \Pincrease of precision\Q strategy as in. Various other generalizations of Puiseux expansions have been investigated by van der Hoeven, starting in 1997 with his PhD thesis. First of all, he developed a framework for the resolution of algebraic equations over afield> of generalized power series instead of |]>>. One natural example is to take =\|)>>, where > is an effective subfield of another field of Laurent series |)>>. In this case, the underlying value group of > becomes non-archimedean, and the issue arises how to conduct exact computations with truncated power series. This is easy if =\>, but less trivial if > contains transcendental power series such as , because of the required zero test. We refer to> for some recent perspectives on this type of computations. The resolution of algebraic equations over fields > of generalized power series is still based on the Newton polygon method. However, the complexity can no longer be analyzed in terms of the truncation order in a non-archimedean context. Instead, one may consider the resolution of equations in Hensel position as a natural building block. In, van der Hoeven showed how to reduce the resolution of a general algebraic equation of degree to at most applications of Hensel's lemma. It would be interesting to analyze the complexity of this algorithm in the special cases that were considered above. Non-archimedean value groups are not merely a theoretical curiosity. Until recently, effective counterparts of Hironaka's theory of standard bases for power series were only known in the case of algebraic power series. In, generalized Puiseux series have been put to develop elimination theories for more general power series, such as differentially algebraic power series. Non-archimedean value groups actually arise in anatural way when studying algebraic differential equations, and the Newton polygon method can be generalized to this context; see for recent progress and further references. The main purpose of this paper is to present a self-contained and quasi-optimal algorithm for approximate factorization over rings of formal power series. We show how to efficiently factor into irreducible polynomials, and for each irreducible factor > we construct generators of the valuation group of |]>/|)>> in a form of a ; see Definition. An of modulo >|)>> is a list of factors ,\,P> of modulo >|)>>, along with their associated multiplicity and contact tower; see Definition. In particular the > are irreducible, pairwise coprime, and we have <\equation*> P=P>*\*P>+O>|)>, for some integers \1>. The contact tower associated to > allows the computation of the valuation in |]>/|)>> in softly linear time. The following main result will be proved at the end of section: <\theorem> Let > be a fixed positive value, and assume >>. Let \|]>> be monic of degree in , known modulo >|)>>, and such that the characteristic of> is zero orn>. Then, an irreducible factorization of modulo >|)>> can be computed using <\equation*> >*\|)>+2*|\>> operations in>. <\example> Take \\>, \2>, and x+O|)>>. Then , =x>, and =2> is an irreducible factorization of modulo >|)>>. Taking , =x-z>, =x+z>, =m=1>, we obtain another such factorization. This shows that approximate factorizations are not unique in general. Note that the term |\>> is negligible with respect to >*\> as soon as the precision > is sufficiently large. By using our approximate factorization algorithm with a sufficiently large precision, we deduce the following complexity bound for the actual irreducible factorization of ; see section. <\theorem> Let > be a fixed positive value, and assume >>. Let \|]>> be monic and separable of degree in and known at precision P|)>+\> in with \0>. Assume that the characteristic of> is zero orn>. Then, the irreducible factors of can be computed modulo >|)>> using <\equation*> >* P|)>+\|)>|)>+2*|\>> operations in>. Theorem considers P|)>> as part of the input. This is not very restrictive in characteristic zero or val P|)>> thanks to1>. On the other hand, if belongs > then P|)>\*deg P> can be computed with *deg P|)>> operations in >. Theorem can be regarded as a deterministic counterpart of1.6> and is also similar to4>, although the underlying algorithms are notably different. Our proofs are elaborated from scratch by taking special care of the precisions and the cost of all factorizations in >. We rely neither on Puiseux expansions (contrary to), nor on , nor on approximate roots, nor on the \Pdivide and conquer\Q strategy from on the precision. Instead, our algorithm is based on a natural cascade of factorizations driven by Newton polytopes and a new method to balance the depth of the recursive calls: namely our central shift algorithm of section. Note that approximate factorizations in the sense of Theorem (especially below the valuation of the discriminant) are not assessed in. The algorithm behind Theorem decomposes into several subtasks for which we design efficient solutions. The first subtask concerns the computation of so-called and ; see section. Distinct-slope factorizations separate the factors of according to the slopes of its Newton polygons. Equal-slope factorizations serve a similar purpose for polynomials with a single slope. We achieve these computations in softly linear time by means of a generalized Hensel lifting, as explained in section. The contact factorization algorithm performs a cascade of distinct-slope and equal-slope factorizations over increasing contact towers. When the tree modeling the successive splittings of is not sufficiently well balanced, the total complexity moves away from quasilinearity. Our algorithm of section circumvents this issue through tree-balancing. The top level algorithm is described in section. Computing over contact towers involves two difficulties. First, as for towers of algebraic field extensions, we do not know how to perform arithmetic operations in softly linear time. We overcome this difficulty by doing most of the operations within the original ring |]>> using a sufficiently high precision. The second difficulty concerns zero tests and inversions in towers. In section, we introduce , that can be computed fast thanks to accelerated tower arithmetic. As said, the power series setting from this paper is simpler than the one of general local fields studied by Montes Nevertheless, the main mathematical ideas are roughly the same and go back to the work of MacLane on : approximate roots, OM-factorizations, and contact towers share the same philosophy. Compared to, our contact towers represent a kind of a more general \Paugmented semi-valuations\P. Approximate roots can indeed be regarded as special cases of contact towers but also of so-called \Ptipos\Q in. Our contact factorization algorithm does not rely on approximate roots: as explained in section, such roots may be useful in practice, but it is a drawback that they are not preserved during factorizations. In fact, our new central shift strategy behaves as an algorithmic improvement with respect to approximate roots; see section. While MacLane, and later Montes, focused on constructing augmented (semi-)valuations over polynomial rings, our down-to-earth and self-contained approach begins with designing efficient data structures in the vein of triangular sets and Hironaka's standard bases. In addition, let us mention that, compared to, our multi-factor Hensel lifting of section is based on a faster multi-remaindering strategy. We would also like to insist on our novel strategy for approximate factorizations, that is behind Theorem. Roughly speaking, the problem here is similar to approximate factorization in >. The first quasi-optimal algorithms for the computation of the distinct roots were designed for the case when the required precision is sufficiently high; more recently, a different algorithm was proposed for small precisions. Detailed comparisons between all known algorithms for local factorization would be too long and technical to be discussed here. Instead, we dedicate our next section to that illustrate the computational difficulties that are common to all known approaches. Before we give the formal definition of a , we review a few motivating examples from the complexity perspective. Let |\>> be a totally ordered abelian group and let \|\>> be a monoid embedded in |\>>. A with respect to the > is a direct sum <\equation*> \>R, where the > are abelian groups such that *R\R> for all and in >. An element of is said to be if it belongs to one of the >. Any element in can be uniquely written \>>, where >|homogeneous component of of degree >\R> is called the of degree of . If \> and \|\>>>, then we also denote <\equation*> >>|homogeneous components of from degree to e+\>>>>\\>>|f\e+\>>>>>>. The of a non-zero element R>, written >|initial form of >>, is the non-zero homogeneous component > with the smallest index . By convention we set \0>. An ideal of is said to be whenever it can be generated by homogeneous elements, or equivalently whenever the homogenous components of any element of also belong to . To each non-zero element R> we may associate the smallest index v> such that \0>; we set \\>. The map \\|}>> is a , which means that it satisfies \min,v|)>> and \v+v> for all R>. Given \|\>>>, we call >> the of at >.|r-frame|>|gr-geometry||gr-grid||0.2>|gr-grid-old||0.2>|gr-edit-grid-aspect|||>|gr-edit-grid||0.2>|gr-edit-grid-old||0.2>|gr-grid-aspect|||>|gr-grid-aspect-props|||>||gr-geometry||gr-frame|>|gr-mode||gr-text-at-halign|center|gr-text-at-valign|bottom|gr-grid-aspect-props|||>|gr-grid-aspect||>|gr-grid||gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||gr-edit-grid-old||1>|magnify|0.840896414744361|||>>||>||>||>>||>>|||||||||=9>|>>|||||||||>>|||>>||>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>||>||>||>||>||>||>||>||>||>||>||>||>||>||>>>>> The Newton polygon of \z*x++z|)>*x+z*x+z*x+x+z*x+x+z*x+z*x>. Each dot represents a monomial in . > The of a non-zero polynomial <\equation*> P=P+P*x+\+P>*x>\R of degree > is the lower border of the convex hull in 0>\\|}>|)>> of the set of points <\equation*> |)>|)>\0\i\d,P\0|}>. Figure illustrates this definition with |]>> and =\>. The Newton polygon is thus a broken line with edges ,j|)>,\,,j|)>>, with 0>, such that: <\itemize> \i\\\i>, =v>|)>> for ,r>, |)>\|i-i>*v>|)>+-i|i-i>*v>|)>>, for all and \i\i> with \0>, |)>\|i-i>*v>|)>+-i|i-i>*v>|)>>, for all and i> or i> with \0>. Intuitively speaking, these conditions mean that |)>|)>> lies on or above the Newton polygon. If =0>, then we have \0> and \\>. Any ,r> determines an edge > with vertices ,j|)>> and,j|)>>. The associated to > is <\equation*> \,\E>|]>*x>\R. Whenever \\>, the of > is -j|)>/-i|)>>. The first slope is > whenever =0>. Two consecutive edges have different slopes. factorization> In order to illustrate computations in algebraic extensions of > or |]>>, let us first consider applying the Newton polygon method to an input polynomial of the form <\equation*> P=P+z*P, where \\> is a monic separable irreducible polynomial of degree > and \\> has degree d> in . We then consider <\equation> P=0 as a polynomial equation in . The Newton polygon of consists of a single edge starting at > and ending at ,0|)>>; its slope is . Equation has a solution in |]>>, where \\/|)>>. Indeed, let > be the class of in >. Replacing by +> in, we obtain the new equivalent equation <\equation> P|)>*+*P|)>*+\+!>*P|)>>|)>*>=z*P+|)>. The separability of > implies |)>\0>, which allows us to apply Hensel's lemma: there exists a unique solution \\|]>> with valuation |)>\0> in . This is the point of view of factoring in terms of Puiseux expansions. In terms of space complexity, we note that computations in > typically require > times more space than in >. Fortunately, this is compensated by the fact that the \Punique\Q solution> to actually describes all > solutions to in |\>|]>>. Indeed, any solution in |\>|]>> is obtained by substituting a root \|\>> of > for > in the expression of>. From a time complexity point of view, the resolution of can be done efficiently by using Newton's method. However, this involves truncated power series evaluations of expressions such as +>|)>>, where \\|]>>. These give in turn rise to modular compositions (with modulus >). Over general coefficient fields >, no quasi-optimal algorithm (of complexity >>) is currently known for this task, so it is preferable to avoid such operations whenever possible. In particular, it is better to avoid working over algebraic extensions of the field > of coefficients. In order to avoid modular compositions, one idea is to consider that equation does not require any explicit resolution. In other words, it is already in such asimple form that we may essentially consider it as \Psolved\Q. More generally, later in this paper, we will consider an equation =0> as \Psolved\Q if and only if the Newton polygon of with respect to suitable \Pcontact coordinates\Q has a single slope for which the associated Newton polynomial is separable (and technically, irreducible). The problem of solving a general equation =0> with \> then reduces to the problem of factoring as a product of \Psolved\Q polynomials. From this perspective, expressing the solutions of =0> as Puiseux series becomes a rewriting problem for \Psolved\Q polynomials, which is independent from the main resolution of the equation =0> itself. Consider the polynomial equation in over |]>> given by <\equation> P\x-6*x-5*z*x+9=0. When solving this equation by means of the Newton polygon method, we see that the Newton polygon of has a single slope with associated Newton polynomial <\equation*> x-6*x+9=-3|)>. In other words, all solutions of are of the form +o>, where -3=0>. Usually, the Newton polygon method proceeds by performing a change of variable <\equation*> x=\+, while imposing the constraint |)>\0>. So we are reduced to solving <\equation*> P+|)>=+4*\*+12*-5*z*-5*z*\=0. The Newton polygon has two edges: ,|)>> and ,|)>>. Therefore |)>=1> and we have -5*z*\=0+o|)>>, so =\*z+o>, where -5*\=0>. We proceed with the change of variable <\equation*> =\*z+z*|~>, while imposing the constraint |~>|)>\0>. So we are now led to solving <\equation*> P+\*z+z*|~>|)>/z=0=24*\*|~>+O|)>+O. The unique value of |~>> can therefore be computed efficiently by means of the Newton iteration as a regular root of +\*z+z*|~>|)>/z>. However, this means that we have to work over the algebraic extension ,\|]>>. The idea behind contact calculus is to avoid computing over this type of algebraic extensions, by working with respect to so-called contact coordinates instead. In the present example, the idea is to rewrite as <\equation*> -3|)>-5*z*x=0. We next reinterpret this equation as <\equation> \-5*z*\=0, where > and > are two new variables that are subject to the following constraints: <\itemize> =x>, =\-3>, |)>=0> and |)>\0>. The variables > and > can be regarded as unknowns, with values in the ring of Puiseux series in . These unknowns satisfy the system of equations <\equation*> \=x,\=\-3,\-5*z*\=0. In other words, computing Puiseux expansions of solutions to is equivalent to computing Puiseux expansions of solutions to the latter system. We note that -3> is separable in > and that the solutions for > begin with +O>. Then -5*z*\> is separable in > for each solution >, so the system admits the following solutions: <\equation*> ||||||>||+O>|>|>||>*z+O|)>>>|>||+O>||>||>*z+O|)>>>|>||+O>||>||>*\*z+O|)>>>|>||+O>||>||>*\*z+O|)>>>>>> After the change of variable =z*|~>>, these solutions are regular roots of the following map modulo >: <\eqnarray*> ,|~>|)>>|>||~>--3|)>>>||~>-5*\>>>>>.>>>> By means of the Newton iteration, these roots may be lifted efficiently to any required precision, and so may the corresponding solutions of . The variables > and > are called contact coordinates. Note that <\equation*> P=-3|)>+O|)>, so the germ of the curve defined by -3=0> approximates the one defined by . From a geometric point of view, the two germs are \Pin contact\Q. Informally speaking, the Newton polygon of equation in > has a single edge of vertices > and >, with associated Newton polynomial -5*z*\>, whence |)>=1>>. The precise meaning of this \Pgeneralized Newton polygon\Q will be the purpose of section. Since the polynomial /z|)>-5*\> is separable in /z>, we consider the polynomial -5*z*\> to be \Psolved\Q. Working with contact coordinates is a little bit tricky, since > and > are related by the equation =\-3>. Basic arithmetic operations and the Newton polygon method therefore have to be adapted with care. It turns out that \Pcontact calculus\Q with respect to contact coordinates has a double flavor. At small orders > in , it boils down to working in towers of algebraic extensions of |]>/>|)>>. At large orders in, we may convert between polynomials in |]>> and |]>,\|]>/-\+3|)>> through the mechanism of -3|)>>-adic expansions. In this paper, we have chosen to do most actual computations in |]>>, since fast algorithms for basic arithmetic operations in this ring are well known. However, conversions between the \Pplain coordinates\Q > and the \Pcontact coordinates\Q ,\|)>>> incur some precision loss. Fortunately, this precision loss can be controlled for the applications in this paper. Of course, it would be interesting to design a genuine fast arithmetic for contact coordinates without precision loss. Example has several variants that motivate the general definition of contact coordinates in the next section. First of all, consider the equation <\equation> P\|)>-6*|)>-5*z*|)>+9=0. In that case, the contact coordinates would rather be =x-> and =\-3>. This illustrates that we do not systematically take =x>, although we always do have -x\\|]>>> when working over >. Let us next consider the equation <\equation> P\-3|)>-5*z*x|)>+z*x=0. In this case, we start with the same contact coordinates=x> and=\-3> as for, but also need to introduce a third one =\-5*z*\>, subject to |)>\2>. In general, we may need to introduce as many as |log d/log 2|\>> contact coordinates. Yet another variant of is the equation <\equation> P\x-6*x+9-z=0 We again use the same contact coordinates=x> and=\-3> as for, but this time> rewrites into -z>, that can be factored: <\equation*> \-z=+z|)>*-z|)>. In general, these types of factorizations can be expensive to compute with respect to the original coordinates and become more transparent for the contact coordinates. Let us first consider the equation <\equation> P=x-*x+>-z=0. When solving this equation using the usual Newton polygon method, we find that there is a single slope |)>=0>, with =x>, for which the associated Newton polynomial -2*\+1> has asingle root =1> of multiplicity . This means that the leading terms of the Puiseux expansions are and that the remaining terms can be found by performing the change of variable > and solving the resulting equation for >: <\equation*> -*+|>-z=0. In a similar way, we find the leading term of >, which has again multiplicity . We have to go on like this for steps until reaching the equation <\equation*> -|1-z>*+|>-z=0. At this point there are two possible dominant terms for > (namely > and >), each of multiplicity one, and we consider that we essentially solved the equation (more terms can be obtained efficiently using Newton's method). From the complexity point of view, the problem is that we need to recompute a new equation at every step where we discover one more term of the expansion, which is quite expensive. A well known trick to replace the 50 steps by a single one is to compute the solution =z/> to the derivative of the equation, that is <\equation*> 2*\-=0, and directly set +> instead of >. The new equation in > then becomes <\equation*> -z=0, after which the resolution process directly splits into two branches =z> and =-z>>. In general, for a -fold leading term, we need to consider a solution > to the >-fold derivative of the equation. In that case, the change of variables +>> is called a . For general contact coordinates, things become more technical, but similar strategies apply. In general, if > is a ring with unity, if is a monic polynomial of degree in >, if divides , and if is invertible in >, then there exists a unique monic polynomial \> of degree such that > has degree d-d/m>; see section. The polynomial is called the -th of . If , then the -th approximate root \\> corresponds to the Tschirnhaus transform +>. In general, the -adic expansion of writes as +u*g+\+u*g+u> where the > are polynomials in > of degreedeg g=d/m>, so is the -th of if and only if =0>>. Let us now consider yet another type of equation with an almost -fold multiple solution <\equation> P\**\*-z|)>=0. When solving the equation naively with the Newton polygon method, we obtain a fold branch > at the first step, a single branch |)>> and a >-fold branch |)>> at the second step, a single branch |)>> and a >-fold branch +O|)>> at the third step, and so on. From the complexity point of view, factoring out a single branch at every step leads to a cost <\equation*> O++\+1|)>=O|)> as a function of , which is not quasi-linear in . Using Tschirnhaus transforms is not really of any help. For instance, the >-fold derivative of the equation yields <\equation*> d!*\-!**z+\+z|)>=0, with solution =1+|)>*z+\>. After the change of variable +>, we still obtain one single branch and one >-fold branch. What really helps in this situation is a way to determine the series <\equation> \=1+z+\+z. This series has the property that, after the change of variable +>, we obtain the equivalent equation <\equation*> +z+\+z|)>*+z+\+z|)>*\*+z|)>*=0, whose Newton polygon has edges. In particular, the resolution process now branches into distinct parts of multiplicity one. Computing the series is equivalent to \Psolving\Q . But instead of peeling off factors of degree one from the left-hand side of, we rather compute > with precision about in a recursive manner. This allows to factor as the product of two polynomials of degree close to , and to repeat this process in a recursive manner. Series such as will be called . For a general polynomial equation =0>, even within contact coordinates, the central shift will allow us to guarantee a suitably balanced factorization for which and can recursively be factored with good complexity. This section formalizes the concept of contact towers. The effective ground field is written> and the contact coordinates will be denoted by ,\,\>. We endow ,\,\|]>|]>> with the weighted valuation, simply written \P\Q, defined by and =\\\> for ,t>. With <\equation*> >|valuation semi-group of the -th level of a contact tower>>\=\+\*\+\+\*\, this valuation induces a grading <\equation*> \,\,\|]>|]>=\>\,\,\|]>|]>, where ,\,\|]>|]>> is the set of polynomials made only of terms of valuation ; notice that ,\,\|]>|]>=\>. When no confusion is possible, we drop \Pweighted\Q. Let > be the least common multiple of the denominators of ,\,\>. Then, the Chinese remainder theorem implies the following identity for the group completion |\>> of>: <\equation*> |\>>|group generated by >>>|ramification index of |\>>>>|\>=\+\*\=\*>. The integer > is called the of the valuation. The following definition is central for the rest of this paper. <\definition> A of height consists of: <\itemize> Variables ,\,\>, called contact coordinates; Defining polynomials >|-th defining polynomial of a contact tower>\\|]>,\,\|]>> for ,t>; Rational numbers ,\,\>, called weights. These data are required to satisfy the following properties: <\itemize> > is monic in > of degree \1>; > \\d>, for ,t> and ,i-1>; \0> and *\\1> for ,t>; We endow ,\,\|]>|]>> with the weighted valuation defined by and =\> for ,t>. We demand that: <\itemize> =d*\>, for ,t>; \d*\>, for ,t-1>. The tower is said to be when \2> for ,t>. Unless explicitly stated, the towers in this paper will be in the sense that \2> for ,t-1>. The weights ,\,\> will also be called the , in reference to the slopes of the corresponding Newton polygons; see section. When a contact tower is almost reduced then *\*d|)>|)>> holds. The of the tower is *\*d>. <\example> , =\-3>, =0> form a contact tower of height . <\example> Consider the example. It turns out that, =\-3> and=\-5*z*\> form a contact tower with contact slopes =0>, =1>. Here we got > and > from =val|)>=val=0> and =val|)>=val*\|)>=2>. We introduce another independent variable > of weight > and subject to the constraint \d*\>. We also define the ideal <\equation*> >|defining ideal of a contact tower of height >>I\-\,\,\-\,\-\|)>\\,\,\|]>|]>, and the corresponding quotient ring <\equation*> >|level of a contact tower>>\\\,\,\|]>|]>/I. In the following paragraphs, we show that > is effective for computations with finite truncation orders in and >. For this, we adopt the point of view of standard bases, while doing the proofs from scratch for completeness. We recall that the > on > is defined as follows: <\equation*> ,\,a|)>\,\,b|)>\\j\,n|}>a=b,\,a=b,a\b. We also introduce a total ordering > with <\equation*> z\\\\\\\\\1 on the group >*\>*\*\>\>*\>*\*\>\e,\,e\\|}>> by <\equation*> >*\>*\*\>\z>*\>*\*\>>>|>>|||+e*\+\+e*\\f+f*\+\+f*\\>>|||+e*\+\+e*\=f+f*\+\+f*\\>>|,\,e,e,e|)>\,\,f,f,f|)>.>>>>>|\>>>>>>>>>>> The ordering > is a in the sense that <\equation*> z>*\>*\*\>\z>*\>*\*\> implies <\equation*> z+g>*\+g>*\*\+g>\z+g>*\+g>*\*\+g> for all ,\,g|)>\\>. The of \,\,\|]>|]>> with respect to this ordering is defined to be the largest monomial with a non-zero coefficient in . The set of monomials spanned by the leading monomials of the elements of an ideal is written . Note that >*\>*\*\>*lm I\lm I>. With the terminology of, the ordering > is called a . A of an ideal \,\,\|]>|]>> with respect to the monomial ordering> is a set of generators ,\,g> such that the leading monomial of any polynomial in is a multiple of the leading monomial of at least one of the >. In other words, is generated by ,\,lm g>. A standard basis is said to be whenever none of the non-leading monomials in the > belong to . For the completeness, we now prove two well known lemmas from the theory of standard bases. <\lemma> \ |)>,\,in|)>> is a reduced standard basis of |)>,\,in|)>|)>> for >. <\proof> Since ,\,\> are independent of >, it suffices to prove the lemma in ,\,\|]>|]>>. According to the assumptions, |)>=|]>*\>> is monic of degree > in >, and > \\d> for all ,t> and ,i-1>. Therefore, <\equation*> lm|)>|)>=lm \=\> for ,t>. The lemma follows from general standard basis theory since the leading monomials of the |)>> share no variable. For completeness, we give a dedicated proof. Let us prove by induction on 1> that |)>,\,in|)>> is a standard basis for the ideal |)>,\,in|)>|)>>> in ,\,\|]>|]>>. This clearly holds for . Let us assume that the induction hypothesis holds for some 1> and consider |)>,\,in|)>|)>>. If > H\d>, then is a multiple of >. Otherwise, we write <\equation*> H,\,\|)>=H,\,\|)>+H,\,\|)>*\+\+H,\,\|)>*\, with d> and \0>. Then <\eqnarray*> |||)>,\,in|)>|)>>>||| mod |)>,\,in|)>|)>+\+ mod |)>,\,in|)>|)>|)>*\,>>>> so > belongs to the ideal |)>,\,in|)>|)>> of ,\,\|]>|]>>. By the induction hypothesis, > is a multiple of >> for some i>, whence so is . It follows that |)>,\,in|)>> is a standard basis. The fact that it is reduced is clear from degree considerations. For l>, we define <\equation*> S\,0,-\,0,\,0,\,0,\,0|)> where > stands at position and > at position . Note that the dot product \,\,\|)>>> is identically zero. For ,\,G|)>>, the initial form of , still written >, is defined as |)>,\,in|)>|)>>. <\lemma> If *in|)>+\+H*in|)>=0> for homogeneous ,\,H\\,\,\|]>|]>>, then <\equation> ,\,H|)>\k\l\t>\,\,\|]>|]>*in|)>. <\proof> We prove the lemma by induction on . For , we have nothing to prove, so assume that 1>. Extracting homogeneous components, we may assume without loss of generality that <\equation*> val*in|)>|)>=val*in|)>|)> whenever \0> and \0>. By the induction hypothesis, we may also assume that \0>. Long division of > by |)>,\,in|)>> yields <\equation*> H=Q*in|)>+\+Q*in|)>+R for homogeneous polynomials ,\,Q,R\\,\,\|]>|]>> with > R\d>, for ,t-1>. Reducing the relation *in|)>+\+H*in|)>=0> modulo |)>,\,in|)>|)>>, we obtain <\equation*> R*in|)>=0 mod |)>,\,in|)>|)>. Since > is monic in >, it follows that |)>,\,in|)>|)>>, and thus that . Consequently, we obtain <\equation*> ,\,H|)>=,\,H,Q*in|)>+\+Q*in|)>|)>, which implies <\eqnarray*> ,\,,0|)>>|>|+Q*in|)>,\,H+Q*in|)>,0|)>>>|||,\,H|)>-Q*in|)>-\-Q*in|)>.>>>> Let ,t-1>. If =0>, then =H> is homogeneous. Otherwise, we have <\eqnarray*> *in|)>|)>>||-val \+val \>>|||*\|)>-val \>>|||*\|)>-val \>>|||,>>>> so > is also homogeneous. Each > can be expanded with respect to >: <\equation*> =0>*\, with \\,\,\|]>|]>>. Then we have <\eqnarray*> ||0>*\|)>*in|)>+\+0>*\|)>*in|)>>>|||0>*in|)>+\+*in|)>|)>*\,>>>> which implies *in|)>+\+*in|)>=0> for all 0>. We conclude by applying the induction hypothesis. <\lemma> If *in|)>+\+H*in|)>=0> holds with > homogeneous in ,\,\|]>|]>>, then there exist ,\,G> in ,\,\|]>|]>> such that *-\|)>+\+G*-\|)>=0> and |)>=H> for ,t>. <\proof> We expand each > with respect to the variable >: <\equation*> H=0>H*\,H\\,\,\|]>|]>. For all 0>, we get <\equation*> H*in|)>+\+H*in|)>=0, so Lemma ensures the existence of homogeneous polynomials >> in ,\,\|]>|]>> such that <\equation*> ,\,H|)>=k\l\t>Q>*in|)>. Letting \0>Q>*\>, we deduce that <\equation*> ,\,H|)>=k\l\t>Q*in|)>. Since the > are homogeneous, up to replacing the > by their homogeneous components of suitable valuation, we may assume that <\itemize> the > are homogeneous, =val*in|)>|)>> holds for all l> with \0> and \0>, =val*in|)>|)>> holds for all l> with \0> and \0>. For l>, we introduce the vectors <\equation*> >\,0,--\|)>,0,\,0,\-\,0,\,0|)>, where -\|)>> stands at position and -\> at position , so the dot product >\-\,\,\-\|)>> is identically zero. We set <\equation*> ,\,G|)>\k\l\t>Q*>. Using the fact that =val \\val \=d*\>, we conclude that <\equation*> in,\,G|)>=ink\l\t>Q*>|)>=k\l\t>Q*in|)>=,\,H|)>. <\lemma> We have |)>=|)>,\,in|)>|)>>. <\proof> Let I>, so there exist ,\,P\\,\,\|]>|]>> with <\equation*> P=P*-\|)>+\+P*-\|)>. We repeat the following operations: <\enumerate> Let \min+val \\i=1,\,t|)>>. Since \val \=d*\>, we always have \val P>. If =val P>, then we obtain a relation <\equation*> in=\>in|)>*in|)> where > is the non-empty subset of indices such that =\-d*\>, so we are done. Otherwise \val P>, hence \>in|)>*in|)>=0>. The latter relation can be lifted to G*-\|)>=0> with |)>=in|)>> for ,t>, by Lemma. Replace the vector ,\,P|)>> by ,\,P|)>-,\,G|)>>, and go to step1. Thanks again to the assumption \val \=d*\>, the relation *-\|)>+\+P*-\|)>> holds after each iteration. Furthermore, the value of > strictly increases, so the process converges. We conclude that \|)>,\,in|)>|)>>. <\proposition> -\,\,\-\> is a standard basis of > for >. It is reduced whenever the contact tower is reduced. <\proof> Assume that 0> belongs to >. Then |)>>, so Lemma implies that =lm|)>|)>\lm P> for some . From Proposition, we know that an element of > can be uniquely represented by a polynomial ,\,\|)>\\|]>|]>,\,\|]>> of partial degree d> in > for ,t>. We call the of . We introduce contact towers as a tool for the local resolution of polynomial equations. For this, we will often reduce to the case when all the roots of the polynomial are in the local region of interest. Such polynomials are said to be \Pclustered\Q: <\definition> An element in > is a if its canonical representative is monic in > of degree 1> and if =l*\>. <\example> For the contact tower of Definition, the polynomial > is a clustered polynomial regarded in > for ,s>. The theory of standard bases comes with algorithms to compute modulo ideals given by standard bases. We now detail how to perform such computations in the case of >. Additions, subtractions and scalar multiplications are straightforward, but other operations require an appropriate treatment of \Pcarries\Q within >-adic expansions. For the contact coordinates of Example, let us briefly illustrate how carries occur during multiplications. <\example> In Example the polynomials =\-3> and=\-5*z*\> form a contact tower with contact slopes =0>, =1>. Let us first illustrate the computation of a product modulo >: <\equation*> a\+\*\|)>**\-3*z*\+\|)> mod I. Doing adirect polynomial multiplication, we obtain <\equation*> a=\*\+*\-3*z*\+\|)>*\-3*z*\*\+\*\ mod I, which is not in canonical representation since the degrees in > and > are too high. We thus have to rewrite <\equation*> \*\=+3|)>*\ mod I=\+3*\+5*z*\ mod I and <\equation*> \*\=\*\+5*z*\ mod I=\*\+5*z*\+15*z mod I. At the end, this leads to the following canonical representation for modulo >: <\equation*> a=+1|)>*\+*\+|)>*\+1|)>*\+|)>*\+5*z*\+45*z mod I. The canonical representative of an element in > can uniquely be written as <\equation*> A=0>A,\,\|)>*\, where \\|]>,\,\|]>> satisfies > A\d> for ,t>. Similarly, the canonical representative of another element \> can be written as <\equation*> B=0>B,\,\|)>*\. Now assume that =0> for sufficiently large values of . Then we may regard as aunivariate polynomial in >: the \Pdegree of in >\Q, written > b>|degree of with respect to the contact variable >>> b>, is defined as the largest integer such that \0>. We say that is >>\Pmonic of degree in >\Q when =1> and =0> for n>. Now we ask whether we can define and compute a generalized Euclidean division of by . The answer is \Pyes\Q under suitable assumptions. More generally, the following lemma shows that there exists a unique -adic expansion of. <\lemma> With the above notation let us assume that is clustered at > and has degree 1> in >. Then, there exist unique elements > in > satisfying <\equation*> a=0>q*b, and such that > q\n> for all 0>. <\proof> This lemma is a reformulation of what we have already proved with contact coordinates. In fact, it suffices to increase the height of the tower by one, to set <\equation*> \\B,\,\|)>*\, \n>, and to assign any weight \d*\> to the new variable >. Therefore, the canonical representative of the image of in > is given by <\equation*> a=0>E,\,\|)>*\, where > E\d> for ,t+1>. Consequently the above -adic expansion of exists with \E,\,\|)>>. As for uniqueness, let the > be as in the statement of the lemma, and let us write them <\equation*> q=Q,\,\|)> with > Q\d>. The > must satisfy <\equation*> 0>A,\,\|)>*\-0>Q,\,\|)>*\,\,\|)>\I, that implies <\equation*> 0>A,\,\|)>*\-0>Q,\,\|)>*\\I=I+-\|)>. It follows that the > do exist and are uniquely determined by the canonical representative of in >. <\definition> With the notation of Lemma, 1>q*b> and > are respectively called the and of the Euclidean division of by , and are written 1>q*b=a quo b> and =a rem b>. <\example> With the contact coordinates of Example, take <\equation*> a\\*\b\\-\. We have <\eqnarray*> ||*b+\ mod I>>|||*b+\+5*z*\ mod I>>|||+1|)>*b+\+5*z*\ mod I.>>>> Therefore the division of by writes with \+1> and \+5*z*\>. In what follows, we will restrict ourselves to computations with \Ppolynomials\Q in <\equation*> >|polynomials at the level of a contact tower>>\\\|]>,\,\|]>/I instead of \Pseries\Q in >. Elements in > can be represented canonically by polynomials ,\,\|)>\\|]>,\,\|]>> of partial degrees d> in > for ,t>. In order to alleviate terminology, we call elements in > , in which case we always assume that is represented canonically as a polynomial *\+\+c> in > with ,\,c\\>; we will also call this the . At the same time, we will keep the terminology of \Pcanonical representatives\Q whenever we need to carefully distinguish between and its actual polynomial representative . By what precedes, we may recursively expand elements in > with respect to ,\,\,> until >. However, from a computational point of view such >-adic expansions> are expensive. Indeed such expansions are reminiscent of computations modulo triangular sets, so it would be interesting to examine whether the algorithms of could be adapted or not. In this subsection we follow another direction that leads to efficient algorithms. The key idea is to rewrite elements in > with respect to the and . For this purpose, we introduce the following polynomials: <\eqnarray*> >|>|>|>|expression of > in terms of the plain coordinates>>\>|>|,\,\|)>,i=1,\,t.>>>> Note that > is monic of degree *\*d>. The change of representation is presented in the following lemma: <\lemma> The following map is a |]>>-algebra isomorphism: <\eqnarray*> >|conversion to plain coordinates>>\:\>|>||]>>>|>|>|i=0,\,t.>>>> <\proof> We introduce the following auxiliary evaluation morphism over |]>>: <\eqnarray*> |~>:\|]>,\,\|]>>|>||]>>>|>|>|i=0,\,t.>>>> For ,t>, we have <\equation*> |~>,\,\|)>-\|)>=\,\,\,\|)>-\=0, so ,\,\|)>-\\ker |~>> and > is well defined. Let us prove by induction on that > is bijective. This is clear when , so assume that 1>. Let \|]>> be of degree l*d> for some integer0>. The >-adic expansion of yields a polynomial <\equation*> Q|)>=Q+\+Q*\\\|]>|]> such that |)>=P> and \\|]>d>> for ,l-1>. Next we recursively compute ,\,\|)>\\|)>> for ,l-1>. This yields <\equation*> ,\,\|)>\,\,\|)>+\+,\,\|)>*\ with |)>>. This proves that > is surjective. Now let \ker \> be non-zero. Since |)>|)>\d*\*d*deg> >, we must have > \0>, that is \ker \>. The induction hypothesis implies that =0>. As seen in the proof of Lemma, the isomorphism > corresponds to a cascade of >-adic expansions for ,t>. We begin with recalling known costs for univariate expansions over an effective ring >. <\lemma> Let \n>> and let \> be monic of degree . The -adic expansion of can be computed using *log|n/d|\>+1|)>|)>> operations in >. <\proof> Without loss of generality, we may assume that *d> for some integer 0>. We compute ,g,\,g>> using |)>> operations in>. We divide by >>, so +f*g>> with \2*d> and \2*d>. Then we compute the -adic expansion of > and > in a recursive manner so the expansion of is obtained by merging those of > and >. The depth of the recursive calls is |n/d|\>+1|)>|)>>. The sum of the costs of the operations at depth is |)>>, whence the claimed bound. <\lemma> Let ,\,f> be polynomials in d>> and let be a monic polynomial of degree in>. Then, +f*g+\+f*g> can be computed using *log|n/d|\>+1|)>|)>> operations in >, where d*l>. <\proof> Without loss of generality, we may assume that > for some integer 0>. We compute ,g,\,g>> with |)>> operations in>. In a recursive manner we compute \f+f*g+\+f*g> and \f+f*g+\+f*g>, and finally we compute +g*F> with |)>> operations in >. The rest of the complexity analysis follows as in the proof of Lemma. <\remark> When univariate polynomial multiplication is done using FFT techniques, we note that it is possible to save a factor in Lemmas and; see. <\proposition> Let d*\*d>, and write . One evaluation of > modulo >|)>> at an element of degree l> in > (for the canonical representation), and one evaluation of > modulo >|)>> at a polynomial of degree n> in , both take |)>*log n|)>> operations in >. <\proof> Let \|]>> be of degree n>. Its >-adic expansion takes |)>*log l|)>> operations in > by Lemma. Then, we perform calls to > in degree d>. A straightforward induction gives a total complexity bound <\eqnarray*> |||)>*log l+l*|)>*log d+l*d*|)>*\|)>*log d+\|\>>>|||+l*d*\*d**d*\|)>*log d||)>>>||||)>*log n|)>.>>>> The backward conversion makes use of Lemma, and the complexity analysis is similar. <\proposition> Let d*\*d>, and let and be two contact polynomials in > of degreel> in > and given with precision >|)>>. Then, the product can be computed modulo >|)>> with |)>*log n|)>> operations in >, where l*d>. <\proof> The product is computed via the following formula: <\equation*> a*b=\*\|)>+O>|)>. By Proposition the cost of the conversions amounts to |)>*log n|)>>. Multiplying > and > modulo >|)>> incurs |)>|)>>. For actual machine computations, we only work with truncated power series. The decision of whether it is more efficient to use contact representations or the plain representations in |]>> depends on the truncation order. For sufficiently small orders, the \Pcarries\Q can be neglected, which makes it more efficient to conduct computations directly in the contact representation. For large orders, and thus for asymptotic complexity analyses, the overhead of the conversions using isomorphism becomes small, and it is more efficient to perform arithmetic operations in |]>>. Until the end of the paper we perform most of the computations directly in |]>>, and thereby minimize the number of conversions. The isomorphism also allows for efficient Euclidean divisions in > with respect to>, in the sense of Lemma. In fact, let and be as in the lemma, and compute the division of > by >: <\equation*> \=Q*\+R, where deg|)>=d*\*d*n>. The degree in > of the canonical representative of > is therefore n>. It follows that > equals the remainder > of Definition. Since both and have finite degree in >, we note that this also yields an easier way to define the division in comparison to Lemma. In particular, the assumption that > is not needed. <\proposition> Let d*\*d>, and let and be two contact polynomials in > of degreel> in >, and given with precision >|)>>. If is monic in >, then the division of by can be computed modulo >|)>> with |)>*log n|)>> operations in >, where l*d>. <\proof> The division is computed as above via <\equation*> \=\*\+\. By Proposition the conversions take |)>*log n|)>>. Dividing > by > modulo >|)>> incurs |)>|)>>. Recall that > represents the valuation semi-group of the contact tower <\equation*> \\\+\*\+\+\*\. <\proposition> Let |\>> stand for the image of > in >. The valuation |]>\\\|}>> extends to a semi-valuation \\\|}>> with |\>|)>\\> for ,t+1>, and such that > inherits the weighted grading of ,\,\|]>|]>>. <\proof> For \> of canonical representative , we set <\equation*> v\val A. We need to verify that actually defines a semi-valuation in >. If is another element of > of canonical representative , then it is straightforward to verify that \min,v|)>>. As for the product, we compute the long division by the standard basis thanks to Proposition: <\equation*> A*B=Q*-\|)>+\+Q*-\|)>+R, where is the canonical representative of , so =val R>. The latter long division begins with setting A*B> and then it successively subtracts polynomials of the form >*\>*\*\>*-\|)>> from where t>, \>, \\>, and . Since the monomials in have valuation val>, it follows that <\equation*> val\min=val P. This shows that val>. Since =val A+val B>, we deduce that \v+v>. We write A>|valuation of with respect to > A> for the in of \,\,\|]>|]>>. The valuation in of an element of > will be the valuation in of its canonical representative. In the canonical representation, the degrees of the > being bounded, the valuation in of an element in> can be related to > in terms of the >. The following bounds will be useful when converting between the canonical and plain representations. <\lemma> Let \> be of canonical representative ,\,\|)>> for some t+1>. Then we have <\equation*> *> A|)>=v-\*> A|)>\val A\v=val A>. <\proof> Assume 0>. There exists a monomial of the form \ A>*\>*\*\>> in . Using \0> and \d*\> for ,t>, we verify that <\eqnarray*> \v-val A>|>|*\+\+e*\>>||>|-1|)>*\+-1|)>*\+\+-1|)>*\+\*deg> A>>>> and then that <\eqnarray*> \v-val A>|>|*\+-1|)>*\+\+-1|)>*\+\*deg> A>>||>|+-1|)>*\+\+-1|)>*\+\*deg> A>>|||*\+-1|)>*\+\+-1|)>*\+\*deg> A>>||>|+-1|)>*\+\+-1|)>*\+\*deg> A>>|||>>||>|+\*deg> A.>>>> The following lemma asserts that > preserves the valuation in . <\lemma> For all \> we have |)>=val a>. For all \|]>> we have |)>=val A>. <\proof> For any element \>, the inequality |)>\val a> clearly holds. Conversely, for any \|]>>, we have |)>\val A>. It follows that <\equation*> val|)>\val a=val|)>|)>\val|)>, whence the first assertion. The second assertion is a consequence of the fact that > is a |]>>-isomorphism; see Lemma. The next lemma relates valuations and precisions of approximations of and >. <\lemma> Let > and \0> be rational numbers. For all \> we have <\equation*> |]>;\>=+\+l*\>|)>|]>;\>,l\1+deg> a. For all \|]>> we have <\equation*> |]>;\>=+\>|)>|]>;\>. <\proof> Lemmas and give us <\equation> v-l*\\val|)>\v. In particular, if \\+\+l*\> then |)>\\+\>. As for the second assertion, the inequalities are equivalent to <\equation*> val A\v|)>\val A+l*\. In particular, if A\\+\> then |)>\\+\>. <\remark> Lemma can be refined into <\eqnarray*> |]>;\>>||;\+l*\>|)>|]>;\>,l\1+deg> a.>>||]>;\>>||-l*\;l*\+\>|)>|]>;\>,l\1+deg>|)>.>>>> For simplicity we will not use this refinement in the sequel. The usual Hensel lemma asserts that if a monic polynomial \|]>> factors into two monic coprime polynomials > and > modulo , then there exist unique monic polynomials > and > in |]>> such that *>, = mod z>, and = mod z>. In addition, > and > can be obtained with a softly linear cost in the output size. A variant of Hensel lifting is the Weierstraÿ preparation theorem, in which case and > are no longer monic, but > is invertible as a power series in . We will generalize these two kinds of lifting to the contact coordinate framework. Throughout this section, , ,\,a> are elements in >, regarded informally as \Ppolynomials\Q in the main variable >. We will assume that *\*a> holds for a \Psufficient\Q initial precision, and that ,\,a> are \Ppairwise coprime\Q. We want to lift ,\,a> into ,\,> so that *\*> holds up to a required precision. The case when is monic and <\equation*> deg> a=deg>|)> corresponds to the . The case when and <\equation*> deg>|)>\deg> a is called the of . Let \|]>,\,\|]>> be the canonical representative of . We recall that > a=deg> A>, a=val A>, and > is the image of > in>. If is a nonzero element in > that is monic in >, then represents the remainder in the division of by , as specified in Definition. Let be clustered (see Definition) at > and of degree 1> in >. Given \> with > b\l>, its inverse modulo , whenever it exists, belongs to >*\> for some \\>. In order to determine a bound for >, consider \> satisfying <\itemize> > u\l>, \v+v> is an integer 0>, >=u*b rem a>. Lemma yields <\equation*> val u\v-l*\=\-v-l*\. If \v+l*\>, then setting |~>\|\-v-l*\|\>> leads to <\equation*> v+l*\-1\\-|~>\v+l*\. So we may divide by |~>>> and subtract |~>> from> in order to get a \Psimplified\Q modular inverse of that satisfies <\equation> v+l*\-1\\\v+l*\. If \v+l*\-1>, so that |~>\|\-v-l*\|\>\0>, then multiplication of by |~>>> also reduces to the case when() holds. In general, this shows that modular inverses can always be normalized in the sense of the following definition: <\definition> Let be clustered at > of degree 1> in >, and let \> be of degree l> in>. A of with relative precision \0> is an element >\z>*\> with ;\>> such that: <\itemize> > u\l>, \v+v> satisfies =|v+l*\|\>\\>, >=;\>>. If =min\|)>>, then we say that >> is the of . The existence and the computation of such inverses are postponed in section. The next definition concerns the special case when belongs to >. <\definition> Let \> be of degree in > ( is in >). A of is a homogeneous element >\z>*\> such that: <\itemize> \v+v> satisfies =|v+d*\|\>\\>, >=>>. <\lemma> If \> has a normalized initial inverse, then it is unique and =v+v> holds for all \>. <\proof> We have \v+v>. Definition also yields <\equation*> \+v=v\v+v=v+\-v. Concerning the uniqueness, if /z>> represents a normalized initial inverse of then <\equation*> v|)>*b|)>\\ and therefore |)>\\-v>, whence >. <\lemma> If has a normalized inverse modulo with relative precision \0>, as in Definition, then it is unique and rem a|)>=v+v> holds for all \>. <\proof> We extend the contact tower with \a> and apply Lemma in order to obtain the equality for the valuation. As for the uniqueness let /z>> represent another normalized inverse modulo . We have |)>*b|)>\\+\> and thus |)>\\+\-v>, whence >. We explain how to increase the relative precision of a normalized modular inverse, in terms of the contact coordinates. <\proposition> Let \>, \\> and \0>, be such that <\itemize> is clustered at > of degree 1> in >, l>, >> is a normalized inverse of modulo with relative precision \0>. Then, there exists a unique normalized modular inverse /z>> of with relative precision > such that |]>;\>=u>. More precisely, with \v+v> and <\equation*> c\u*>-u*b|)> rem a, we have c\\> and <\equation*> =u++\+\;\>/z>. <\proof> Let > represent an unknown in |]>+\;\>> with > \l>, and which satisfies <\equation> >-|)>*b rem a|]>;2*\>=0. This equation is equivalent to <\equation*> >-u*b rem a|]>+\;\>=*b rem a|]>+\;\>, and, by Lemma, to <\eqnarray*> >-u*b|)> rem a|]>+\+\;\>>||*u*b rem a|]>+\+\;\>>>|||>* rem a|]>+\+\;\>>>|||>*|]>+\+\;\>.>>>> Hence <\equation*> z>*=+\+\;\>. We have >-u*b|)>\\+\>, and therefore \v+\+\>. Lemma implies that\ <\equation*> val c\v+\+\-l*\=\-v+\+\-l*\\\+\-1, so can actually be divided by >>. We conclude that =c/z>> is the unique solution of(), whence =u+> fulfills all requirements. <\corollary> Let be clustered at > of degree 1> in >. If \> admits an initial inverse >> modulo , then there exists a unique >\\> such that >|)>=u> and >=u>*b rem a>. <\proof> Thanks to repeated applications of Proposition we can construct the initial inverse of modulo with any finite relative precision. The existence of>> follows from the completeness of >. The next corollary addresses the precision loss of the initial inverse of modulo when and are truncated modulo >|)>>. <\corollary> Let be clustered at > of degree 1> in >. If \> admits an initial inverse >> modulo , then >> (as defined in Corollary) can be computed modulo -\>|)>> from the truncations of and modulo >|)>>, whenever \\>. <\proof> Let <\equation*> \\|]>>|)>,\\|]>>|)> represent the truncations of of and modulo >|)>>, and let > be the smallest element of> larger or equal to +v-v-\>. Thanks to repeated applications of Proposition we can compute the initial inverse /z>> of > modulo > with relative precision >. Since =|v+l*\|\>=v+v> and =l*\>, we have \v> and therefore \0>. From <\equation*> >-* rem |]>;\>=0, we deduce that <\equation*> >-*b rem a|]>;\>=0+O>|)>. It follows that -u>|)>*b rem a|]>;\>=0+O>|)>> and then that <\equation*> >*-u>|)>*b rem a|]>+v;\>=0+O>|)>. Using >*b rem a=z>>, we obtain that <\equation*> -u>|)>*z>|]>+v;\>=0+O>|)>, hence <\equation*> -u>|]>;\>=0+O-\>|)>. Lemma implies that <\equation*> val-u>|)>\min+\-v,\-\|)>. Thanks to the value taken for > it follows that <\equation*> val-u>|)>\min+v-v-\+v-v,\-\|)>=\-\, whence =u>+O-\>|)>>. We now turn to the Weierstraÿ normalization of an element \>. The following definition gathers the necessary technical conditions and data structures. <\definition> Let \> be of degree 1> in >. A for with relative precision \0> consists of elements ,a,u> in > and \\> that satisfy the following properties: <\description-compact> >>> is clustered at > of degree \1> in >, =|]>|)>;\>>, >>>|)>|)>=0>, =v|)>+v|)>>, =|]>|)>;\>>, >>*a|]>;\>=0>, >>/z>> represents the normalized inverse of > with relative precision >. If =min\|)>>, then we say that ,a,u,\> is an for. The Weierstraÿ lifting step summarizes as follows. <\proposition> Let \> be monic of degree 1> in > and let ,a,u,\> denote a Weierstraÿ context for with relative precision \0>. Then, there exists a unique Weierstraÿ context ,,,\> for with relative precision > such that |]>|)>;\>=a>, |]>|)>;\>=a>, and |]>|)>;\>=u>. More precisely, with <\equation*> b\u*a rem a, we have b\\> and <\eqnarray*> >||+|]>|)>+\+\;\>/z>>>|>|||]>|)>;2*\>.>>>> Letting <\equation*> c\u*>-u*|)> rem , we also have c\\> and <\equation*> =u+|]>|)>+\+\;\>/z>. <\proof> Consider the unknowns \|]>|)>+\;\>> and \|]>|)>+\;\>> such that > \l> and <\equation*> ;2*\>=+|)>*+|)>|]>;2*\>=*a+a*+*a|]>;2*\>. It follows that <\equation*> |]>;2*\>=*a rem a|]>;2*\>. Lemma and the constraints on valuations and precisions equivalently yield <\eqnarray*> *a rem a|]>+v|)>+\;\>>||*a* rem a|]>+v|)>+\;\>>>|||>* rem a|]>+\-v|)>+\;\>>>|||>*|]>+\-v|)>+\;\>>>|||>*|]>|)>+\+\;\>,>>>> whence <\equation*> z>*\*a rem a|]>|)>+\+\;\>. Then Lemma gives <\equation*> val*a rem a|)>\v*a rem a|)>-l*\\v|)>+\+\-v|)>=\+\. This shows that > exists and is uniquely determined by <\equation*> \*a rem a|]>|)>+\+\;\>/z>. The formula for > is straightforward and the one for > follows from Proposition. <\corollary> Let \> be monic of degree 1> in > and let ,a,u,\> denote an initial Weierstraÿ context for . Then, there exist unique >,a>\\> such that >|]>|)>>=a>, >|]>|)>>=a>, and >*a>>. We call >> (that is clustered at >) the of . <\proof> This follows from Proposition and the completeness of >. <\corollary> Let \> be monic of degree 1> in >. If there exists an initial Weierstraÿ context ,a,u,\> for , then >> and >> (as defined in Corollary) can be computed modulo -\>|)>> from the truncation of modulo >|)>>. <\proof> We introduce the truncation \\|]>>|)>> of modulo >|)>>, and set> to the smallest element of > larger or equal to -\>. The quadruple >, >, >, > is an initial Weierstraÿ context for>. From Proposition we know that we can compute the Weierstraÿ context >, >, >, > for > with relative precision >, so that -*|]>;\>=0> and <\equation*> *|]>;\>=0+O>|)>. According to Corollary we may consider the modular inverse > of > modulo >>, so that * rem a>=z>>. Hence <\equation*> *a-**|]>+v|)>;\>=0+O>|)> and <\equation*> >* rem a>|]>+v|)>;\>=0+O>|)>. Lemma implies that <\eqnarray*> rem a>|)>>|>|+v|)>-\+\-l*\,\-\|)>>>|||+v|)>-|)>+v|)>|)>+\-l*\,\-\|)>>>|||-v|)>+\-v|)>,\-\|)>>>|||,\-\|)>>>|||-\.>>>> Since > and >> are monic of the same degree in > we deduce that =a>+O-\>|)>>. The above formulas for the Weierstraÿ lifting can be applied directly in >, but for the sake of efficiency it is worth using plain coordinates. As a technical complication, conversions between contact and plain coordinates result in precision loss. Fortunately, this loss is sufficiently small so that it has no serious impact on the complexity of our top-level factorization algorithm. In the following algorithm, the input and output polynomials use plain coordinates. However, the relative precision>, to be doubled during a lifting step, refers to the contact coordinates. <\specified-algorithm> <\description-compact> A contact tower of height and degree as above, a rational number\0>. A monic polynomial \|]>> modulo +2*\>|)>>, where \>, and polynomials ,A,U> in |]>> modulo +\>|)>>. The elements \|)>|]>|)>|)>;\>> for , \|)>|]>|)>|)>;\>>, and > form a Weierstraÿ context for with relative precision>, as in Definition. ,,> in |]>> modulo +2*\>|)>>, such that the elements \|)>|]>|)>;2*\>> for , \|)>|]>|)>;2*\>>, and > form a Weierstraÿ context for with relative precision > such that |]>|)>;\>=|]>|)>;\>> for and |]>|)>;\>=|]>|)>;\>>. <|specified-algorithm> <\enumerate> Set \v+2*\>. Compute \U*A rem A> in |]>/+\>|)>>. Compute \B/z>> and \A+> in |]>/>|)>>. Compute \A quo > in |]>/>|)>>. Compute \U*>-U*|)> rem > in |]>/+\>|)>>. Compute \C/z>> and \U+> in |]>/>|)>>. Return ,,>. <\proposition> Algorithm is correct and takes <\equation*> O+\|)>|)>|)> operations in >, where deg> a>. <\proof> The hypotheses of Proposition are satisfied. We let <\equation*> b\u*a rem a=\|)>. Lemma implies <\equation*> |]>+\>=|]>+\>|)>|]>+\>. We have seen in Proposition that b\\>, whence B\\> by Lemma. Consequently > is well defined. With the notation of Proposition we verify that <\eqnarray*> >||+b/z>|]>|)>+2*\>>>||||)>|]>|)>+2*\>>>||||]>|)>+2*\>|)>|]>|)>+2*\>>>>> and <\eqnarray*> |]>>|)>|]>|)>+2*\>>|||]>>|)>|]>|)>+2*\>>>|||> quo |]>>|]>|)>+2*\>>>||||]>|)>+2*\>.>>>> By Proposition, properties, , and of Definition thus hold for ,>, and relative precision >. In a similar fashion we verify that <\equation*> |]>+\>=|)>|]>+\>=|]>+\>|)>|]>+\>, so we have <\equation*> |]>|)>+2*\>=+\|)>|]>|)>+2*\>=+\|]>>|)>|]>|)>+2*\>. By Proposition, property holds. We are done with the correctness. The cost analysis is obtained routinely by using =|v|)>+d*\|\>\|v|\>>. Applying successively Algorithm several times enables us to lift any such initial context to any requested precision. The cost is summarized in the following corollaries. <\corollary> Let \> be of degree 1> in > and let ,a,u,\> be \ an initial Weierstraÿ context for . Then, given \0>, we may compute aWeierstraÿ context ,,,\> for with relative precision > using <\equation*> O|)>*log*v|)>|)> operations in >, where =v+\> and *\*d> is the degree of the contact tower. <\proof> We convert the input data into the plain representation modulo>|)>> using Proposition, with |)>*log|)>> operations in >. We successively apply Algorithm to increase the relative precision from |R>> to |R>>, for ,|log*\|)>|\>>. By Proposition, the total cost of the lifting contributesto <\eqnarray*> |||log*\|)>|\>>+|R>|)>|)>|)>>>||||log*v|)>|\>>|)>+|log*v|)>|\>+1>|log*\|)>|\>>|R>|)>|)>>>||||)>*log*v|)>+|)>|)>.>>>> At the end of the lifting, we convert the polynomials to contact coordinates modulo>|)>> via Proposition, again with |)>*log|)>> operations in >. <\corollary> Let \> be of degree 1> in > and let ,a,u,\> form an initial Weierstraÿ context for . Then, given with precision >|)>> with \\>, we can compute its Weierstraÿ part >> (as defined in Corollary) with precision -\>|)>> using <\equation*> O|)>*log|)>|)> operations in >, where *\*d> is the degree of the contact tower. <\proof> The truncation of >> at precision >|)>> does not depend on >, as long as the initial Weierstraÿ context properties are preserved. In particular we may set > to the largest slope of >> (which is > if >> is a power of >), so we have \>*\> where \deg> a>, whence <\equation> R\R*l\d*l. We use Corollary with relative precision \\-\>, as in the proof of Corollary. The running time is <\equation*> O+\|)>|)>*log*v|)>|)> which yields the claimed bound thanks to inequality and <\equation*> v+\=v+\-\=v+\-|v|)>+d*\|\>\v+\--1|)>=\+1. We now turn to the lifting of a factorization of an element \>, assuming that suitable approximate modular inverses are known. The following definition gathers the necessary technical conditions and data structures. <\definition> Let be clustered at > of degree 1> in >. A for with relative precision \0> consists of elements ,\,a,u,\,u> in > and integers ,\,\> that satisfy the following properties: <\description-compact> >>For ,s>, > is clustered at > of degree \1>, and has relative precision >, >>=v|)>+\+v|)>>, and +\+l>, >>*\*a|]>;\>=0>, >>For ,s>, >|)>=v> rem a|)>> and /z>> is the normalized inverse of >> modulo > with relative precision >, where >\a*\*a*a*\*a>. If =min\|)>>, then we say that ,\,a,u,\,u,\,\,\> is an for. Informally speaking, the assumption that >> admits a normalized initial inverse modulo > for ,s> corresponds to the idea that ,\,a> are \Pinitially coprime\Q. We revisit the classical Chinese theorem in this context. <\lemma> Given a Hensel context as in Definition, the following formula holds in|]>>: <\equation*> 1=*>/z>+\+u*>/z>|]>>. <\proof> Let us write <\equation*> c\u*>/z>+\+u*>/z>\\|]>. By construction this yields <\equation> 1=*>/z> rem a|]>>=|]>> for ,s>. Assume by induction that there exists \\|]>> such that <\equation> 1=*a*\*a|]>>. holds for some 1>, which is indeed the case for by. Combined with for , there exists \\|]>> such that <\equation> 0=*a*\*a-*a|]>>. Since *\*a> is initially invertible modulo >, Corollary yields the existence of the initial inverse /z>\\|]>> of *\*a> modulo >, so there exists \\|]>> such that <\equation*> 1=v*a*\*a/z>-* \ a. Combining the latter equality to gives <\equation*> 0=--v*/z>|)>**a|]>*\*a|)>;\>, thanks to Lemma and. In this way, equality holds for with \-v/z>|)>*>. At the end of the induction equality holds for , and since > c\deg> a>, we finally deduce that |]>*\*a|)>;\>=0>. Given clustered at >, we can increase |)>t>> with \a> and \\>. The contact tower |)>t+1>> obtained in this way corresponds to the quotient ring />: in the sequel /> is endowed with the semi-valuation induced by >. <\proposition> Given a Hensel context as in Definition, the map <\eqnarray*> :/*\*a|)>|]>;\>>|>|/|)>|]>;\>\\\/|)>|]>;\>>>||>||]>;\>,\,|]>;\>|)>>>>> is a >-linear isomorphism and we have ,\,c|)>\;\>>, where <\equation*> c\*c/z> rem a|)>*>+\+*c/z> rem a|)>*>. <\proof> It is clear from the assumptions that the map is well defined and >-linear. Let <\equation*> ,\,c|)>\/|)>|)>;\>\\\/|)>|)>;\>. From Lemma we have <\equation*> v*c rem a|)>=v|)>+v|)>\\-v> rem a|)>+v=\-v>|)>+v=v|)>+\, so Lemma implies <\equation*> val*c rem a|)>\\. If follows that *c rem a|)>/z>> belongs to > and that *c/z> rem a|)>*>|)>\v>. By construction we have <\equation*> \;\>|)>=|]>;\>,\,|]>;\>|)>=,\,c|)>, that proves that > is surjective. Let /*\*a|)>|)>;\>> be in the kernel of >. There exists \\> such that *a|]>;\>> for ,s>. By Lemma we deduce that <\equation*> b=*>*q*a/z>+\+u*>*q*a/z>|]>;\>, whence ;\>=0>. Consequently > is injective. The Hensel lifting step goes as follows. <\proposition> Let be clustered at > of degree 1> in >. Let ,\,a,u,\,u,\,\,\> represent a Hensel context for with relative precision \0>. Then, there exists a unique Hensel context ,\,,,\,,\,\,\> for with relative precision > such that |]>|)>;\>=a> and |]>|)>;\>=u> for ,s>. More precisely, letting <\equation*> b\u*a rem a, for ,s>, we have b\\>, <\equation*> =a+|]>|)>+\+\;\>/z>. Letting i>> and <\equation*> c\u*>-u*e|)> rem ,for >i=1,\,s, we also have c\\> and <\equation*> =u+|]>|)>+\+\;\>/z>. <\proof> For ,s>, let us consider unknowns > in |]>|)>+\;\>> such that > \l> and <\equation*> ;2*\>=+|)>*\*+|)>|]>;2*\>. After expanding the right-hand side of the latter equation, we obtain equivalently that <\equation> *\*a|]>+\;\>=>*+\+>*|]>+\;\>. By Proposition, equality is in turn equivalent to <\equation*> |]>+\;\>=>*|)> rem a|]>+\;\> i=1,\,s. For ,s>, Lemma and the constraints on valuations and precisions then yield <\eqnarray*> *a rem a|]>+v|)>+\;\>>||*>* rem a|]>+v|)>+\;\>>>|||>* rem a|]>+\-v>|)>+\;\>>>|||>*|]>+\-v>|)>+\;\>>>|||>*|]>|)>+\+\;\>,>>>> whence <\equation*> z>*\*a rem a|]>|)>+\+\;\>. Then Lemma gives <\equation*> val*a rem a|)>\v*a rem a|)>-l*\\v|)>+\+\-l*\=\+\. For ,s>, this shows that > is uniquely determined by <\equation*> \*a rem a|]>|)>+\+\;\>/z>, whence ,\,> satisfy the required properties. We finally remark that <\equation*> e rem =*\***\* rem for ,s>, so the formulas for the > follow from Proposition. <\corollary> Let be clustered at > of degree 1> in > and let ,\,a,u,\,u,\,\,\> represent an initial Hensel context for . Then, there exist unique >,\,a>\\> such that >|]>|)>>=a>, for ,s>, and >*\*a>>. <\proof> This follows from a repeated use of Proposition with increasing precision. <\corollary> Let be clustered at > of degree 1> in > and let ,\,a,u,\,u,\,\,\> represent an initial Hensel context for . Then >> (as defined in Corollary) can be computed modulo -\>|)>> for ,s> from the truncation of modulo >|)>>. <\proof> We introduce the truncation \\|]>>|)>> of modulo >|)>> and let> be the smallest element of > larger or equal to -min,s>|)>>. By assumption, ,\,a,u,\,u,\,\,\> form an initial Hensel context for>. From Proposition we know that we can compute the Hensel context ,\,,,\,,\,\,\> for > with relative precision >, so that -*\*|]>;\>=0> and <\equation*> *\*|]>;\>=0+O>|)>. Since /z>> is the initial inverse of *\***\*> modulo >, Corollary ensures the existence of the modular inverse > of *\***\*> modulo >>, which satisfies <\equation*> **\***\* rem a>=z>. It follows that <\equation*> *a-**\*|]>+v|)>;\>=0+O>|)>, whence <\equation*> >* rem a>|]>+v|)>;\>=0+O>|)>. Lemma implies that <\eqnarray*> rem a>|)>>|>|+v|)>-\+\-l*\,\-\|)>>>|||+v|)>-|)>+v-v|)>|)>+\-v|)>,\-\|)>>>|||,\-\|)>>>||>|-\.>>>> Since > and >> are monic of the same degree in > we deduce that =a>+O-\>|)>>. Hensel lifting is performed by the following algorithm that is dedicated to doubling the relative precision of a Hensel context. <\specified-algorithm> <\description-compact> A contact tower of height and degree as above, a rational number\0>. A monic polynomial \|]>> modulo +2*\>|)>>, where \>, and polynomials ,\,A,U,\,U> in |]>> modulo +\>|)>>. Integers ,\,\>> in>. The elements \\|)>>, \\|)>>, and > for ,s> form a Hensel context for with relative precision> as in Definition. ,\,,,\,> in |]>> modulo +2*\>|)>>, such that the elements \\|)>>, \\|)>>, and > for ,s> form a Hensel context for with relative precision >. <|specified-algorithm> <\enumerate> Set \v+2*\>, and |\>\max,\,\|)>>. Compute \A rem A> in |]>/+|\>>|)>>, for ,s>. For ,s>: <\enumerate> Compute \U*R rem A> in |]>/+\>|)>>, Compute \B/z>> and \A+> in |]>/>|)>>. Compute i>> in |]>/+|\>>|)>>. Compute \E rem > in |]>/+|\>>|)>> for ,s>. For ,s>, compute \U*>-U*S|)> rem > in |]>/+\>|)>>. For ,s>, compute \C/z>> and \U+> in |]>/>|)>>. Return ,\,,,\,>. <\proposition> Algorithm is correct and takes <\equation*> O+\|)>|)>*log s|)> operations in >, where deg> a>. <\proof> The hypotheses of Proposition are satisfied. We let <\equation*> b\u*a rem a=\|)>. Lemma implies <\equation*> |]>+\>=|]>+\>|)>|]>+\>. We have seen in Proposition that b\\>, whence B\\> by Lemma. Consequently > is well defined for ,s>. With the notation of Proposition we verify that <\eqnarray*> >||+b/z>|]>|)>+2*\>>>||||)>|]>|)>+2*\>>>||||]>|)>+2*\>|)>|]>|)>+2*\>.>>>> By Proposition, properties, , and of Definition thus hold for ,\,> and relative precision >. In a similar fashion we verify that <\equation*> |]>+\>=|)>|]>+\>=|]>+\>|)>|]>+\>. From Proposition we know that >> divides >, so it divides >. Consequently> is well defined for ,s>, and we have <\equation*> |]>|)>+2*\>=+\|)>|]>|)>+2*\>=+\|]>>|)>|]>|)>+2*\>. By Proposition, property holds. We are done with the correctness. Concerning complexities, from Definition we first observe that <\equation*> \\v>|)>+\*deg> a=v>|)>+v|)>=vv|)>\v|)>, for ,s>. Consequently steps2,4, and5 take <\equation*> O+\|)>|)>*log s|)> operations in > using the sub-product tree technique; see10, Theorems10.6 and10.10>, for instance. The other steps require +\|)>|)>|)>> further operations in >. Applying successively Algorithm several times enables us to lift an initial Hensel context to any requested precision. The cost is summarized in the following corollary. <\corollary> Let be clustered at > of degree in >, and let ,\,a,u,\,u,\,\,\> be an initial Hensel context for . Then, given \0> and \v+\>, we may compute a Hensel context ,\,,,\,,\,\,\> for with relative precision > using <\equation*> O|)>*log*v|)>*log s|)> operations in >, where *\*d> is the degree of the contact tower. <\proof> We convert the input data into the plain representation modulo>|)>> using Proposition, with |)>*log|)>> operations in >. We successively apply Algorithm to increase the relative precision from |R>> to|R>>, for ,|log*\|)>|\>>. By Proposition, the total cost of the lifting contributes to <\eqnarray*> |||log*\|)>|\>>+|R>|)>|)>*log s|)>>>||||log*v|)>|\>>|)>*log s+|log*v|)>|\>+1>|log*\|)>|\>>|R>|)>*log s|)>>>||||)>*log*v|)>*log s+|)>*log s|)>>>||||)>*log*v|)>*log s|)>.>>>> At the end of the lifting, we convert the polynomials to contact coordinates modulo>|)>> using Proposition, again with |)>*log|)>> operations in >. <\corollary> Let be clustered at > of degree in >, and let ,\,a,u,\,u,\,\,\> be an initial Hensel context for . Then, given at precision >|)>> we can compute >> (as defined in Corollary) at precision -\>|)>> for s>, using <\equation*> O|)>*log|)>*log s|)> operations in >, where *\*d> is the degree of the contact tower. <\proof> We use Corollary with the relative precision \\-min,s>|)>> as in the proof of Corollary. The running time is <\equation*> O+\|)>|)>*log*v|)>*log s|)>. Then we verify that <\equation*> v+\-\=v+\-|v>|)>+l*\|\>\v+\--1|)>=\+1. Using \R*l\l*d> the cost of the lifting simplifies to |)>*log|)>*log s|)>>. In this section we introduce the notion of \Pseparability\Q for contact towers. This will allow the construction of derivations on contact towers, which will be the key ingredient of the central shift algorithm in section. Informally speaking, a contact tower is said to be separable when the initial forms of the its defining polynomials> are separable. The precise definition is as follows. <\definition> A tower |)>t>> of contact coordinates as in Definition is said to be when \|\ \>> is initially invertible in >, for ,s>. It is said to be if the normalized initial inverses of the \|\ \>> are known for algorithmic purpose. Throughout this section, we assume that |)>t>> is effectively separable. For ,t>>, \\,\,\|]>> represents the initial inverse of \|\ \>> modulo >. More precisely, we assume that > is homogeneous and satisfies * \|\ \>|)>=z>>, where \\>. From Definition we know that <\equation*> 0\\\-1|)>*\, since \|\ \>|)>=-1|)>*\>. <\example> We define an effectively separable contact tower of height by taking , =\-3>, =0>, =0>, and =\/6>. Indeed, <\equation*> in* \|\ \> rem> \|)>=in|3> rem> \|)>=1, where >> stands for remainder with respect to the variable >. <\example> Consider Example: =\-3> and=\-5*z*\> form a contact tower of height with contact slopes =0>, =1>. We get > and > from =val|)>=val=0> and =val|)>=val*\|)>=2>. As for the modular inverses we may take =0>, =2>, <\equation*> \=|6>,\=*\|30>. Indeed, we verify that <\eqnarray*> * \|\ \> rem> \|)>>||*\|15> rem> \|)>>>|||**\+\|)>|15> rem> \|)>>>||||)>.>>>> Since the map :\\\|]>> is a |]>>-isomorphism, from Lemma, the derivation |\ x>> on |]>> induces a derivation on > (that is still denoted by |\ x>> for simplicity): <\equation*> a|\ x>>|derivative of with respect to >> a|\ x>\\|\ x>|)>|)>. The separability assumption ensures that this derivation satisfies several convenient properties. <\lemma> Let |)>t>> be a separable contact tower. For ,t> we have <\equation*> in \|\ x>|)>=in \|\ \>* \|\ x>|)> and\ <\equation*> v \|\ x>|)>=-1|)>*\+-1|)>*\+\+-1|)>*\. <\proof> We prove the result by induction on . For we have <\equation*> \|\ x>= \|\ \> and <\equation*> v \|\ x>|)>=val \|\ \>|)>=-1|)>*\. For ,t> we have <\equation*> \|\ x>= \|\ \>+ \|\ \>* \|\ x>+\+ \|\ \>* \|\ x>. By Lemma, the separability assumption yields <\eqnarray*> \|\ \>* \|\ x>|)>>|| \|\ \>|)>+v \|\ x>|)>.>>>> Combined with the induction hypothesis we deduce <\eqnarray*> \|\ \>* \|\ x>|)>>||-1|)>*\+-1|)>*\+\+-1|)>*\.>>>> On the other hand, for i> we have <\equation*> v \|\ \>* \|\ x>|)>\d*\-\+-1|)>*\+\+-1|)>*\, and therefore <\eqnarray*> ||| \|\ \>* \|\ x>|)>-v \|\ \>* \|\ x>|)>>>||>|*\-\--1|)>*\--1|)>*\-\--1|)>*\>>|||--1|)>*\-\--1|)>*\-\>>|||-d*\|)>+\+-d*\|)>>>||>|>>>> We now study the effect of several consecutive differentiations in . <\lemma> Let |)>t>> be a separable contact tower. For any \> we have <\eqnarray*> c|\ x>|)>>|>|+*\-\|)>+\+*\-\|)>-\>>|||-\+v \|\ x>|)>.>>>> <\proof> The inequality follows from <\equation*> c|\ x>= c|\ \>* \|\ x>, Lemma, and the inequality <\equation*> -\+-1|)>*\+\+-1|)>*\\-\+-1|)>*\+\+-1|)>*\ for ,t-1>. <\lemma> Let |)>t>> be a separable contact tower and let \> be such that <\equation*> v \ a|\ \>|)>=v-\. Then we have <\equation*> in a|\ x>|)>=in \|\ x>* \ a|\ \>|)>. <\proof> Writing *\+\+c>, we have <\equation*> \ a|\ x>= \|\ x>* \ a|\ \>+ c|\ x>*\. Then, for ,l>, we have |)>\v-j*\> so Lemma yields <\equation*> v c|\ x>*\|)>\v-\+v \|\ x>|)>. On the other hand, <\equation> v \|\ x>* a|\ \>|)>=v-\+v \|\ x>|)>, so Lemma implies <\equation*> c|\ x>*\|)>-v \|\ x>* a|\ \>|)>\\-d*\\0> and <\equation*> in a|\ x>|)>=in \|\ x>* a|\ \>|)>. <\lemma> Let |)>t>> be a separable contact tower. Given \> and 0> such that <\equation*> v a|\ \>|)>=v-k*\, we have <\equation*> in a|\ x>|)>=in \|\ x>|)>* a|\ \>|)>. <\proof> First note that <\equation*> v a|\ \>|)>=v-j*\ holds for all k>. We prove the lemma by induction on . The result is clear for , so assume that 1>. The induction hypothesis implies that <\equation> a|\ x>= \|\ x>|)>* a|\ \>+R for some such that <\equation*> v\v a|\ x>|)>. Differentiating with respect to >yields <\equation> |\ \> a|\ x>=|\ \> \|\ x>|)>* a|\ \>+ \|\ x>|)>* a|\ \>+ R|\ \>. Since \|\ x>|)>> does not depend on >, the initial form of \|\ x>|)>> also does not depend on>. It follows that <\equation*> v|\ \> \|\ x>|)>|)>\v \|\ x>|)>|)>-\, whence <\equation> v|\ \> \|\ x>|)>* a|\ \>|)>\v \|\ x>|)>* a|\ \>|)>. Equation, the assumption on , and the definition of imply that <\equation> v R|\ \>|)>\v-\\v a|\ x>|)>-\=v \|\ x>|)>* a|\ \>|)>. By combining, , and we deduce <\equation> in|\ \> a|\ x>|)>=in \|\ x>|)>* a|\ \>|)>. On the other hand Lemma gives us <\equation> in a|\ x>|)>=in \|\ x>*|\ \> a|\ x>|)>. We conclude the proof by combining equations and. Canonical representations are not always the most efficient ones for computations with initial forms. This can be already observed in the case when . Indeed, let us write\ <\equation*> in|)>=\>+c-1>*z-1>>*\-1>+\+c*z>, with \\> and \\> for ,d-1>. Let > and \1> be coprime integers such that <\equation*> \=|r>=|d>. Then, the coefficient > is zero whenever is not a multiple of >. This shows that |)>> is sparse in the sense that it contains at most \d/r> non-zero terms besides >>. In particular, computations that use the dense representation are deemed to be suboptimal. Assume for instance that we need to compute the valuation and the initial inverse of\>. We first extract the initial part of its canonical representative ; there exist ,r-1|}>> and ,\,a-1>\\> such that <\equation*> in=a-1>*z--1|)>*f-k*|r>>*\-1|)>*r+k>+\+a*z-k*|r>>*\, where \val A>. Note that > is again sparse. We now have to compute the Bézout relation of the specializations at of > and |)>> in |]>>. Without exploiting the sparsity, this computation takes |)>*log d|)>> operations in >. In this particular case, the remedy is to compute with respect to >> instead of >, while exploiting the fact that *\> and |)>> are dense polynomials in >>. In order to generalize this remedy to the case when 1>, we show in this section how to rewrite sparse homogeneous polynomials in |]>,\,\|]>> into suitable products of coefficients in \Palgebraic towers\Q |)>t>> over > and \Pmonomials\Q. In all computations below, |)>t>> will be an effectively separable contact tower (as in Definition) that satisfies the following additional property. <\definition> With the notation of Definition, a contact tower of height is said to be when ,\,\,0|)>> has valuation *\> and is initially invertible, for ,s>. It is said to be if the normalized initial inverse of ,\,\,0|)>> is known for algorithm purpose, for ,s>. This regularity assumption implies that > is determined by <\equation*> \=>*val,\,\,0|)>|)>. An over > is a sequence |)>t>> with \\> and \\|]>/|)>|)>>, for ,t> and monic polynomials |)>\\|]>>. We will write > for the image of> in > and set \deg \> for ,t>. The tower is said to be when we are given and in |]>> of respective degree deg \> and deg \-1> such that the Bézout relation <\equation*> 1=u*\+v*\ holds, for ,t>. The next definition concerns the alternative representation of homogeneous polynomials modulo |)>,\,in|)>|)>>. <\definition> An consists of the following data: <\itemize> An effectively separable tower <\equation*> \\\\\\|]>/|)>|)>,i=1,\,t, where > is monic of degree \0> in |]>>. The class of > in > is written>. For ,t> the inverse of > exists and is known. A tower of purely ramified extensions of \\|]>>, written <\equation*> \\\,\,y|]>/>-b*\*z>,\,y>-b*\*z>*y>*\*y>|)>, where ,\,r> are positive integers called , <\equation*> ,\,f|)>\\\,r-1|}>\\\,r-1|}>, for ,t>, and > is invertible in > for ,t-1>. The class of > in > is written >. \\> and a uniformizing parameter \\> such that >=\*z>, where \r*\*r>, for ,t>. \\>> coprime with > along with integers > and > such that >=\>*\> and *r+v*f=1>, for ,t>. > The construction of an initial expansion associated to a contact tower is achieved by induction on. This subsection is devoted to the case when . As in the introduction of this section, we write <\equation*> in|)>=\>+c-1>*z-1>>*\-1>+\+c*z>, with \\> and \\> for ,d-1>. Note that \0> because the tower is regular. As before, we let > and \1> be coprime integers such that <\equation*> \=|d>=|r>. We define <\equation*> \|)>\x>+c-r>*x-1>+\+c>*x+c, where \d/r>. Note that =0> whenever is not a multiple of >. The inverse of > is: <\equation*> \=|)>-\|-\*x>|)>|)>. With \f> and \1>, the map <\eqnarray*> :\|)>|]>/|)>|)>>|>||]>>>|>|>|,>>>> is well defined because <\eqnarray*> |)>|)>|)>>||>+c-r>*z>*\-r>+\+c*z*f/r>>>|||>|)>>+c-r>*z>*>|)>-1>+\+c*z*s>>>|||*z>|)>>+c-r>*z>**z>|)>-1>+\+c*z*s>>>||||)>*z*s>>>|||>>> Let us now show how to compute conversions >. Let \|]>d>> be homogeneous of valuation > and write <\equation*> A=a-1>*z--1|)>*f-k*|r>>*\-1|)>*r+k>+\+a*z-k*|r>>*\ with ,r-1|}>>. Then the formula <\equation*> \=z-k*|r>>*\*-1>*\-1>+\+a*\+a|)> allows for the computation of > without any arithmetic operations or zero tests. This also shows that > is an isomorphism. Assume that two elements >*\>> and >*\>> in |]>> with \\\\r> have the same valuation, that is <\equation*> \+\*|r>=\+\*|r>. If =0> (that corresponds to =0>), then =1> so =\=0> and therefore =\>. Otherwise we have <\equation*> -\|)>*f=-\|)>*r, and > and > are coprime. So > divides -\>, whence =\> and =\>. In other words, any homogeneous element in |]>|]>> can be written in a unique way as >*\>> with \>, \\>, and \\r>. Now consider the Bézout relation *r+v*f=1> between > and >, with |\|>\f> and |\|>\r>. The element <\equation*> \\z>*\>\\|]> has valuation >. From <\equation*> \>=z*r>*\*r>=z*f>*\*r>=z*f>**z>|)>>=\>*z and <\equation*> \>=z*f>*\*f>=z*f>*\*r>=z*f>*\**z>|)>>=\>*\, we obtain formulas to rewrite and > in terms of >: <\equation*> z=\>*\>,\=\>*\>. Consequently > is a of |]>>, whose valuation group is <\equation*> |\>=>*\, and \\>>. In particular, > is a purely ramified extension of >. It remains to make |)>1>> effectively separable. To this end, we first compute <\eqnarray*> \|\ \>|)>|)>>|||\ \>*s>+c-r>*z>*\-1|)>>+\+c*z*s>|)>|)>>>|||*\*-1|)>>+-1|)>*c-r>*z>*\-2|)>>+\+c>*z*-1|)>>|)>*r*\-1>|)>>>|||*\-1>*z*-1|)>>+-1|)>*c-r>*\-2>*z*-1|)>>+\+c>*z*-1|)>>|)>*r*\-1>>>|||*\|)>*z*-1|)>>*\-1>.>>>> Let > and > be such that * \|\ \>|)>=z>> and let |)>*z>*\>\\|)>|)>> be such that \\r-1>. Then we have <\eqnarray*> >>|||)>*z>*\>*r*\|)>*z*-1|)>>*\-1>>>|||*\|)>*\|)>*z+f*-1|)>>*\+r-1>.>>>> Necessarily =1> and *\*\|)>> is the inverse of |)>>. From this inverse we easily recover the Bézout relation of > and>, that makes the tower |)>1>> effectively separable. 2>> The next lemma deals with the construction of an initial expansion associated to a contact tower. We extend the above construction for . <\lemma> Given an effectively separable and regular contact tower |)>t>>, there exists an initial expansion such that each > divides >, and <\eqnarray*> :\|)>,\,\|]>/|)>|)>>|>||]>>>|>|>|for >j=1,\,i,>>>> is a |)>>-algebra isomorphism, for ,t>. We set \d/r>. In addition, with \r*\*r>, |]>> has valuation group <\equation*> |\>=>*\. The algebra |]>> inherits the grading of |)>,\,\|]>>. We still write for the semi-valuation induced over |]>>, so =1> and |)>=\> for ,t>. Any homogeneous element of |]>> can uniquely be written as >*\>*\*\>>, where \> and <\equation*> ,\,\|)>\\\,r-1|}>\\\,r-1|}>. <\proof> We prove the lemma by induction on The case has been addressed in the previous subsection, so we assume that 2> and recall that > is a uniformizing parameter of|]>>. We write <\equation*> in|)>=\>+C-1>*\-1>+\+C, where \\,\,\|]>> is homogeneous for ,d>. Then we define <\equation*> c*\>\\|)>, where \\> and \\>, for ,d-1>. We introduce <\equation*> s\gcd,e|)>,r\|s>,f\|s>, so we have <\equation> \=|d*R>=|r*R>. Since the tower is regular, > is invertible. Since |)>> is homogeneous, we have =0> whenever is not a multiple of > and <\equation*> e-j*r>+-j*r|)>*|r>=d*|r> for ,s>. The latter equation is equivalent to <\equation*> e-j*r>=j*f. We define > as <\equation*> \|)>\x>+c-r>*x-1>+\+c>*x+c and <\equation> \>=\*\>. The inverse of > is then given by <\equation> \=|)>-\|-\*x>|)>|)>. From the induction hypothesis, >> can uniquely be rewritten as <\equation*> \>=b*z>*\>*\*\>, where > is invertible in > and ,\,f|)>\\\,r-1|}>\\\,r-1|}>>. We also have <\equation*> v>|)>=r*v|)>=r*\\r*d*\, so Lemma further yields <\eqnarray*> =val>*\>*\*\>|)>>|>|>|)>-r*\>>||>|*d*\-r*\>>||>|>>> Inside >, the following equalities hold: <\eqnarray*> >+c-r>*\>*\-r>+\+c*\*f>>||>|)>>+c-r>*\>*>|)>-1>+\+c*\*f>>>|||*\>|)>>+c-r>*\>**\>|)>-1>+\+c*\*f>>>||||)>*\*f>>>|||>>> which shows that > is well defined. Let \,\,\|]>> be homogeneous of valuation >, such that > A\d> for ,t>, and let us write it in the form <\equation*> A=A-1>*\-1|)>*r+k>+\+A*\+k>+A*\, with > homogeneous in ,\,\|]>> and ,r-1|}>>. Then <\eqnarray*> |>||-1>|)>*\-1|)>*r+k>+\+\|)>*\+k>+\|)>*\>>|||-1>|)>**\>|)>-1>+\+\|)>*\*\>+\|)>|)>*\>>>> shows that it is straightforward to compute > recursively, and that > is a |)>>-algebra isomorphism; an explicit recursive formula for > will be given in the proof of Proposition below. Now assume that two elements >*\>> and >*\>>, with \\\\r>, have the same valuation, that is <\equation*> |r*\*r>+\*|r*\*r>=|r*\*r>+\*|r*\*r>, or, equivalently <\equation*> -\|)>*f=-\|)>*r. Since 2>, from Definition, \0>, and since > and > are coprime, > divides -\>, whence =\> and =\>. In other words, any homogeneous element in |]>> can be uniquely written >*\>> with \>, \\> and \\r>. Let <\equation*> 1=u*r+v*f be the Bézout relation of > and >, with |\|>\f> and |\|>\r>. The element <\equation*> \\\>*\>\\|]> has valuation <\equation*> |r*\*r>+*f|r*\*r>=*r+v*f|r*\*r>=*\*r>. On the other hand we verify that <\equation> \>=\*r>*\*r>=\*f>**\>|)>>=\>*\ and <\equation> \>=\*f>*\*f>=\*f>*\*r>=\*f>*\>|)>>*\=\>*\. Consequently, the valuation group of |]>> is <\equation*> |\>=*\*r>*\, and > is a uniformizing parameter. In addition we have <\equation*> \>=>*\|)>>=\*R>*\*z, whence <\equation> \=\*R>*\. In order to show that |)>t>> is separable, we verify that <\eqnarray*> \|\ \>|)>|)>>|||\ \>*s>+c-r>*\>*\-1|)>>+\+c*z*f/r>|)>|)>>>|||*\*-1|)>>+-1|)>*c-r>*\>*\-2|)>>+\+c>*z*-1|)>>|)>*r*\-1>|)>>>|||*\-1>*\*-1|)>>+-1|)>*c-r>*\-2>*\*-1|)>>+\+c>*\*-1|)>>|)>*r*\-1>>>|||*\|)>*\*-1|)>>*\-1>.>>>> Let > and > be such that * \|\ \>|)>=z>> and let |)>*\>*\>\\|)>|)>> be such that \\r>. Then we have <\eqnarray*> >>|||)>*\>*\>*r*\|)>*\*-1|)>>*\-1>>>|||*\|)>*\|)>*\+f*-1|)>>*\+r-1>.>>>> It follows that =1> and <\eqnarray*> >>||*\|)>*\|)>*\*\+f*s>>>|||*\|)>*\|)>*\*\>,>>>> whence <\equation> |)>|)>=r*\*\|)>*\>. From this inverse we easily recover the Bézout relation of > and> so the tower |)>t>> is effectively separable. Before turning the above construction of the initial expansion into an algorithm, we study the costs of the conversions > and >. We recall from section that products in > take *\*s|)>>|)>> operations in >. <\proposition> Assume that we are given an initial expansion of a contact tower, and let be homogeneous of valuation \0> in |]>,\,\|]>/|)>|)>>. Recall that \r*\*r>. Then we can compute > in the form *R>> with \> using <\equation*> **\*s|)>>*log*R|)>*t|)> operations in >. Conversely, given *R>> with \>, we can compute <\equation*> \*R>|)>\\|)>,\,\|]>/|)>|)> with the same cost bound. In addition, if \> has degree l> in > and if > divides *R>, then we can compute *R>|)>> using <\equation*> *\*s|)>>*log*R|)>*t|)> operations in >. <\proof> Let denote the canonical representative of . There exists such that k\r-1> and <\equation*> A=\*-1>C*j+k>*\*j>. For ,s-1> we recursively compute *\-*j+k|)>*\|)>*R>\\*j+k>|)>> with \\>. Then we verify <\eqnarray*> >||*-1>\*j+k>|)>*\*j>>>|||*-1>c*\-*j+k|)>*\|)>*R>*\*j>>>|||*-1>c*\-*j+k|)>*\|)>*R>*\*\*j>)>>>|||-1>c*\|)>*\-k*\|)>*R>*\)>>>|||-1>c*\|)>*\*-k*\|)>**R+u*k>*\*R>.,, and)>>>>> Recall that the inverse of > is at our disposal and that the > belong to >. So we need to compute *-k*\|)>*R+u*k>> using binary powering and fast tower arithmetic. Then, we multiply this quantity by -1>c*\>. These products require <\equation*> **\*s|)>>*|\|>*-k*\|)>*R+|\|>*k|)>+1|)>|)> operations in >. Since |\|>\r> and |\|>\f=\*R>, we may simplify <\equation*> log|\|>*-k*\|)>*R+|\|>*k|)>\log-k*\|)>*R+k*\*R|)>=log*R|)>. Let |)>> be the cost of evaluating > at any valuation \>. We have shown that <\equation*> |)>=s*|)>+**\*s|)>>*log*R|)>|)>, whence <\equation*> |)>=O**\*s|)>>*log*R|)>*t|)>. The above formulas can be read in reverse order for performing a backward conversion>, with a similar cost; note that *\*R mod r>. The second assertion of the proposition corresponds to the special case where , which leads to the cost |)>> via the following formulas: <\eqnarray*> c*\|)>*\*R>|)>>||c*\-r*j*\|)>*R>*\*\**j>|)>>>|||\*\-r*j*\|)>*R>*\|)>>>|||\*\-r*j*\|)>*R>|)>*\.>>>> Having shown how the conversions > and > can be computed efficiently, let us now turn to the incremental construction of an initial expansion. We keep the same notation as in section. <\proposition> Given the initial forms |)>,\,in|)>> of an effectively separable and regular contact tower, an initial expansion can be computed using <\equation*> **\*s|)>>*log*\*d|)>*t|)> operations in >. <\proof> The case has been detailed in section: it takes <\equation*> *log*v|\|>|)>|)>=*log*r|)>|)>=*log*\*r|)>|)> arithmetic operations in >. By induction on we may assume that the initial expansion has been computed up to height. We write <\equation*> in|)>=\>+C-1>*\-1>+\+C, with the > homogeneous in ,\,\|]>>. Since =d*\> and \d>, Proposition allows us to compute >|)>> for ,s-1> using <\equation> **\*s|)>>*log*\*d|)>*t|)> operations in >. This is sufficient to obtain>. If /z>> stands for the normalized initial inverse of >, then we can compute *\>=T|)>>. Hence <\equation*> z>=T|)>*T|)>=c*\>c*\>=c*c*\>*z>, so the computation of the inverse of > requires one evaluation of > at > and |)>=O*\|)>|)>> products in >. The inverse of > is then obtained via with |)>> operations in >. The cost of these two tasks does not exceed the bound. The computation of the inverse of > modulo > then requires one evaluation of> at the initial inverse of \|\ \>>, then |)>=O*\|)>|)>> products in >, and > products in>, by using formula. The second cofactor of the Bézout relation of > and >, namely |)>/\>, requires |)>|)>=|)>> further operations in >. By using formula, the computation of > from > takes <\equation*> O|\|>*R|)>|)>=O|R|)>|)> operations in >, that is **\*s|)>>*log d|)>> operations in >. The sum of the costs for all levels of the tower is bounded by <\eqnarray*> ||s**\*s|)>>*log*\*d*d*\|)>*t|)>>>|||**\*s|)>>*log*\*d|)>*t|)>.>>>> In this section we apply the lifting algorithms of section in order to compute so-called of a polynomial that is clustered at > (Definition). These are partial factorizations that are related to the of with respect to the current contact coordinates (Definition). Until the end of the paper, contact towers will be effectively separable (Definition) and regular (Definition). Since we occasionally will have to manipulate multiple contact towers at multiple levels, it is convenient to <\itemize> regard an element \> as an element in any other > via the natural isomorphism\\>; write <\equation*> |)>>|>>>in|)>,|)>>| regarded in >>>v|)>,|]>;\>>| regarded in >>>|]>;\> for the initial form, the valuation, and the truncation of , when regarded as an element in >; given \|]>,\,\|]>>, write <\equation*> in|)>v|)> for the initial form and the valuation of ,\,\|)>> in >. Since we assumed from the outset that we have an algorithm or oracle for factoring univariate polynomials over >, we are interested in factoring elements of |]>> into irreducible factors. There is a corresponding notion of irreducible contact towers and, thanks to our oracle, all contact towers that we will need for our main factoring algorithm can be forced to be of this type. <\definition> A homogeneous contact polynomial \> is said to be if there exists > and > homogeneous in \\> such that |)>=in*a;\|)>>. A contact tower |)>t>> is if ;\|)>> is initially irreducible for ,t>>. In view of the initial expansion |)>t>> and |)>t>> of a contact tower |)>t>>, we observe from Lemma that |)>t>> is irreducible if and only if > is a field. Equivalently, |)>t>> is a tower of field extensions. In this case, any non-zero element in > admits a unique normalized initial inverse. <\proposition> A separable contact tower |)>t>> is irreducible if and only if ;\|)>> is irreducible. <\proof> If |)>t>> is reducible then their exists a smallest index such that > admits an initial factorization regarded in >. This initial factorization yields an initial Hensel context that can be lifted into a non trivial factorization of ;\|)>> by Corollary. Conversely assume that |)>t>> is irreducible and let be a factor of ;\|)>>. Then, |)>> initially divides ;\|)>>, hence cannot be a non trivial factor of ;\|)>>. The next lemmas are devoted to the complexity of initial inversions. <\lemma> Let |)>t>> be an effectively separable, regular, and irreducible contact tower, and assume that its initial expansion has been precomputed. Let \> be homogeneous and of valuation in . Then, admits a unique normalized initial inverse, that can be computed with <\equation*> **\*d|)>>*log*\|)>|)>=>*log*\|)>|)> operations in >. <\proof> From Lemma we know that \d*\>. The computation of <\equation*> \=c*\*R> takes <\eqnarray*> **\*s|)>>*log*R|)>*t|)>>||**\*s|)>>*log*\*R|)>*t|)>>>|||**\*d|)>>*log*\|)>|)>>>>> operations in > by Proposition. Then we compute *\|v|\>>> in time <\equation*> O**\*s|)>>*log*\|)>|)>=O>*log*\|)>|)>. Proposition allows us to obtain <\equation*> u\\*\|v|\>>*\*|v|\>-v|)>>|)>\\|]> with **\*d|)>>|)>> further operations. Since \0>, Lemma implies u\-d*\>. We verify that <\eqnarray*> |)>>||\|v|\>>*\*|v|\>-v|)>>*c*\*v>*>>||||v|\>>*\*|v|\>>>>||||v|\>>,>>>> by using identity >=\*z> stated in Definition. It follows that =z|v|\>>>. After multiplying or dividing by a suitable power of we obtain the normalized initial inverse of. <\lemma> Let |)>t>> be an effectively separable, regular, and irreducible contact tower, and assume that its initial expansion has been precomputed. Let be clustered at > of degree 1> in > such that > does not divide >, and let \> be homogeneous of degree l> in > and of valuation in . We can test whether admits a normalized initial inverse modulo or not, and if so compute this initial inverse with >*log|)>|)>> operations in >. <\proof> We increment the tower |)>t>> with =in>. The extended tower is not necessarily separable or irreducible because of its top level, but this does not prevent from building the corresponding incremented initial expansion with the difference that > is not a field extension of >, that is not even necessarily separable. By Proposition this \Palmost initial expansion\Q incurs >*log|)>|)>> operations in>. The conclusion follows from Lemma: still writing =c*\*v>>, the required initial modular inverse exists if and only if is invertible in >. The following lemma asserts that is clustered at any > for t-1> as soon as it is clustered at>. <\lemma> Let \> be clustered as in Definition, of degree in >. Then, for ,t>>, the polynomial is clustered at >, and we have |)>=m*\> where \d*\*d*l>. <\proof> Note that > is monic in of degree >. Therefore is monic in > of degree > when regarded in >, for ,t>. The rest of the proof is done by induction on from down to. The case corresponds to the hypothesis of the lemma. Now let us assume that |)>=m*\> holds for some t>, and consider the contact representation <\equation*> a=\>+c-1>*\-1>+\+c in >, with <\equation*> v;\|)>=v;\|)>\-j|)>*\ for ,m-1>. It follows that <\eqnarray*> *\;\|)>>|>|-j|)>*\+j*d*\>>||>|-j|)>*d*\+j*d*\>>|||*m*\,>>>> where the second inequality is strict for m>. Consequently, |)>=m*\>. <\definition> Let |)>t>> be an effectively separable, regular, and irreducible contact tower and let \> be clustered at |)>t>>. An of at precision >|)>> is a sequence of pairs >,>|)>t>>|)>> modulo >|)>> for ,n>, such that: <\itemize> >|)>t>>> is an effectively separable, regular, and irreducible contact tower for ,n>; \t> and >|)>t>=|)>t>> for ,n>; >\\>>> is a power of the last contact coordinate >+1>> of >>> for ,n>; >*\*a>+O>|)>> (this equality can be regarded equivalently in any > for t>). Consider a contact polynomial <\equation*> a=c*\+c*\+\+c\\, with \\> for ,l> and \0>. The \\\\|}>|)>> of is the lower border of the convex hull of the set of pairs > with i\l> and v|)>>. More precisely, > is a broken line with vertices ,j|)>,\,,j|)>>, where <\itemize> \\\i=l>, =v>|)>> for ,r>, for all ,l> such that \0>, the point |)>|)>> is on or above the Newton polygon. Any ,r> determines an edge > between the vertices ,j|)>> and ,j|)>>, of slope -j|)>/-i|)>>. The set of points above the Newton polygon is convex. When =0> we have =+\>, so the slope of the first edge is >. In order to establish the usual relationship between > and the Newton polygons of the factors of, we introduce the following definition. <\definition> With the above notation, the Newton polygon ,j|)>,\,,j|)>> of \> is said to be when the elements >> are initially invertible in >, and we are given the normalized initial inverses /z>> of >> for ,r>. If =0> then we set \0> by convention. The following lemma extends a special case of a classical result about Minkowski sums of polytopes due to Ostrowski (translated in, and revisited later in). In our variant we need to take care of \Pcarries\Q involved by the contact arithmetic. <\lemma> Let >c*\> and >c*\> be contact polynomials in >. Their respective Newton polygons =,j|)>,\,>,j>|)>|)>> and =,j|)>,\,>,j>|)>|)>> are assumed to be regular, the slopes of > are strictly smaller than the ones of >, and all slopes are -\>. If \0>, >=1>, \0>, and >=1>, then the Newton polygon > of equals <\equation*> \=,j|)>+,j|)>,\,>,j>|)>+,j|)>,\,>,j>|)>+>,j>|)>|)>. In addition, the contact polynomial <\equation*> a*b=+l>c*\ satisfies +i>|)>=in>*c>|)>> for ,r> and >+i>|)>=in>>*c>|)>> for ,r>. <\proof> First of all, note that the hypothesis on the slopes guarantees that the region of the plane above the Newton polygon <\equation*> \\,j|)>+,j|)>,\,>,j>|)>+,j|)>,\,>,j>|)>+>,j>|)>|)> is actually convex. Let ,j|)>> be a point above >. For all ,r>, we have <\equation> j-j\-j|i-i>*-i|)>. Similarly, for any point ,j|)>> above > and for all ,r> we have <\equation> j-j\-j|i-i>*-i|)>. Since the slope of the edge ,j|)>,,j|)>|)>> is smaller than the slope of ,j|)>,,j|)>|)>>, for ,r>, we obtain <\equation*> j-j\-j|i-i>*-i|)>\-j|i-i>*-i|)>,i\i. Combining the latter inequality with leads to <\equation*> j+j-j-j\+j|)>-+j|)>|+i|)>-+i|)>>*+i-i-i|)>, which means that +i,j+j|)>> is above the line spanned by ,j|)>+,j|)>> and ,j|)>+,j|)>>. Similarly, since \i>> and since the slope of the edge -1>,j-1>|)>,>,j>|)>|)>> is smaller than the one of ,j|)>,,j|)>|)>>, we obtain <\equation*> j-j>\>-j-1>|i>-i-1>>*-i>|)>\-j|i-i>*-i>|)>, for ,r>. In combination with, this yields <\equation*> j+j-j>-j\+j>|)>-+j>|)>|+i>|)>-+i>|)>>*+i-i>-i|)>, so +i,j+j|)>> is above the line spanned by >,j>|)>+,j|)>> and >,j>|)>+,j|)>>. So far, we have proved that +i,v>|)>+v>|)>|)>> is above >, for all =0,\,r> and =0,\,r>. Since >> and >> are invertible, for in ,\,i>-1>, Lemma yields <\equation*> v>*c>|)>=v>|)>+v>|)>. Now consider the contact polynomial >*c>=e+e*\\\> with ,e\\>, so we have >*c>|)>=v|)>> and |)>\v>*c>|)>-\>. Because the slopes of > are -\>, the point +1,v|)>|)>> is strictly above >. Let us fix \-\> to a value different from the slopes of > and >. Let us assume first that > is less than the smallest slope of >. If > is less than the largest slope of > we let to be the largest integer such that > is less than the slope of ,j|)>,,j|)>|)>>, otherwise we let >. Let > be the corresponding valuation induced in >: |)>=\> for t> and |)>=\>; we write > for the corresponding initial part. We verify that <\eqnarray*> >||>|)>+\*iand>in=>|)>|)>*\>,>>|>||>|)>+\*iand>in=>|)>|)>*\>,>>|>||>|)>+v>|)>+\*+i|)>and>in=in>c>|)>*\+i>.>>>> Consequently, Lemma implies <\equation*> +i,v>|)>+v>|)>|)>=+i,j+j|)> belongs to the Newton polygon of , and +i>|)>=in>*c>|)>>. Assume now that > is greater than the smallest slope of > then we let to be the first integer such that > is greater than the slope of ,j|)>,,j|)>|)>>. Using a similar argument as above, we may prove that\ <\equation> >+i,v>|)>+v>|)>|)>=>+i,j>+j|)> belongs to the Newton polygon of , and that >+i>|)>=in>*c>|)>>. This concludes the proof. <\lemma> Let |)>t>> be an effectively separable, regular, and irreducible contact tower and let <\equation*> a=c*\+c*\+\+c be a contact polynomial with the \\> and truncated modulo >|)>> with \d*\>. Then, the effectively regular Newton polygon of can be computed using <\equation*> >*\|)> operations in >. <\proof> We first compute the initial expansion of >, that contributes to >*log*\|)>|)>> from Proposition. Set in ,l>. In order to compute the valuation of > we run over all its homogeneous components in > in increasing valuation order. Up to precision >, the number of such components is \*r*\*r>. Each such component has s*\*s> terms. Overall the number of zero tests in > is |)>>. From the valuations of the >, the computation of the Newton polygon > does not involve arithmetic operations in>, but *r*\*r|)>|)>> bit operations (with the usual \Pdivide and conquer\Q algorithm). Finally, for a vertex of abscissa of the Newton polygon we need to compute the initial inverse of >. For this purpose we extract in;\|)>/z c>> and appeal to Lemma. Let \> be clustered at |)>t>> given with its effectively regular Newton polygon >. We are to show that each edge of> gives rise to a factor of . <\specified-algorithm> <\description-compact> An effectively separable, regular, and irreducible contact tower |)>t>> along with its initial expansion; a contact polynomial +c*\+\+c\\> given modulo >|)>> with \d*\>> and clustered at >; the effectively regular Newton polygon of (whose slopes are all -d*\>). Let \i\\\i\i=l> be the abscissas of the vertices of the Newton polygon, as in Definition. The normalized initial inverse /z>> of >> is part of the input for ,r>. Contact polynomials ,\,a> modulo >|)>>, clustered at >, such that *\*a+O>|)>>, >*a> admits a single Newton polynomial that coincides with the -th one of , for ,r>. <|specified-algorithm> <\enumerate> If then return . Let |r/2|\>> and set \-\>, where > is the slope of the edge between abscissas > and >. Compute \in/z>;\|)>>, \>|]>>|)>>>, \w>, \\>. Via Corollary called with precision+\>|)>>, compute contact polynomials > and > in > modulo >|)>> such that *+O>|)>>, > is clustered at >, ;\|)>=in;\|)>>, and ;\|)>=in;\|)>>. Recursively call the algorithm with input >: the vertices of the Newton polygon of > are ,j-j|)>,,j-j|)>,\,,0|)>> and the normalized initial inverses are >*w;\|)>,\,in>*w>;\|)>> rescaled by suitable powers of . Recursively call the algorithm with input >: the vertices of the Newton polygon of > are |)>,-i,j|)>,\,-i,j|)>>, with normalized initial inverses >,\,w>>. Return the union of the sets of factors returned by the above recursive calls. <\proposition> Algorithm is correct and takes <\equation*> O|)>*log|)>*log r|)>=|)> operations in >. <\proof> If then the algorithm is clearly correct. From now assume 2>. By definition of the effectively regular Newton polygon, the value of |)>> occurring in step3 writesas <\equation*> in|)>=>;\|]>-i*\>*\>+\+;\|]>>. From *c>/z>|)>=1> and |)>\v+-j|)>*\\v>|)>+\> for i>, Lemma yields <\equation*> v*c|)>=v|)>+v|)>=\-v>|)>+v|)>\\+\. Then Lemma implies *c|)>\v*c|)>-d*\\\>, hence step3 computes an initial Weierstraÿ context for . Let >> and >> be as in Corollary: >*a>>, =a>+O>|)>>, and =a>+O>|)>> hold in step4. From Lemma we know that the Newton polygon of a is the Minkowski sum of those of >> and >> (up to the occasional vertex at infinity of >> and ). Since the vertices of the Newton polygon of have valuation in \> (or infinity), so are those of the polygons of >> and >>. Let > be the first index such that >\0>. From c>\\>, Lemma implies >;\|)>\\+d*\>, whence <\equation> val*c>/z>|)>\v*c>/z>;\|)>\\+d*\-v>;\|)>\\. It follows that the Newton polygon of > coincides with the one of >> for , and that these polygons are effectively regular, with the initial inverses as in steps4 and5. In step3, for ,h-1>, we compute >*w/z>;\|)>> with |)>*log d|)>> operations in > thanks to Proposition. The same cost applies to the computation of >*w;\|)>> in step5. By Corollary, and since \v>|)>+d*\\2*\>, the cost of the lifting in step4 is <\equation*> O|)>*log|)>|)>. The depth of the recursive calls is >, so the complexity bound follows from a standard induction. <\definition> Let |)>t>> be a contact tower, and let a be a contact polynomial clustered at>. The of is made of contact polynomials ,\,a> clustered at > such that *\*a>, the Newton polygon of > admits a single edge for ,r> and the sequence of the slopes of these edges is strictly increasing. <\corollary> Let |)>t>> be an effectively separable, regular, and irreducible contact tower, and let a be a contact polynomial clustered at >. Then, there exists a unique distinct-slope factorization of . <\proof> Since the tower is irreducible, the Newton polygon of can be made effectively regular, thanks to Lemma. Consequently the existence of the distinct-slope factorization of follows from Proposition. Given a distinct-slope factorization ,\,a>, by Lemma the slopes of the > are those of the Newton polygon of . If > is set to the opposite of the slope of > then ;\|)>> is a Newton polynomial of of slope > (up to a power of > and up to a factor in >). The uniqueness of the > thus follows from the uniqueness of the lifting of the distinct slope factors. Consider the factorization of an element \> whose Newton polygon has asingle edge with finite slope. We have already seen that an initial factorization into pairwise coprime factors of |)>>> lifts into a factorization of . We now explain how to obtain this initial factorization. The contact polynomial is assumed to be truncated modulo >|)>> with \d*\>. We assume that the initial expansion of the contact tower has already been computed. We extend the map > (defined in Lemma) as follows: <\eqnarray*> |~>:\|)>,\,\|]>/;\|)>|)>>|>|,y|]>>>|>|>|=\|)>i\t>>|>|>|.>>>> We set > to be the opposite of the unique slope of the Newton polygon of <\equation*> a=\+c*\+\+c. Note that \0>. Let <\equation> |r>\;\|)>*R|l>=R*\ with > prime to \1> and let \l/r>. Note that |)>*R> is an integer. In the next subsection we shall see that the notation is consistent since > will be the \Pnext ramification index\Q. We compute *\*i>\\*i>|)>> with \\>, for ,\-1>, and construct <\equation*> \|)>\x>+\-1>*x-1>+\+\\\|]>, so we have <\equation> |~>|)>|)>=\*\>*\/\>|)>. We factor <\equation*> \=\*\*\, where each > is a power of a monic irreducible factor and the > are pairwise coprime. For ,s>, we let \deg \> and <\equation> a\|~>*\>*\/\>|)>|)>. We compute > using <\equation*> a=\*\>+\-1>*\*-1|)>>|)>*\*-1|)>>+\+\|)>, where > stands for the coefficient of > in >. <\lemma> For ,s>, the polynomial > defined in is homogeneous, monic in >, and of valuation *\/R=\*v/\>. In addition, we have <\equation*> in|)>=in*\*a;\|)>. <\proof> The first assertion is clear by construction. The second assertion follows from the fact that > is a ring isomorphism that preserves the valuation. We next compute the modular inverses <\equation*> \\|\>|)> mod \ for ,s>. Let us write the expansion of > as follows <\equation*> \|)>\\-1>*x-1>+\+\\\|]>\>, let |\>\0> be the smallest integer such that *\+|\>> is a multiple of > and set <\equation*> |\>\*\+|\>|R>. From, we deduce <\equation*> f*\+|\>\v|)>*R+R\+d*\+1|)>*R\+1|)>*R. Recall from Definition that >=\*z>. We further set <\eqnarray*> >|>||\>>*\>*\+|\>>|)>*\*-1|)>>+\>>|||+\|\>>*\*\*-1|)>+|\>>|)>*\>+\|\>>*\*\*\+|\>>|)>>>>> so we have <\eqnarray*> |~>|)>>|||\>>*\>*\+|\>>*y*-1|)>>+\+\|\>>*\*\*\+|\>>>>||||\>>*\*\+|\>>*\>|\>>|)>.>>>> From <\equation*> \|)>*|)>|\|)>>=1 mod \|)> we deduce that <\eqnarray*> |||~>*> rem> a;\|)>|)>>>||||~>|)>*|~>||~>|)>> rem \*\>*\|\>>|)>>>||||\>>*\*\+|\>>*\>|\>>|)>**\>*\|\>>|)>|\*\>*\|\>>|)>> rem \*\>*\|\>>|)>>>||||\>>*\*\+|\>>>>||||\>>*\|\>*R>>>||||\>>,>>>> whence <\equation*> in*> rem> a;\|)>=in|\>>|)>;\|)>=z|\>>. After a division by a suitable power of , we deduce the normalized initial inverse of > modulo > for ,s>. The following algorithm makes use of the separable factorization of univariate polynomials: see. In the case of characteristic zero or sufficiently large, that holds in the present paper, the separable factorization coincides with the squarefree factorization. <\specified-algorithm> <\description-compact> An effectively separable, regular, and irreducible contact tower |)>t>> along with its initial expansion; a contact polynomial +c*\+\+c\\> modulo >|)>> clustered at |)>t>>, with \d*\>>; the Newton polygon of , with a single edge of finite slope>. A factorization of into clustered polynomials > at |)>t>> modulo >|)>>, each> has a single edge of slope > in its Newton polygon and the associated Newton polygon is the initial power of an irreducible polynomial. The characteristic of > is zero or l>. <|specified-algorithm> <\enumerate> Compute |~>> and \\|]>> such that |~>=\*\>*\/\*\>|)>>. Factor =\*\*\>, where ,\,\> are pairwise coprime powers of irreducible factors of >: this can be done by computing the separable factorization of > and then the irreducible factors of the separable ones. For ,s> compute \|\>|)> mod \>. For ,s> compute > as defined in. For ,s> compute > as defined in, and set \|v|)>+l*\|\>=|v|\>>. Lift the initial factorization of |)>=in*\*a;\|)>> into *\*> to precision>|)>> by using Corollary at precision +|v|\>>|)>>. Return ,\,> modulo >|)>>. <\proposition> Assume that>> holds. Algorithm is correct and takes <\equation*> >*\|)>+|\>>|~>*d|)> operations in >, where |~>> is the degree of the separable part of >. <\proof> From the above discussion the required initial Hensel context is known when entering step6, so lifting is possible thanks to Corollary. Using Lemma we verify that <\eqnarray*> |]> a|)>>|>||]> a;\|)>>>||||)>-v;\|)>>>||>|+d*\-\>>||>|.>>>> It follows that the Newton polygon of > modulo >|)>> has a single edge of slope >. We are done with the correctness of the algorithm. Let >*\\|\>>. Steps1, 4, and5 take <\equation*> *\*s|)>>*log|)>*t|)>=>*log \|)> by Proposition. For the factorization of > in step 2, as indicated we first compute the separable factorization =|~>*|~>*\*|~>> using *d>|)>> operations in > by, and then factor |~>,\,|~>>> (which are pairwise coprime). Consequently the cost of factoring over>is <\equation*> >|~>|)>+\+>|~>|)>\|\>>|~>*d|)>. Step3 contributes to <\equation*> O*\*s|)>>*|)>*log \|)> operations in >: this includes the computation of |\>> via10, Theorem10.10>, the remainders by the > via10, Theorem10.6>, and \>> modular inversions. Finally, the cost of step6 follows from Corollary and ,s>|)>\\>>. <\definition> Let |)>t>> be an effectively separable, regular, and irreducible contact tower, and let a be a contact polynomial clustered at> having a single edge in its Newton polygon. The of is made of contact polynomials ,\,a> clustered at > such that *\*a>, the Newton polygon of > admits a single edge of the same slope as and its Newton polynomial is the initial of a power of an irreducible homogeneous polynomial for ,r>. These irreducible homogeneous polynomials are pairwise distinct.\ <\corollary> Let |)>t>> be an effectively separable, regular, and irreducible contact tower, and let a be a contact polynomial clustered at > having a single edge in its Newton polygon. Then, there exists a unique equal-slope factorization of , up to a permutation of the factors. <\proof> The existence follows from Proposition. As for the uniqueness, assume that ,\,a> is an equal-slope factorization of . In the same way as we constructed > from in equation, we define the polynomial \\|]>> of degree > by <\equation*> |~>;\|)>|)>=\*\>*\/\>|)>, for ,r>. The > are powers of pairwise distinct irreducible polynomials, so they coincide with those computed in Algorithm. After distinct-slope and equal-slope factorizations, we have reduced the general situation to the case where the Newton polygon of has a single edge and the associated Newton polynomial is an initial power of an irreducible homogeneous polynomial. This allows us to increment the underlying contact tower with a new contact coordinate at level and then to pursue the factorization of with respect to the extended tower. In order to ensure that the extended contact tower is separable, we assume from now on that the characteristic of > is zero or sufficientlylarge. <\specified-algorithm> <\description-compact> An effectively separable, regular, and irreducible contact tower |)>t>> along with its initial expansion; a contact polynomial +c*\+\+c> clustered at > modulo >|)>> with \d*\>>, whose Newton polygon has a single edge of finite slope>, and such that the associated Newton polynomial is the initial power of an irreducible homogeneous polynomial. An extended tower |)>t+1>> modulo >|)>>, still effectively separable, regular, and irreducible, and such that is clustered at it of degree > in >. The characteristic of > is zero or l>. <|specified-algorithm> <\enumerate> Compute |~>> into the form *\>*\/\>|)>>, with \\|]>>. Compute the separable factorization =\>>, where > is irreducible and separable, according to the assumptions. Set \deg \=\/m>, \r*s> as above, and compute <\equation*> \\|~>*s>*\/\>|)>|)>. Extend the contact tower with > and extend the initial expansion accordingly. Make level of the tower effectively separable by computing the inverse of \|\ \>> modulo >. <\proposition> Algorithm is correct and takes <\equation*> >*\|)> operations in >. <\proof> By construction, > is homogeneous of valuation *s*R> in ,\,\|]>>, and |)>t+1>> satisfies all the requirements of Definition. The incremented tower remains effectively regular, since the known initial inverse of > straightforwardly yields an initial inverse of ,\,\,0|)>>. We extend the initial expansion at level accordingly. The initial inverse in step5 does exist because > is separable. Steps1 and3 contribute to\ <\equation*> **\*s|)>>*log|)>*t|)>=>*log \|)> by Proposition. Step2 takes |)>*log \|)>> operations in > by. The cost of step5 is >*log|)>|)>=>*log \|)>> by Lemma. Finally, is initially equal to >> whenever \d*\>, which means that is clustered at >. In principle, Algorithm might introduce a new contact coordinate > of degree one in >. For complexity reasons it is better to avoid this from happening. As outlined in the introductory sections and, we now work out the central shift algorithm. Let |)>t>> be an effectively separable, regular, and irreducible contact tower. Let *\+c*\+\+c> be clustered at >. An of is an element \> such that <\equation*> *f+c*f+\+c|]>|)>>=0. If *\+c*\+\+c> is a Newton polynomial of , then an of is an initial root of regarded with > set to the opposite of the slope of . One key idea behind the central shift algorithm is the following lemma, that will be used in a \Pdivide and conquer\Q fashion in the subsequent algorithm. <\lemma> Let be a contact polynomial clustered at >, and let be a non-zero initial root of |)>> of multiplicity 1>. If the characteristic of > is zero or l>, then is an initial root of a|\ \>> of multiplicity , for ,l>. <\proof> Set \v|)>>. Lemma implies <\equation> in a|\ \>;\|)>=in \|\ \>|)>* a|\ \>;\|)>. Since the tower is separable, we know from Lemma that \|\ \>> is initially invertible, hence is an initial root of a|\ \>;\|)>> of multiplicity . <\specified-algorithm> <\description-compact> Input>An effectively separable, regular, and irreducible tower |)>t>>; a contact polynomial \> clustered at > and of degree 1> in > modulo>|)>>, with \d*\>; we assume that |)>=in-f|)>;\|)>>, where is initially invertible in>. An effectively separable, regular, and irreducible tower |\>|)>t>> such that |\>=\> for ,t-1>, and the non-zero initial roots of the Newton polynomials of have multiplicityl/2>. <|specified-algorithm> <\enumerate> If then replace > by -f> and return |)>t>>. Let |l/2|\>> and compute the Weierstraÿ normalization of a|\ \>> modulo >|)>> via Corollary. The initial context is made of <\equation*> a\in-f|)>;\|)>,a\in!>* \|\ \>|)>;\|)>, and the normalized initial inverse /z>> of > in >. Call the algorithm recursively with input |)>t>> and modulo>|)>>. Let |~>|)>t>> be the tower obtained in return. Compute the effectively regular Newton polygon of in |~>> modulo>|)>> via Lemma. Compute the distinct-slope factorization of in |~>> modulo >|)>> with Algorithm. If all the non-zero initial roots of the Newton polynomials of have multiplicityl/2>>, then return |~>|)>t>> modulo>|)>>. Otherwise, compute the factor > modulo>|)>> of of degree > in > whose initial is the >-th power of a linear factor |~>-> with \l/2>, > non-zero, and where |~>> is set to ;\|)>>. Let \-> and compute the Weierstraÿ normalization > of > |\ |~>>>> modulo>|)>> via Corollary. The initial context is made of <\equation*> \in|~>-|)>->;|~>|)>,\in!|-|)>!>* |~>|\ \>|)>>;\|)>, and the normalized initial inverse /z|~>>> of > in >. Call the algorithm recursively with input |~>|)>t>> and > modulo>|)>>. Return the tower |\>|)>t>> obtained in the output. <\proposition> Algorithm is correct and takes <\equation*> >*\|)> operations in>. <\proof> If the algorithm exits at step1, then > when regarded in the returned tower. Since |)>\v;\|)>> the initial form of the returned > is the same as the initial form of the input value of >, hence the returned tower is effectively separable, regular, and irreducible. The Newton polynomial of cannot have non-zero initial roots with respect to the returned contact tower, so the output is correct. The initial Weierstraÿ context in step2 follows from equation. If the algorithm exits at step6, then the output is clearly correct. Let us now examine the situation when the algorithm does not exit at step6. In step7, Lemma ensures that > is a non-zero initial root of a Newton polynomial of a|\ \>> of multiplicity -h>, regarded in |~>>. Since |^>\\>, > is a non-zero initial root of a Newton polynomial of of multiplicity -h>. As a non-zero initial root of a Newton polynomial of modulo >|)>> we necessarily have >*a|)>\\>, hence <\equation*> v>*a;\|)>\\+d*\ by Lemma. From Lemma, we deduce that <\equation*> v>;\|)>\\+d*\-v|)>\\, and consequently that <\equation*> val-h>|)>\v-h>;\|)>\\. It follows that > is a non-zero initial root of a Newton polynomial of of multiplicity -h> modulo >|)>>, hence that -h\/2>. Consequently, <\equation> \/2. We verify that =-\l/2-=h-l/2\-1>, so \0>. In step8, the contact polynomial> has degree -=l-h> in |~>>. By Lemma, inequality, and by following the same reasoning as for , a non-zero initial root of a Newton polynomial of > in |\>> has multiplicity <\equation*> \-|)>/2+=+|)>/2=-/2\/2-/2=h\l/2. Let us now examine the Newton polynomials of in |~>>. For this purpose, by means of Corollaries and, we may decompose into <\equation*> a=a*a**a, where> has Newton polynomials with slopes -|~>>, where > has Newton polynomials with slope-|~>>, and where > has a single Newton polynomial of slope |~>> but that does not admit > for initial root. The initial of \|\>-\> is >, so its valuation is |~>>. Therefore the Newton polygon of > in |\>> has a single edge of slope |~>>. We also verify that the Newton polygon of > in |\>> admits a single edge of slope |~>>. Then, the Newton polygon of > in |\>> is the same as in |~>>. Finally the Newton polygon of > in |\>> has slopes -|~>>. Consequently the non-zero initial roots of the Newton polynomials of in |\>> cannot have multiplicitiesl/2>. We are done with the proof of the correctness. From Lemma we have <\equation*> in \|\ \>|)>=in \|\ \>*\* \|\ \>|)>. Therefore, by using Proposition, the initial inverse of \|\ \>> can be obtained with |)>> operations in > from the precomputations attached to |)>t>>. The needed initial Weierstraÿ contexts in steps2 and8 can be obtained with |)>> operations in > thanks to Proposition again. The corresponding Weierstraÿ normalizations take further |)>> operations in > by Corollary. Let > represent the cost of the algorithm with input of degree . In step1, the cost is =O|)>>. In step4 the effectively regular Newton polygon can be determined with cost >*\|)>> by Lemma. Step5 amounts to |)>> by using distinct-slope factorization and Proposition. In step6, we appeal to the equalslope factorization but discarding the irreducible factorizations: in fact, having a root of multiplicity l/2> is equivalent to having a separable factor of multiplicity l/2>, that can thus be read off from the separable factorization. So Proposition provides us with a cost >*\|)>> for steps6 and7. Consequently the cost >> of the algorithm in degree in > satisfies <\equation*> >=>+>+>*\|)>. We conclude by a standard induction. We are now in a position to present our top level algorithm for contact factorization. The distinct-slope and equal-slope factorizations are intertwined in order to increase the current contact tower and split the input polynomials. The process finishes once the polynomial to be factored is a power of the top level contact coordinate, up to the input precision. The central shift algorithm ensures that the \Pdivide and conquer\Q approach only incurs a logarithmic complexity overhead. The main step of the contact factorization is summarized in the following algorithm. <\specified-algorithm> <\description-compact> Input>|)>t>> effectively separable, regular, and irreducible; a contact polynomial +c*\+\+c\\> modulo >|)>> clustered at >, with \d*\>. A set > of contact factors >,>|)>t>|)>> with precision >|)>> for ,n> such that: <\enumerate-alpha> >|)>t-1>=|)>t-1>>, for ,n>; >*\*a>+O>|)>>; >> is clustered at >>, for ,n>; The Newton polygon of >> with respect to >|)>t>> has a single edge whose Newton polynomial is an initial power of an homogeneous polynomial of degree> in >; If the Newton polygon of >> has a non-zero initial root, then its multiplicity is max>. The characteristic of > is zero or l>. <|specified-algorithm> <\enumerate> Initialize > with the empty set. Compute the effectively regular Newton polygon of modulo >|)>> via Lemma, and then the distinct-slope factorization of modulo >|)>> by using Algorithm. Let > be the set of factors obtained in return. For each in >, compute the equalslope factorization of over |)>t>> by using Algorithm. Let > be the set of all resulting factors along with their multiplicities. For each in > of multiplicity written : <\enumerate> If l/2>, then insert |)>t>|)>> in >. If l/2> (so is an initial power of a polynomial of degree one in >), then call Algorithm and append the resulting factorization to >. Return >. <\proposition> Assume that>> holds. Algorithm is correct and takes at most <\equation*> >*\|)>+|\>>+\+\|)>*d|)> operations in >. <\proof> Properties(a) to(e) are satisfied by construction. Step2 takes >*\|)>> by Lemma and Proposition. Step3 totalizes >*\|)>+|\>>+\+\|)>*d|)>> by Proposition. Step4 contributes to >*\|)>> by Proposition. Our top level algorithm finally makes a repeated use of Algorithm. <\specified-algorithm> <\description-compact> Input>|)>t>> effectively separable, regular, and irreducible; \> clustered at > modulo >|)>>, of degree in >, with \d*\>. An irreducible contact factorization of modulo >|)>>. The characteristic of > is zero or l>. <|specified-algorithm> <\enumerate> Initialize > and > with the empty set. Call Algorithm and let >,>|)>t>|)>> denote the returned contact factors for ,n>. For ,n>: <\itemize> If >> is a power of >> then insert >,>|)>t>|)>> into >. Otherwise, call Algorithm with >> and >|)>t>> and let >|)>t+1>> be the returned tower. If >> equals >> then insert >,>|)>t+1>|)>> into>. If >> has degree in > and writes >=\-f>, then replace >> by >-f> and insert the pair >,>|)>t>|)>> into>. Otherwise insert the pair >,>|)>t+1>|)>> into>. Call the algorithm recursively for each element of>. Include the returned factors into >. Return >. <\proposition> Assume that>> holds. Algorithm is correct and takes at most <\equation*> >*\|)>+2*|\>> operations in >. <\proof> On the one hand, if the initial of >> is a power of a degree one polynomial, then according to the specification of Algorithm we have <\equation*> deg> a>\max. On the other hand, if >> is an initial power of a polynomial >> of degree 2>, then <\equation*> deg> a>=> a>|deg> \>>\l/2. Consequently the depth of the recursive calls is >. Let us analyze the valuation of >;\|)>>. If >> comes from a proper distinct-slope factor or a proper equal-slope factor of then inequalities and ensure that <\equation*> d*\=v>;\|)>\\. Otherwise has a single slope and its initial is separable, so , >=a> and this case does not yield a recursive call. We conclude that the algorithm behaves as specified. Discarding factorization costs, step2 takes >*\|)>> operations in >, by Proposition. In step3, by Proposition, for each ,n> the initial expansion of >|)>t>>> takes >|)>>|)>>, where >> represents the degree of >|)>t>>>. By Proposition, the cost of Algorithm is >*>|)>>*\|)>>, where >> denotes the degree of >> in its main variable >+1>>>. The total cost of steps3 is <\equation*> l>*>|)>>*\|)>=>*\|)>. Let >,>|)>t>>|)>> for ,m> denote the elements of > when entering step4. By construction we have <\equation*> deg>+1>> b>*deg \>>>\l*d. If > represents the cost function of the algorithm (still discarding factorizations), we have shown that <\equation*> =>*\|)>+j\m>>+1>> b>,deg \>>>|)>, and that =>*\|)>>. Unrolling the recursion > times leads to <\equation*> =>*\*log l|)>=>*\|)>. Let us now turn to the cumulated cost >> of factoring separable polynomials over algebraic extensions of > during the execution of Algorithm. Let us show by induction on and 2> that <\equation> >\|\>>+|\>>*d|)>. This is easy if , so assume that 2>. We recall that <\equation*> |\>>|)>+\+|\>>|)>\|\>>+\+l|)> holds for any positive integers ,\,l>. Assume first that has a non-trivial distinct-slope factorization *\*a> during Algorithm and let ,\,l> be the degrees of ,\,a> in >. Then the induction hypothesis implies <\eqnarray*> >>|>|>,d|)>+\+>,d|)>>>||>||\>>*d|)>+|\>>-2|)>|)>+\+|\>>|)>+|\>>-2|)>|)>>>||>||\>>*d+\+l*d|)>+|\>>-2+\+l-2|)>*d|)>>>||||\>>+|\>>>>||>||\>>+|\>>.>>>> Assume next that the Newton polygon of has a unique slope and that the associated Newton polynomial is the -th power of an irreducible polynomial of degree 2>, for some 2>. Then the induction hypothesis yields <\eqnarray*> >>||>>>||>||\>>+|\>>*d|)>>>||>||\>>+|\>>*d|)>.>>>> Assume finally that the Newton polygon of has a unique slope and that the associated Newton polynomial > has at least two distinct prime factors. Consider the separable factorization <\equation*> \=\*\*\*\ and let ,\,l> be the degrees of ,\,\> in >. Note that +\+l\2> and <\equation*> >\j\k>|\>>*d|)>+j\k>>*d,j|)>. Applying the induction hypothesis, this again yields <\eqnarray*> >>|>|j\k>|\>>*d|)>+j\k>|\>>*j*d|)>+|\>>**d|)>|)>>>||>||\>>j\k>l*j*d|)>+|\>>j\k>*d+l**d|)>|)>>>||||\>>+|\>>j\k>*j-l|)>*d|)>>>||||\>>+|\>>j\k>l|)>*d|)>>>||>||\>>+|\>>*d|)>.>>>> We conclude by induction that() indeed holds. <\render-proof|Proof of Theorem> Theorem is a consequence of Proposition by applying Algorithm with input and the trivial contact tower of height zero. We explain how Abhyankar's approximate roots theory could improve our contact factorization algorithm in some cases. If \> is a monic polynomial of degree and if is a divisor of that is invertible in >, then there exists a unique polynomial of degree such that <\equation> deg|)>\*=l-. This polynomial is called the -th approximate root of . In particular, is monic and the -adic expansion of is of the form <\equation*> f=g+f*g+\+f, where \\l/m>>. Let \x*f>, that is the of , and \x*g>. Condition is equivalent to <\equation*> =+O+1>|)>, which means that is uniquely determined by \|]>>, whenever > is a perfect field. The computation of the -th approximate root of > can be done using the Newton operator if is not in >: we define the sequence|)>0>> <\equation*> h\=1,h\h+h*f*|)>/m+O>|)>. A standard computation shows that this sequence converges quadratically to >. The computation of > by this method takes *log m|)>> operations in >. Let us now extend this construction to contact coordinates. <\lemma> Let \> be monic of degree in >, and let be a divisor of that is invertible in>. Then, there exists a unique \> monic of degree in > such that <\equation*> deg>|)>\l-l/m. <\proof> The condition rewrites <\equation*> deg-\|)>\d*, and we have |)>=d*l>, |)>=d*l/m>. Therefore > is uniquely determined as the -th approximate root of >. In the context of Lemma, the -adic expansion of has the form <\equation*> a=b+a*b+\+a. The algorithmic purpose of approximate roots is as follows. Suppose that <\equation*> in=in|)> for some \> monic in >. We can add one level to > with <\equation*> \\b\\v/deg> b. We write > for the image of in > and examine the Newton polygon of >. If we had <\equation*> in|)>=in+c|)>|)>, with some \>, this would mean that <\equation*> |]>+\>=|]>+\>=+\>, for some sufficiently small positive value of >. In particular, the -adic expansion of would be <\equation*> +\>=*c*b|]>+\> whence <\equation*> *v+v+\>=+m*c*b|]>*v+v+\>. The latter equality is not possible since it contradicts the fact that is an approximate root of . Consequently, the Newton polygon of > cannot have a single edge with a Newton polynomial of the form +c|)>|)>>. Either it has at least two edges, or a single edge but the initial factors of the Newton polynomial have multiplicity m>. For the situations similar to the one of section these computations are expected to be faster and easier than the central shift method. In this section we consider a monic and separable polynomial \|]>>. We are interested in computing the irreducible factorization of modulo >|)>> for some requested precision>. Our strategy naturally relies on computing a contact factorization of for a sufficiently large precision. We begin with analyzing the precision loss induced by the distinct slope and equal-slope factorizations. Let \|]>> be monic and separable, and let |)>t>> be a contact tower. Let |)>>|\> denote an algebraic closure of |)>>, we still write > for the extended valuation. <\lemma> Assume that > is clustered at >. If \|)>|\>> is a root of , then <\equation*> val|)>|)>\\, for ,t>. In addition, for all \|]>> we have <\equation*> val|)>|)>\v;\|)>. <\proof> From Lemma we know that > is clustered at >, hence <\equation*> v;\|)>=d*\*d*m*\, where \deg>|)>>. Since |)>=0>, necessarily |)>|)>\\> holds. Assume that the lemma holds up to some index ,t-1|}>>. From Lemma, the contact polynomial > is clustered at >. Let us canonically write <\equation*> \=\>+c-1>*\-1>+\+c, where \d*\*d*m> and \\>. By induction we have <\equation*> val|)>|)>|)>\v;\|)>\-j|)>*\, for ,l-1>. Since <\equation*> A|)>=\|)>>+\-1>|)>|)>*\|)>-1>+\+\|)>|)>=0, necessarily |)>|)>\\> holds. Let \|]>> be canonically written <\equation*> \=c*\+c*\+\+c, with \\>. Thanks to the induction hypothesis, we verify that <\eqnarray*> |)>|)>>|||)>|)>*\|)>+\|)>|)>*\|)>+\+\|)>|)>|)>>>||>|;\|)>+n*\,v;\|)>+*\,\,v;\|)>|)>>>|||;\|)>.>>>> Finally the lemma holds for index . If |)>t>> is a separable, regular, and irreducible contact tower, then Lemmas and imply that is a valuation of |)>> that extends >. <\proposition> Let |)>t>> be a separable, regular, and irreducible contact tower and let \|)>>. Then is the unique valuation of |)>/> that extends > and we have <\equation*> v=|)>|deg F>, for all in |)>/>. <\proof> Proposition ensures that is irreducible. By setting > to infinity we obtain that is a valuation of /|)>>. The uniqueness and the resultant-based expression are well known; for instance, seeXII, Corollary6.2>. Let be monic in |]>> and clustered at an effectively separable, regular, and irreducible contact tower |)>t>>. We assume that > is larger than or equal to the smallest slope of the Newton polygon of . As before, stands for the image > of in>, whose degree in > is written. <\lemma> With the above notation, the following inequality holds: <\equation*> val A|)>\l*d* \|\ x>|)>+v-\|)>. <\proof> Poisson's formula for resultants yields <\equation*> Res, A|\ x>|)>=|)>=0> A|\ x>|)>. Thanks to Lemma, we deduce: <\eqnarray*> ||, A|\ x>|)>|)>>>||>||)>=0> \|\ x>* a|\ \>|)>|)>,\,\|)>|)>|)>>>||>||)>=0> \|\ x>|)>+v a|\ \>|)>|)>)>>>||>||)>=0> \|\ x>|)>+v-\|)>>>||>| \|\ x>|)>+v-\|)>.>>>> Next, we consider > and > monic in |]>>. Let > and > stand for the canonical representatives of > and > in >, of respective degrees > and > in>. In the sequel, we define |]> a> to be the constant coefficient of>, when regarded as a univariate polynomial in >. <\lemma> With the above notation, if the slopes of the Newton polygon of > are -\> and the slopes of the Newton polygon of > are -\>, then we have <\equation*> val,A|)>|)>\l*d*v|]> a|)>. <\proof> Again, we use Poisson's formula for the resultants: <\equation*> Res,A|)>= A*deg A>*|)>=0>A|)>. It follows that <\equation*> Res,A|)>= A*deg A>*|)>=0>a|)>,\,\|)>|)>. Let ,\,A> be the distinct-slope factors of > (as in Definition) and let ,\,a> stand for their image in >. We verify that: <\eqnarray*> ,A|)>|)>>|||)>=0>a|)>,\,\|)>|)>|)>>>||>||)>=0>val|)>,\,\|)>|)>|)>>>||||)>=0>val|)>,\,\|)>|)>|)>>>||>||)>=0>val|)>>|)>>>||>|*|)>=0>val|)>|)>.>>>> By Lemma, if > is a root of > then |)>|)>> is larger or equal to the opposite of the slope of the single edge of the Newton polygon of >, that is <\equation*> val|)>|)>\|]> a|)>|deg> a>. It follows that <\eqnarray*> ,A|)>|)>>|>|*deg A*|]> a|)>|deg> a>>>|||*d*v|]> a|)>>>|||*d*v|]> a|)>.)>>>>> In the rest of the section, we study the precision loss encountered in each Newton factorization. For a partial factorization *A> with monic > and >, the following well known formula will be used several times: <\equation> Disc*A|)>=Disc|)>*Disc|)>*Res,A|)>. In the sequel > represents the precision at which the irreducible factors of the input polynomial are required. Let in > be given modulo >|)>> with <\equation*> \\val|)>+\, where \>. We assume that the Newton polygon of has been computed. Following Definition, we let > stand for the product of factors of with slopes -\> and let > stand for the product of factors of with slopes -\>, hence *a>. Let \deg> a\1> and \deg> a\1>, let /z>> represent the normalized initial inverse of >. \ According to Corollary, we may obtain > with precision >|)>>, where <\equation*> \\\-\=\-|v|)>+d*\|\>. Setting \\|)>> for , equation and Lemma imply <\eqnarray*> A|)>>||*A|)>|)>-val A|)>-2*val,A|)>|)>>>||>|*A|)>|)>-2*val,A|)>|)>>>||>|-\-2*d*l*v|)>>>|||+|v|)>+d*\|\>-\-2*d*l*v|)>>>||>|-\+|)>+d*\-2*l*v|)>|)>.>>>> Since \1> we have |)>=v|]> a|)>\d*\>, that yields\ <\equation*> \\val|)>|)>+\. We also compute > with precision >|)>>, where \\>, and the same calculation yields <\equation*> \\val|)>|)>+\. <\lemma> With the above notation, let \> be given with precision >|)>> such that <\equation*> \\val|)>|)>+\. Then, Algorithm computes truncations of the distinct slope factors ,\,a> of modulo some >|)>> such that <\equation*> \\\\val|)>|)>|)>+\, for ,r>. <\proof> We apply the above precision analysis in the \Pdivide and conquer\Q fashion used in Algorithm. Now we examine the precision loss during the equal-slope factorization. The input is a polynomial clustered at > and which has a single slope > and known with precision >|)>> such that <\equation*> \\val A|)>+\. Let ,\,a> represent the equal slope factors of as in Definition, and set \deg> a>. By Corollary the contact polynomial > can be computed with relative precision>|)>> where <\equation*> \\\-\and>\\|v-v|)>+l*\|\>=|v|\> for ,r>. Setting \> and \\|)>> for ,r>, Lemma implies that <\eqnarray*> ,A|)>|)>>|>||)>*d*v|)>>>||||)>*d*l*\.>>>> Since <\equation*> 2*|)>*l-l=|)>*l-|)>|)>+|)>*l-l|)>=|)>-1|)>+l*+1|)>|)>\0 and \v>, we obtain that <\equation*> \\val A|)>+\, for ,r>. <\lemma> With the above notation, let \> be given with precision <\equation*> \\val|)>+\. Then Algorithm computes the equal-slope factors ,\,a> modulo >|)>> such that <\equation*> \\val|)>|)>+\. <\proof> In fact Algorithm computes the equal-slope factors of with a precision higher than the one requested here, but the above discussion leads to the lower bounds. We are now ready to prove Theorem. We assume that \|]>> is monic and separable of degree in and known modulo >|)>> where \val P|)>+\>. We combine Theorem with the above precision analyses.\ <\render-proof|Proof of Theorem> We apply Algorithm with entry \|]>> modulo >|)>>, and with the trivial contact tower of height zero. The above precision analyses for the intermediate steps of the contact factorization algorithm, namely Lemmas and, show by induction that all intermediate factors of occurring in the top level algorithm are computed along with a contact tower |)>t>> of degree with precision >|)>> such that <\equation*> \\val A|)>+\. Such a factor is proved to be irreducible when it has degree one in >. In this case, by inequality(), the coefficients of are uniquely determined up to precision in at least <\equation*> val A|)>+\--1|)>*\-\--1|)>*\, which equals <\equation*> val A|)>+\-v \|\ x>|)>, by Lemma. On the other hand, Lemma yields <\equation*> val A|)>\v \|\ x>|)>, so the precision of is at least >|)>> as claimed. Note that the central shift algorithm does not produce factors, so it does not involve any loss of precision. The contact factorization presented in this paper is subject to further improvements. Afirst research direction concerns the design of a contact factorization algorithm that would not rely on univariate irreducible factorization, by using the paradigm of instead; so the computed contact towers would not be necessarily irreducible any longer. Another research direction concerns the design of fast algorithms for the contact coordinates in the vein of: we could avoid the conversions to plain coordinates and their precision loss. Another research direction concerns fields of small positive characteristic 0>. <\bibliography|bib|tm-plain|> <\bib-list|86> S.S.Abhyankar. Irreducibility criterion for germs of analytic functions of two complex variables. , 74(2):190\U257, 1989. S.S.AbhyankarT.Moh. Newton\UPuiseux expansion and generalized Tschirnhausen transformation. I. Reine Angew. Math.>, 260:47\U83, 1973. S.S.AbhyankarT.Moh. Newton\UPuiseux expansion and generalized Tschrinhausen transformation. II. Reine Angew. Math.>, 261:29\U54, 1973. M.E.Alonso, F.J.Castro-JiménezH.Hauser. Encoding algebraic power series. , 18(3):789\U833, 2018. M.Aschenbrenner, L.vanden DriesJ.vander Hoeven. . 195Annals of Mathematics studies. Princeton University Press, 2017. J.-D.Bauch, E.NartH.D.Stainsby. Complexity of OM factorizations of polynomials over local fields. Comput. Math.>, 16:139\U171, 2013. A.Bostan, G.ChristolPh.Dumas. Fast computation of the Nth term of an algebraic series over a finite prime field. M.Rosenkranz, , ISSAC '16, 119\U126. New York, NY, USA, 2016. ACM. A.Bostan, F.Chyzak, G.Lecerf, B.SalvyÉ.Schost. Differential equations for algebraic functions. C.W.Brown, , ISSAC '07. New York, NY, USA, 2007. ACM. A.CampilloJ.I.Farrán. Symbolic Hamburger\UNoether expressions of plane curves and applications to AG codes. , 71(240):1759\U1780, 2002. D.G.CantorD.M.Gordon. Factoring polynomials over -adic fields. W.Bosma, , 1838, 185\U208. Springer-Verlag, 2000. D.G.CantorE.Kaltofen. On fast multiplication of polynomials over arbitrary algebras. , 28:693\U701, 1991. D.G.CantorH.Zassenhaus. A new algorithm for factoring polynomials over finite fields. , 36(154):587\U592, 1981. A.L.Chistov. Polynomial complexity of the Newton\UPuiseux algorithm. , 233, 247\U255. Springer-Verlag, 1986. A.L.Chistov. Efficient factoring polynomials over local fields and its applications. , 1, 1509\U1519. Springer-Verlag, 1991. D.V.ChudnovskyG.V.Chudnovsky. On expansion of algebraic functions in power and Puiseux series, I. Complexity>, 2(4):271\U294, 1986. D.V.ChudnovskyG.V.Chudnovsky. On expansion of algebraic functions in power and Puiseux series, II. Complexity>, 3(1):1\U25, 1987. H.Cohen. . Graduate Texts in Mathematics. Springer, Berlin, Heidelberg, 1993. V.CossartG.Moreno-Socías. Racines approchées, suites génératrices, suffisance des jets. > série>, 14(3):353\U394, 2005. D.Duval. Rational Puiseux expansions. , 70(2):119\U154, 1989. J.Fernández, J.Guàrdia, J.MontesE.Nart. Residual ideals of MacLane valuations. Algebra>, 427:30\U75, 2015. D.FordP.Letard. Implementing the Round Four maximal order algorithm. , 6(1):39\U80, 1994. D.Ford, S.PauliX.-F.Roblot. A fast algorithm for polynomial factorization over >. , 14(1):151\U169, 2002. D.FordO.Veres. On the complexity of the Montes ideal factorization algorithm. G.Hanrot, F.MorainE.Thomé, , 6197, 174\U185. Springer-Verlag, 2010. A.FröhlichJ.C.Shepherdson. On the factorisation of polynomials in a finite number of steps. Z.>, 62:331\U334, 1955. A.FröhlichJ.C.Shepherdson. Effective procedures in field theory. , 248:407\U432, 1956. J.vonzur GathenJ.Gerhard. . Cambridge University Press, New York, 3rd, 2013. J.vonzur GathenV.Shoup. Computing Frobenius maps and factoring polynomials. , 2(3):187\U224, 1992. G.-M.GreuelG.Pfister. . Springer-Verlag Berlin Heidelberg, 2002. J.Guàrdia, J.MontesE.Nart. Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields. , 23(3):667\U696, 2011. J.Guàrdia, J.MontesE.Nart. Newton polygons of higher order in algebraic number theory. , 364(1):361\U416, 2012. J.Guàrdia, J.MontesE.Nart. A new computational approach to ideal theory in number fields. , 13(5):729\U762, 2013. J.Guàrdia, J.MontesE.Nart. Higher Newton polygons and integral bases. Number Theory>, 147:549\U589, 2015. J.Guàrdia, E.NartS.Pauli. Single-factor lifting and factorization of polynomials over local fields. Symbolic Comput.>, 47(11):1318\U1346, 2012. D.HarveyJ.vander Hoeven. Polynomial multiplication over finite fields in time >. ACM>, 69(2):1\U40, 2022. Article No.:12. J.P.G.HenryM.Merle. Complexity of computation of embedded resolution of algebraic curves. J.H.Davenport, , 378, 381\U390. Springer Berlin Heidelberg, 1989. H.Hironaka. Resolution of singularities of an algebraic variety over a field of characteristic zero. , 79:109\U326, 1964. J.vander Hoeven. . , École polytechnique, Palaiseau, France, 1997. J.vander Hoeven. Relax, but don't be too lazy. Symbolic Comput.>, 34:479\U542, 2002. J.vander Hoeven. Newton's method and FFT trading. , 45(8):857\U878, 2010. J.vander Hoeven. Faster Chinese remaindering. , HAL, 2016. . J.vander Hoeven. Computing with D-algebraic power series. , 30(1):17\U49, 2019. J.vander Hoeven. Effective power series computations. , 19(3):623\U651, 2019. J.vander Hoeven. . Scypress, 2020. J.vander HoevenG.Lecerf. Modular composition via factorization. Complexity>, 48:36\U68, 2018. J.vander HoevenG.Lecerf. Accelerated tower arithmetic. Complexity>, 55:101402, 2019. J.vander HoevenG.Lecerf. Directed evaluation. Complexity>, 60:101498, 2020. J.vander HoevenG.Lecerf. Univariate polynomial factorization over finite fields with large extension degree. , 2022. . E.KaltofenV.Shoup. Fast polynomial factorization over high algebraic extensions of finite fields. , ISSAC '97, 184\U188. New York, NY, USA, 1997. ACM. E.KaltofenV.Shoup. Subquadratic-time factoring of polynomials over finite fields. , 67(223):1179\U1197, 1998. K.S.Kedlaya. On the algebraicity of generalized power series. , 58:499\U527, 2017. K.S.KedlayaC.Umans. Fast polynomial factorization and modular composition. Comput.>, 40(6):1767\U1802, 2011. H.T.KungJ.F.Traub. All algebraic functions can be computed fast. ACM>, 25(2):245\U260, 1979. S.Lang. , 211. Springer-Verlag, New York, 3rd, 2002. G.Lecerf. Fast separable factorization and applications. , 19(2):135\U160, 2008. S.MacLane. A construction for absolute values in polynomial rings. , 40(3):363\U395, 1936. S.MacLane. A construction for prime ideals as absolute values of an algebraic field. , 2(3):492\U510, 1936. J.Montes. . , Universitat de Barcelona, Spain, 1999. F.Mora. An algorithm to compute the equations of tangent cones. J.Calmet, , 144, 158\U165. Springer-Verlag Berlin Heidelberg, 1982. G.Moroz. New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems. , 1090\U1099. Los Alamitos, CA, USA, 2022. IEEE. G.MorozÉ.Schost. A fast algorithm for computing the truncated resultant. M.Rosenkranz, , ISSAC '16, 341\U348. New York, NY, USA, 2016. ACM. E.Nart. Okutsu\UMontes representations of prime ideals of one-dimensional integral closures. , 55(2):261\U294, 2011. I.Newton. . Manuscript, 1671. A.M.Ostrowski. Über die Bedeutung der Theorie der konvexen Polyeder für die formale Algebra. , 30(2):98\U99, 1921. Talk given at . A.M.Ostrowski. On multiplication and factorization of polynomials. I. Lexicographic orderings and extreme aggregates of terms. , 13(3):201\U228, 1975. A.M.Ostrowski. On the significance of the theory of convex polyhedra for formal algebra. , 33(1):5, 1999. Translated from . V.Y.Pan. Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding. Symbolic Comput.>, 33(5):701\U733, 2002. S.Pauli. Factoring polynomials over local fields. Symbolic Comput.>, 32(5):533\U547, 2001. A.Poteaux. . , Université de Limoges, France, 2008. A.PoteauxM.Rybowicz. Improving complexity bounds for the computation of Puiseux series over finite fields. , ISSAC'15, 299\U306. New York, NY, USA, 2015. ACM. A.PoteauxÉ.Schost. Modular composition modulo triangular sets and applications. , 22(3):463\U516, 2013. A.PoteauxM.Weimann. Using approximate roots for irreducibility and equi-singularity issues in . , arXiv:1904.00286, 2019. A.PoteauxM.Weimann. Computing Puiseux series: a fast divide and conquer algorithm. , 5:1061\U1102, 2021. A.PoteauxM.Weimann. A quasi-linear irreducibility test in |]>>. , 31:6, 2022. A.PoteauxM.Weimann. Local polynomial factorisation: improving the Montes algorithm. A.Hashemi, , ISSAC '22, 149\U157. New York, NY, USA, 2022. ACM. M.V.Puiseux. Recherches sur les fonctions algébriques. , 15:365\U480, 1850. P.Russell. Hamburger\UNoether expansions and approximate roots of polynomials. , 31:25\U95, 1980. A.Schönhage. Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2. , 7:395\U398, 1977. A.Schönhage. The fundamental theorem of algebra in terms of computational complexity. , Math. Inst. Univ. of Tübingen, 1982. V.Shoup. New algorithms for finding irreducible polynomials over finite fields. , 54(189):435\U447, 1990. S.Smith. On the higher singularities of plane curves. , 6:153\U182, 1875. B.L.vander Waerden. . Springer, 7th, 1991. Based in part on lectures by E. Artin and E. Noether. R.J.Walker. , 13. Princeton University Press, 1950. P.Walsh. A polynomial-time complexity bound for the computation of the singular part of a Puiseux expansion of an algebraic function. , 69(231):1167\U1182, 2000. P.G.Walsh. On the complexity of rational Puiseux expansions. , 188(2):369\U387, 1999. S.M.Watt. A fixed point method for power series computation. P.Gianni, , 358, 206\U217. Springer-Verlag, 1989. O.Zariski. . Hermann, Paris, 1986. <\the-glossary|gly> d>>|polynomials in > of degree d>|> >>|\>>>|cost function for univariate polynomial factorization|> |assumption that irreducible factorization is available in >|> >|homogeneous component of of degree |> >>|homogeneous components of from degree to e+\>|> >|initial form of |> >|valuation semi-group of the -th level of a contact tower|> |\>>|group generated by >|> >|ramification index of |\>>|> >|-th defining polynomial of a contact tower|> >|defining ideal of a contact tower of height |> >|level of a contact tower|> > b>|degree of with respect to the contact variable >|> >|polynomials at the level of a contact tower|> >|expression of > in terms of the plain coordinates|> >|conversion to plain coordinates|> A>|valuation of with respect to |> a|\ x>>|derivative of with respect to |> |)>>|>>|> |)>>| regarded in >>|> |]>;\>>| regarded in >>|> <\the-index|idx> > > > > > > > > > > > > > > > > > > > > > > > > > > > >|> > > > > > > > , > > > > > > > > > > > > > <\initial> <\collection> <\attachments> <\collection> <\associate|bib-biblio> <\db-entry|+58kEKjZ1NKEM4eF|inproceedings|PoteauxWeimann2022> <|db-entry> M. > > <\associate|bib-bibliography> <\db-entry|+58kEKjZ1NKEM4eF|inproceedings|PoteauxWeimann2022> <|db-entry> M. > > <\db-entry|+58kEKjZ1NKEM4dq|book|TeXmacs:vdH:book> <|db-entry> > <\db-entry|+aqffSU2j7gUFFx|book|New1671> <|db-entry> > <\db-entry|+63PGfIkmrfTqAP|article|Puis1850> <|db-entry> > <\db-entry|+PXBVIVv9LqhEls|book|vdH:mt> <|db-entry> L. van den J. van der > <\db-entry|+1tmOncbh1W9AYK0O|book|Walker1950> <|db-entry> > <\db-entry|+1tmOncbh1W9AYK0H|book|Zariski1986> <|db-entry> > <\db-entry|+2WheVMn2twB3YIJ|book|GathenGerhard2013> <|db-entry> J. > <\db-entry|+jZzyy9fWllYOxa|article|CK91> <|db-entry> E. > <\db-entry|+cJSkMhbTYXNoYI|article|Sch77> <|db-entry> > <\db-entry|+14b0GIt51qPCwASB|article|vdH:ffnlogn> <|db-entry> J. van der > >> ACM> 12> <\db-entry|+2EIRPFE3ONuyFfG|article|vdH:tower> <|db-entry> G. > Complexity> <\db-entry|+1VcH6KZo2D1Zrx1G|article|vdH:direval> <|db-entry> G. > Complexity> <\db-entry|+NuHCznHJqSBdB5|article|Shoup1990> <|db-entry> > <\db-entry|+1hEca2LzyXL|article|CZ81> <|db-entry> H. > <\db-entry|+erCfbcCOcYyVBq|article|GathenShoup1992> <|db-entry> V. > <\db-entry|+78JfxnbGAPNu1f|inproceedings|KaltofenShoup1997> <|db-entry> V. > <\db-entry|+2dXiKvosB5WaTKV|article|KaltofenShoup1998> <|db-entry> V. > <\db-entry|+NuHCznHJqSBdAP|article|KedlayaUmans2011> <|db-entry> C. > Comput.> <\db-entry|+14b0GIt51qPCwASE|article|vdH:fffact> <|db-entry> G. > > <\db-entry|+1GIl46OCkUAK86R|article|PoteauxSchost2013-cc> <|db-entry> É. > <\db-entry|+NuHCznHJqSBdAo|article|vdH:ffcomp> <|db-entry> G. > Complexity> <\db-entry|+jZzyy9fWllYOxl|article|FrohlichShepherdson1955> <|db-entry> J. C. > Z.> <\db-entry|+jZzyy9fWllYOxm|article|FrohlichShepherdson1956> <|db-entry> J. C. > <\db-entry|+1CQ02y1d169CJ0pF|book|vdW91> <|db-entry> > <\db-entry|+1tmOncbh1W9AYK06|article|KungTraub1978> <|db-entry> J. F. > ACM> <\db-entry|+9xmYrKa1EHi7oFF|inproceedings|HenryMerle1989> <|db-entry> M. > > <\db-entry|+2WheVMn2twB3YIF|article|Duval1989> <|db-entry> > <\db-entry|+24qkmpAM1xifleYQ|phdthesis|Poteaux2008> <|db-entry> > <\db-entry|+24qkmpAM1xifleYR|inproceedings|PoteauxRybowicz2015> <|db-entry> M. > <\db-entry|+Z3c2FLs1B4bANv2|article|PoteauxWeimann2021> <|db-entry> M. > <\db-entry|+1tmOncbh1W9AYK07|inproceedings|Chistov1986> <|db-entry> > <\db-entry|+1tmOncbh1W9AYK0R|article|Walsh2000> <|db-entry> > <\db-entry|+1tmOncbh1W9AYK0Q|article|Walsh1999> <|db-entry> > <\db-entry|+hSBL0bt6tepuqp|article|vdH:fnewton> <|db-entry> > <\db-entry|+cJSkMhbTYXNoYJ|article|vdH:relax> <|db-entry> > Symbolic Comput.> <\db-entry|+1lzrGAapU5PkWuj|inproceedings|Watt1989> <|db-entry> > > <\db-entry|+1tmOncbh1W9AYK0B|article|ChudnovskyChudnovsky1986> <|db-entry> G. V. > Complexity> <\db-entry|+1tmOncbh1W9AYK0C|article|ChudnovskyChudnovsky1987> <|db-entry> G. V. > Complexity> <\db-entry|+24qkmpAM1xifleYD|inproceedings|BoChLeSaSc2007> <|db-entry> F. G. B. É. > > <\db-entry|+24qkmpAM1xifleY7|inproceedings|BostanChristolDumas2016> <|db-entry> G. Ph. > > <\db-entry|+2ZcDi85A22oBjBfL|article|Kedlaya2017> <|db-entry> > <\db-entry|+2WheVMn2twB3YI8|article|CampilloFarran2002> <|db-entry> J. I. > <\db-entry|+1tmOncbh1W9AYJzo|article|Abhyankar1989> <|db-entry> > <\db-entry|+2DA9SrZp1x7JSbbb|article|AbhyankarMoh1973a> <|db-entry> T. > Reine Angew. Math.> <\db-entry|+2DA9SrZp1x7JSbbc|article|Abhyankar1973b> <|db-entry> T. > Reine Angew. Math.> <\db-entry|+qYhUkmR1lNMNv9d|article|Sm1875> <|db-entry> > <\db-entry|+1SRPbfbU1wabnvuS|techreport|PoteauxWeimann2019> <|db-entry> M. > > <\db-entry|+58kEKjZ1NKEM4eJ|article|PoteauxWeimann2022a> <|db-entry> M. > |]>>> <\db-entry|+24qkmpAM1xifleYI|article|CossartMorenoSocias2005> <|db-entry> G. > > série> <\db-entry|+27V1hR6mtuuyjJ1|article|Russell1980> <|db-entry> > <\db-entry|+24qkmpAM1xifleYH|book|Cohen1993> <|db-entry> > <\db-entry|+1tmOncbh1W9AYK0J|article|FordLetard1994> <|db-entry> P. > <\db-entry|+24qkmpAM1xifleYJ|article|FordPauliRoblot2002> <|db-entry> S. X.-F. > >> <\db-entry|+1tmOncbh1W9AYK08|inproceedings|Chistov1991> <|db-entry> > <\db-entry|+1tmOncbh1W9AYK0L|inproceedings|CantorGordon2000> <|db-entry> D. M. > -adic fields> > <\db-entry|+1tmOncbh1W9AYK0I|article|Pauli2001> <|db-entry> > Symbolic Comput.> <\db-entry|+1lPhDapp2g8VYQc|phdthesis|Montes1999> <|db-entry> > <\db-entry|+1tmOncbh1W9AYK0F|inproceedings|FordVeres2010> <|db-entry> O. > F. E. > <\db-entry|+1tmOncbh1W9AYK0V|article|GuardiaMontesNart2011> <|db-entry> J. E. > <\db-entry|+1tmOncbh1W9AYK0G|article|GuardiaMontesNart2012> <|db-entry> J. E. > <\db-entry|+24qkmpAM1xifleYP|article|Nart2011> <|db-entry> > <\db-entry|+1tmOncbh1W9AYK0E|article|BauchNartStainsby2013> <|db-entry> E. H. D. > Comput. Math.> <\db-entry|+1tmOncbh1W9AYK0Z|article|FernandezGuardiaMontesNart2015b> <|db-entry> J. J. E. > Algebra> <\db-entry|+2PkGsaKkSPYU2X|article|GuardiaMontesNart2013> <|db-entry> J. E. > <\db-entry|+1tmOncbh1W9AYK0Y|article|GuardiaMontesNart2015a> <|db-entry> J. E. > Number Theory> <\db-entry|+14b0GIt51qPCwASO|article|GuardiaNartPauli2012> <|db-entry> E. S. > Symbolic Comput.> <\db-entry|+YSgqjs39X6ctuD|phdthesis|vdH:phd> <|db-entry> > <\db-entry|+2DA9SrZp1x7JSbba|article|vdH:dalg> <|db-entry> > <\db-entry|+24qkmpAM1xifleYK|article|vdH:powser> <|db-entry> > <\db-entry|+pPltnj7SXsatPe|article|ACH18> <|db-entry> F. J. H. > <\db-entry|+24qkmpAM1xifleYO|inproceedings|Mora82> <|db-entry> > > <\db-entry|+17hmIgoi26JFES91|inproceedings|MorozSchost2016> <|db-entry> É. > > <\db-entry|+14b0GIt51qPCwASG|article|Maclane1936> <|db-entry> > <\db-entry|+14b0GIt51qPCwASI|article|Maclane1936b> <|db-entry> > <\db-entry|+8lDHqURSvmeWzy|article|Hir64> <|db-entry> > <\db-entry|+1lzrGAapU5PkWuh|article|Pan2002> <|db-entry> > Symbolic Comput.> <\db-entry|+Wo7mJSTFgbIkoa|techreport|Sch82b> <|db-entry> > <\db-entry|+1lzrGAapU5PkWuf|inproceedings|Moroz2022> <|db-entry> > <\db-entry|+1tmOncbh1W9AYK0e|book|GreuelPfister2002> <|db-entry> G. > <\db-entry|+1Hcl3U922Lc9q60c|techreport|vdH:chinese> <|db-entry> > > <\db-entry|+1SzJxwmKFvW96k8|article|Ostrowski1921> <|db-entry> > > <\db-entry|+12WdaesLREXUYsR|article|Ostrowski1999> <|db-entry> > > <\db-entry|+1SzJxwmKFvW96k6|article|Ostrowski1975> <|db-entry> > <\db-entry|+1GIl46OCkUAK86r|article|Lecerf2008> <|db-entry> > <\db-entry|+2WheVMn2twB3YIV|book|Lang2002> <|db-entry> > <\references> <\collection> > > > > > > > > > > |4>> > > > > > |in|)>>|51>> |v|)>>|51>> ||]>;\>>|51>> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > |>|9>> > |>>|9>> > |in>|9>> > > > > > > > > > > > > > > |\>|15>> ||\>>|15>> > |R>|15>> > > > > |\>|15>> > > > |I>|16>> |\d>>|2>> |\>|16>> > > > > > > > |deg> b>|21>> |\>|21>> > > |\>|22>> > > > |\>|22>> |\>|22>> > > |val A>|25>> > > > > > > > > > > > > > > > > > > > > > > |||font-shape||F>>>|\>>>|3>> > | a|\ x>>|40>> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > |H>|34>> |H>|34>> |H>|34>> |H>|34>> > |W>|30>> |W>|30>> |W>|30>> |W>|30>> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|bib> TeXmacs:vdH:book New1671 Puis1850 vdH:mt Walker1950 Zariski1986 GathenGerhard2013 CK91 Sch77 vdH:ffnlogn vdH:tower vdH:direval Shoup1990 CZ81 GathenShoup1992 KaltofenShoup1997 KaltofenShoup1998 KedlayaUmans2011 vdH:fffact PoteauxSchost2013-cc vdH:fffact vdH:ffcomp vdH:fffact KaltofenShoup1997 FrohlichShepherdson1955 FrohlichShepherdson1956 vdW91 KungTraub1978 HenryMerle1989 Duval1989 Poteaux2008 PoteauxRybowicz2015 PoteauxWeimann2021 PoteauxWeimann2021 PoteauxWeimann2021 Chistov1986 Walsh2000 Walsh1999 Poteaux2008 KungTraub1978 vdH:fnewton vdH:relax Watt1989 ChudnovskyChudnovsky1986 ChudnovskyChudnovsky1987 BoChLeSaSc2007 BostanChristolDumas2016 Kedlaya2017 CampilloFarran2002 Abhyankar1989 AbhyankarMoh1973a Abhyankar1973b Sm1875 PoteauxWeimann2019 PoteauxWeimann2022a CossartMorenoSocias2005 PoteauxWeimann2022a Russell1980 Cohen1993 FordLetard1994 FordPauliRoblot2002 Chistov1991 CantorGordon2000 Pauli2001 Montes1999 FordVeres2010 GuardiaMontesNart2011 GuardiaMontesNart2012 Nart2011 BauchNartStainsby2013 FernandezGuardiaMontesNart2015b GuardiaMontesNart2013 GuardiaMontesNart2015a PoteauxWeimann2022 GuardiaNartPauli2012 PoteauxWeimann2021 vdH:phd vdH:dalg vdH:powser vdH:phd ACH18 Mora82 vdH:powser vdH:mt MorozSchost2016 PoteauxWeimann2021 PoteauxWeimann2022 PoteauxWeimann2021 PoteauxWeimann2021 PoteauxWeimann2022 PoteauxWeimann2021 PoteauxWeimann2022 vdH:tower Maclane1936 Maclane1936b Maclane1936 Maclane1936b Montes1999 Hir64 PoteauxWeimann2022 Pan2002 Sch82b Moroz2022 GreuelPfister2002 vdH:tower vdH:chinese GathenGerhard2013 Ostrowski1921 Ostrowski1999 Ostrowski1975 Lecerf2008 Lecerf2008 GathenGerhard2013 GathenGerhard2013 Lecerf2008 Lang2002 vdH:direval vdH:tower vdH:direval Ostrowski1921 <\associate|figure> |2.1>|> The Newton polygon of |P\z*x++z|)>*x+z*x+z*x+x+z*x+x+z*x+z*x>. Each dot represents a monomial in |P>. |> <\associate|gly> |\d>>|polynomials in |\> of degree |\d>|> |||font-shape||F>>>|\>>>|cost function for univariate polynomial factorization|> |assumption that irreducible factorization is available in |\>|> |>|homogeneous component of |a> of degree |e>|> |>>|homogeneous components of |a> from degree |e> to |\e+\>|> |in>|initial form of |a>|> |\>|valuation semi-group of the |t>-th level of a contact tower|> ||\>>|group generated by |\>|> |R>|ramification index of ||\>>|> |\>||i>-th defining polynomial of a contact tower|> |I>|defining ideal of a contact tower of height |t>|> |\>|level |t> of a contact tower|> |deg> b>|degree of |b> with respect to the contact variable |\>|> |\>|polynomials at the level |t> of a contact tower|> |\>|expression of |\> in terms of the plain coordinates|> |\>|conversion to plain coordinates|> |val A>|valuation of |A> with respect to |z>|> | a|\ x>>|derivative of |a> with respect to |x>|> |in|)>>|||initial form of a regarded in \>>|> |v|)>>||valuation of |a> regarded in |\>>|> ||]>;\>>||homogeneous components of |a> regarded in |\>>|> <\associate|idx> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |\>>|> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> |> <\associate|toc> |math-font-series||font-shape||1.Introduction> |.>>>>|> |1.1.Motivation |.>>>>|> > |1.2.Notations and assumptions |.>>>>|> > |Polynomials |.>>>>|> > |Algebraic towers |.>>>>|> > |Factorization |.>>>>|> > |1.3.Related work |.>>>>|> > |Puiseux expansions |.>>>>|> > |Approximate roots |.>>>>|> > |Local factorizations |.>>>>|> > |Non-archimedean value groups |.>>>>|> > |1.4.Outline of the paper |.>>>>|> > |math-font-series||font-shape||2.Introductory examples> |.>>>>|> |2.1.Graded rings and Newton polygons |.>>>>|> > |2.2.Explicit solutions |versus> factorization |.>>>>|> > |2.3.Contact coordinates |.>>>>|> > |2.4.Towards general contact coordinates |.>>>>|> > |2.5.Tschirnhaus transforms and approximate roots |.>>>>|> > |2.6.Central shifts |.>>>>|> > |math-font-series||font-shape||3.Contact calculus> |.>>>>|> |3.1.Weighted valuations |.>>>>|> > |3.2.Contact towers |.>>>>|> > |3.3.Canonical representation |.>>>>|> > |3.4.Arithmetic in contact towers |.>>>>|> > |3.5.Plain coordinates |.>>>>|> > |3.6.Conversion costs |.>>>>|> > |3.7.Semi-valuations in contact towers |.>>>>|> > |math-font-series||font-shape||4.Contact Hensel lifting> |.>>>>|> |4.1.Normalized inverses |.>>>>|> > |4.2.Lifting modular inverses |.>>>>|> > |4.3.Weierstraÿ normalization |.>>>>|> > |4.4.Weierstraÿ normalization via plain coordinates |.>>>>|> > |4.5.Hensel lifting step |.>>>>|> > |4.6.Hensel lifting via plain coordinates |.>>>>|> > |math-font-series||font-shape||5.Separable towers> |.>>>>|> |5.1.Definition |.>>>>|> > |5.2.First derivatives |.>>>>|> > |5.3.Higher derivatives |.>>>>|> > |math-font-series||font-shape||6.Initial expansions> |.>>>>|> |6.1.Definition |.>>>>|> > |6.2.Initial expansions for towers of height |t=1> |.>>>>|> > |6.3.Initial expansions for towers of height |t\2> |.>>>>|> > |6.4.Conversion costs |.>>>>|> > |6.5.Cost of initial expansions |.>>>>|> > |math-font-series||font-shape||7.Newton factorizations> |.>>>>|> |7.1.Irreducible contact towers |.>>>>|> > |7.2.Contact factors |.>>>>|> > |7.3.Contact Newton polygons |.>>>>|> > |7.4.Distinct-slope factorization |.>>>>|> > |7.5.Equal-slope factorization |.>>>>|> > |7.6.Incrementing the contact tower |.>>>>|> > |7.7.The central shift algorithm |.>>>>|> > |math-font-series||font-shape||8.Contact factorization> |.>>>>|> |8.1.Recentered Newton steps |.>>>>|> > |8.2.Main algorithm |.>>>>|> > |8.3.Approximate roots |.>>>>|> > |math-font-series||font-shape||9.Irreducible factorization> |.>>>>|> |9.1.Roots and contact representation |.>>>>|> > |9.2.Discriminants |.>>>>|> > |9.3.Precision loss during distinct-slope factorization |.>>>>|> > |9.4.Precision loss during equal-slope factorization |.>>>>|> > |9.5.Approximate irreducible factorization |.>>>>|> > |math-font-series||font-shape||10.Conclusion> |.>>>>|> |math-font-series||font-shape||Bibliography> |.>>>>|> |math-font-series||font-shape||Glossary> |.>>>>|> |math-font-series||font-shape||Index> |.>>>>|>