> <\body> |<\doc-note> This work has partly been supported by the French NODE project. ||<\author-affiliation> National Research University Higher School of Economics 20 Myasnitskaya Ulitsa 101000 Moscow, Russia |<\author-email> asdemin_2@edu.hse.ru \; >>|<\doc-date> ||<\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> > Consider a sparse polynomial in several variables given explicitly as a sum of non-zero terms with coefficients in an effective field. In this paper, we present several algorithms for factoring such polynomials and related tasks (such as gcd computation, square-free factorization, content-free factorization, and root extraction). Our methods are all based on sparse interpolation, but follow two main lines of attack: iteration on the number of variables and more direct reductions to the univariate or bivariate case. We present detailed probabilistic complexity bounds in terms of the complexity of sparse interpolation and evaluation. > Let > be an effective field. Consider a sparse polynomial \,\,x|]>>, represented as <\equation> F=F*x>+\+F*x>, where |F,\,F|\>\\>\\\>, ,\,\\\>, and \x>*\*x>> for any,\,e|)>\\>>. We call \s> the of and ,\,\|}>> its . The aim of this paper is to factor into a product of irreducible sparse polynomials. All algorithms that we will present are based on the approach of and . Instead of directly working with sparse representations(), the idea is to evaluate input polynomials at a sequence of well-chosen points, do the actual work on these evaluations, and then recover the output polynomials using sparse interpolation. The evaluation-interpolation approach leads to very efficient algorithms for many tasks, such as multiplication, division, gcd computations, etc. In this paper, we investigate the complexity of factorization under this light. One particularly good way to choose the evaluation points is to take them in a geometric progression: for a fixed =,\,\|)>\>|)>>, we evaluate at ,\,\,\>, where \,\,\|)>>. This idea goes back to Prony and was rediscovered, extended, and popularized by Ben Or and Tiwari. We refer to for a nice survey. If > is a finite field, then afurther refinement is to use suitable roots of unity, in which case both sparse evaluation and interpolation essentially reduce to discrete Fourier transforms. In this paper, we do not specify the precise algorithms that should be used for sparse evaluation and interpolation, but we will always assume that the evaluation points form geometric progressions. Then the cost > of sparse evaluation or interpolation at such points is quasi-linear in . We refer to Sections, , and for more details on this cost function > and the algebraic complexity model that we assume. One important consequence of relying on geometric progressions is that this constraints the type of factorization algorithms that will be efficient. For instance, several existing methods start with the application of random shifts \x+\> for one or more variables >. Since such shifts do not preserve geometric progressions, this is a technique that we must avoid. On the other hand, monomial transformations like \y>*\*y>> do preserve geometric progressions and we will see how to make use of this fact. The main goal of this paper is to develop fast algorithms for factoring sparse polynomials under these constraints. Besides the top-level problem of factorization into irreducibles, we also consider several interesting subtasks, such as gcd computations, Hensel lifting, content-free and square-free factorization, and the extraction of multiple roots. While relying on known techniques, we shall show how to conciliate them with the above constraints. Our complexity bounds are expressed in terms of the maximal size and total degree of the input and output polynomials. In practical applications, total degrees often remain reasonably small, so we typically allow for a polynomial dependence on the total degree times the required number of evaluation/interpolation points. In this particular asymptotic regime, our complexity bounds are very sharp and they improve on the bounds from the existing literature. Concerning the top-level problem of decomposing sparse polynomials into irreducible factors, we develop two main approaches: a recursive one on the dimension and a more direct one based on simultaneous lifting with respect to all but one variables. We will present precise complexity bounds and examples of particularly difficult cases. The factorization of polynomials is a fundamental problem in computer algebra. Since we are relying on sparse interpolation techniques, it is also natural to focus exclusively on randomized algorithms of Monte Carlo type. For some deterministic algorithms, we refer to>. Before considering multivariate polynomials, we need an algorithm for factoring univariate polynomials. Throughout this paper, we assume that we have an algorithm for this task (it can be shown that the mere assumption of > being effective is not sufficient). In practice, we typically have =>>>, =\>, \\>, or \\> for some prime and\1>. Most basic is the case when > is a finite field, and various efficient probabilistic methods have been proposed for this case. An early such method is due to Berlekamp>. A very efficient algorithm that is also convenient to implement is due to Cantor and Zassenhaus. Asymptotically more efficient methods have been developed since as well as specific improvements for the case when > is composite. See also14> and. Rational numbers can either been regarded as a subfield of > or >. For asymptotically efficient algorithms for the approximate factorizations of univariate polynomials over >, we refer to. When reducing a polynomial in > modulo for a sufficiently large random prime, factorization over > reduces to factorization over > via Hensel lifting. For more general factorization methods over >, we refer to. Now let \> and assume that we have an irreducible factorization *\*P>> with ,\,P>\\> for \\> or \>. (In practice, we require that ,\,P>> are known with sufficient precision.) In order to turn this into a factorization over>, we need a way to recombine the factors, to find the subsets ,\|}>> for which I>P\\>. Indeed, if is irreducible in > and deg F\2>, then is never irreducible in > and irreducible with probability 1/d> in > for a large random prime . The first recombination method that runs in polynomial time is due to Lenstra-Lenstra-Lovasz. Subsequently, many improvements and variants of this LLL-algorithm have been developed. The problem of factoring a bivariate polynomial \> over > is similar in many regards to factoring polynomials with rational coefficients. Indeed, for a suitable random prime , we have seen above that the latter problem reduces to univariate factorization over >, Hensel lifting, and factor combination. In a similar way, after factoring |)>>> for a sufficiently random > (possibly in an extension field of >, whenever > is a small finite field), we may use Hensel lifting to obtain a factorization in |]>|]>>, and finally recombine the factors. The precise algorithms for factor recombination are slightly different in this context (see also for earlier related work), although they rely on similar ideas. Hensel lifting naturally generalizes to polynomials in three or more variables ,\,x>>. Many algorithms for multivariate polynomial factorization rely on it, as well as many implementations in computer algebra systems. One important property of higher dimensional Hensel lifting is that factor recombination can generally be avoided with high probability, contrary to what we saw for adic and bivariate Hensel lifting. This is due to Hilbert and Bertini's irreducibility theorems: <\theorem> Assume that \,\,x|]>\\> is irreducible and of total degree . Let be the set of points ,\,\,\,\,\,\,\,\|)>\\> for which <\equation> F*t+\*u+\,\,\*t+\*u+\|)> is irreducible in >. Then is an Zariski open subset of >, which is dense over the algebraic closure of >. Effective versions of these theorems can be used to directly reduce the factorization problem in dimension to abivariate problem (and even to a univariate problem if=\>>, using similar ideas). We refer to and6> for a recent presentation of how to do this and to 6.1> for the mathematical background. In order to analyze the computational complexity of factorization, we first need to specify the precise way we represent our polynomials. When using a dense representation ( storing all monomials of total degree d> with their (possibly zero) coefficients), Theorem allows us to directly reduce to the bivariate case (if > is very small, then one may need to replace > by a suitable algebraic extension). The first polynomial time reduction of this kind was proposed by Kaltofen. More recent bounds that exploit fast dense polynomial arithmetic can be found in. Another popular representation is the \Pblack box representation\Q, in which case we are only given an algorithm for the evaluation of our polynomial . Often this algorithm is actually a straight line program (SLP), which corresponds to the \PSLP representation\Q. In these cases, the relevant complexity measure is the length of the SLP or the maximal number of steps that are needed to compute one black box evaluation. Consequently, affine changes of variables() only marginally increase the program size. This has been exploited in order to derive polynomial time complexity bounds for factoring in this model; see also. Here we stress that the output factors are also given in black box or SLP representation. Plausibly the most common representation for multivariate polynomials in computer algebra is the sparse one(). Any sparse polynomial naturally gives rise to an SLP of roughly the same size. Sparse interpolation also provides a way to convert in the opposite direction. However, for an SLP > of length , it takes > time to recover its sparse representation , where >. , the back and forth conversion F\F>> therefore takes quadratic time |)>>. While it is theoretically possible to factor sparse polynomials using the above black box methods, this is suboptimal from a complexity perspective. Unfortunately, general affine transformations() destroy sparsity, so additional ideas are needed for the design of efficient factorization methods based on Hilbert-Bertini-like irreducibility theorems. Dedicated algorithms for the sparse model have been developed in. There are two ways to counter the loss of sparsity under affine transformations, both of which will be considered in the present paper. One possibility is to successively use Hensel lifting with respect to ,\,x>. Another approach is to use a more particular type of changes of variables, like *u,\,\*u|)>>. However, both approaches require to be of a suitable form to allow for Hensel lifting. Some reference for Hensel lifting in the context of sparse polynomials are. For most applications in computer algebra, the total degree of large sparse polynomials is typically much smaller than the number of terms. The works in the above references mainly target this asymptotic regime. The factorization of \Psupersparse\Q polynomials has also been considered in. The survey talk discusses the complexity of polynomial factorizations for yet other polynomial representations. The theory of polynomial factorization involves several other basic algorithmic tasks that are interesting for their own sake. We already mentioned the importance of Hensel lifting. Other fundamental operations are gcd computations, multiple root computations, square-free factorizations, and determining the content of a polynomial. We refer to for classical univariate algorithms. As to sparse multivariate polynomials, there exist many approaches for gcd computations. Whenever convenient, we will assume that the characteristic of > is either zero or sufficiently large. This will allow us to avoid technical non-separability issues; we refer to for algorithms to deal with such issues. A survey of multivariate polynomial factorization over finite fields (including small characteristic) can be found in. Throughout this paper, factorizations will be done over the ground field >. Some algorithms for \Pabsolute factorization\Q over the algebraic closure > of > can be found in; alternatively, one may mimic computations in > using dynamic evaluation. The goal of this paper is to redevelop the theory of sparse polynomial factorization, by taking advantage as fully as possible of evaluation-interpolation techniques at geometric sequences. The basic background material is recalled in Section. We recall that almost all algorithms in the paper are randomized, of Monte Carlo type. We also note that the correctness of a factorization can easily be verified, either directly or with high probability by evaluating the polynomial and the product of the potential factors at arandompoint. As an appetizer, we start in Section with the problem of multivariate gcd computations. This provides a nice introduction for the main two approaches used later in the paper: induction on dimension and direct reduction to the univariate (or bivariate or low dimensional) case. It also illustrates the kind of complexity bounds that we are aiming for. Consider the computation of the gcd of two sparse polynomials \,\,x|]>>. Ideally speaking, setting s>, >\max,s,s|)>>, max,d|)>>, we are aiming for acomplexity bound of the form <\equation> >+d>*s|)>, where > is a constant. Since is typically much smaller than>>, we can afford ourselves the non-trivial overhead with respect to in the term >*s>. The inductive approach on the achieves the complexity() with =1> on many practical instances, but its worst case complexity is >+d*s|)>|)>>. This algorithm seems to be new. Using adirect reduction to univariate gcd computations via so-called \Pregularizing weights\Q, the second approach achieves the complexity() with \2>, and even =1> for many practical examples. This algorithm is a sharpened version of the algorithm from4.3>>. Most existing algorithms for multivariate polynomial factorization reduce to the univariate or bivariate case. Direct reduction to the univariate case is only possible for certain types of coefficients, such as integers, rational numbers, or algebraic numbers. Reduction to the bivariate case works in general, thanks to Theorem, and this is even interesting when =\>: first reduce modulo a suitable prime, then factor over >, and finally Hensel lift to obtain a factorization over >. In this paper, we will systematically opt for the bivariate reduction strategy. For this reason, we have included a separate Section on bivariate factorization and related problems. This material is classical, but recalled for self-containedness and convenience of the reader. If > is a finite field, then we already noted that multivariate factorization does not directly reduce to the univariate case. Nevertheless, such direct reductions are possible for some special cases of interest: content-free factorization, extraction of multiple roots, and square-free factorization. In Section, we present efficient algorithms for these tasks, following the \Pregularizing weights\Q approach that was introduced in Section for gcd computations. All complexity bounds are of the form() for the relevant notions of output size , input-output size >>, and total degree . In Section we turn to the factorization of a multivariate polynomial \,\,x|]>>> using induction on the dimension. Starting with a coprime factorization of a bivariate projection ,x,c,\,c|)>\\,x|]>> of for random ,\,c>, we successively Hensel lift this factorization with respect to ,\,x>. Using a suitable evaluation-interpolation strategy, the actual Hensel lifting can be done on bivariate polynomials. This leads to complexity bounds of the form >+d>*s|)>|)>> with =2>. In fact, we separately consider factorizations into two or more factors. In the case of two factors, it is possible to first determine the smallest factor and then perform an exact division to obtain the other one. In the complexity bound, this means that should really be understood as the number of evaluation-interpolation points, the minimum of the sizes of the two factors. It depends on the situation whether it is faster to lift a full coprime factorization or one factor at a time, although we expect the first approach to be fastest in most cases. Due to the fact that projections such as ,x,c,\,c|)>> are only very special types of affine transformations, Theorem does not apply. Therefore, the direct inductive approach from Section does not systematically lead to a full irreducible factorization of. In Remarks and, we give an example on which our approach fails, together with two different heuristic remedies (which both lead to similar complexity bounds, but with =3> or higher). In the last Section, we present another approach, which avoids induction on the dimension and the corresponding overhead in the complexity bound. The idea is to exploit properties of the Newton polytope of and \Pface factorizations\Q ( factorizations of restrictions of to faces of its Newton polytope). In the most favorable case, there exists a coprime edge factorization, which can be Hensel lifted into a full factorization, and we obtain a complexity bound of the form(). In less favorable cases, different face factorizations need to be combined. Although this yields a similar complexity bound, the details are more technical. We refer to for a few existing ways to exploit Newton polytopes for polynomial factorization. In very unfavorable cases (see Section), the factorization of cannot be recovered from its face factorizations at all. In Section, we conclude with a fully general algorithm for irreducible factorization. This algorithm is not as practical, but addresses pathologically difficult cases through the introduction of a few extra variables. Its cost is *>+d|)>> plus the cost of one univariate factorization of degree |)>>. In this paper paper, we will measure the complexity of algorithms using the algebraic complexity model. In addition, we assume that it is possible to sample a random element from > (or a subset of >) in constant time. We will use |)>> as a shorthand for *|)>>>. We let \|}>> and >\|}>>. We also define >\R\x\0|}>>, for any ring . Given a multivariate polynomial \,\,x|]>> and ,n|}>>, we write \deg> F> ( > F>) for the degree ( valuation) of in >. We also write \deg F> ( ) for the total degree ( valuation of ), and we set \max deg> F>. Recall that > stands for the number of terms of in its sparse representation(). <\render-remark|Acknowledgment> We wish to thank Grégoire Lecerf for useful discussions during the preparation of this paper. Let > (or >>) be the cost to multiply two dense univariate polynomials of degreen> in >. Throughout the paper, we make the assumption that /n> is anon-decreasing function. In the algebraic model, when counting the number of operations in >, we may take =O>. If > is a finite field>, then one has >=O>, under suitable number theoretic assumption. In this case, the corresponding bit complexity (when counting the number of operations on a Turing machine) is|)>>. For polynomials >> of degreen> it is possible to find the unique >, such that with n>. This is the problem of , which can be solved in time |)>> by applying Newton iteration 9.1>. Arelated task is : given > and \\>>, check whether is of the form >> for some >> and monic >>, and determine and if so. For a fixed >, this can be checked, and the unique can be found in |)>> arithmetic operations in > by applying Newton iteration 9.28>. Consider the Vandermonde matrix <\eqnarray*> |||>|>|>>|>|||>>||>|>|>>>>>,>>>> where ,\,\\\> are pairwise distinct. Given a column vector with entries ,\,c>>, it is well known that the products , *C>, >*C>, and |)>>*C> can all be computed in time *log n|)>>. These are respectively the problems of , , , and . For fixed ,\,\>, these complexities can often be further reduced to *log n/log log n|)>>> using techniques from. For our factorization algorithms, we will sometimes need to assume the existence of an algorithm to factor univariate polynomials in > into irreducible factors. We will denote by > the cost of such a factorization as a function of . We will always assume that /d> is non-decreasing. In particular |)>+|)>\+d|)>> for all> and >. If > is the finite field > with >> elements for some odd , then the best univariate factorization methods are randomized of Las Vegas type. When allowing for such algorithms, we may take =O*log |)>>, by using Cantor and Zassenhaus' method from. With the use of fast modular composition, we may take <\equation*> =d>*log> q+ q|)>, but this algorithm is only relevant in theory, for the moment. If the extension degree> is composite, then this can be exploited to lower the practical complexity of factorization. In all probabilistic algorithms in this paper, will stand for a sufficiently large integer such that \Prandom elements in >>\Q are chosen in some fixed subset of >> of size at least. In the case when is larger than the cardinality >|\|>> of >>, this means that > needs to be replaced by an algebraic extension of degree log N/log |\|>>, which induces a logarithmic > overhead for the cost of field operations in >. We will frequently use the following well-known lemma: <\lemma> \UZippel>Let \,\,x|]>> be a polynomial of total degree. Let \> be finite and let ,\,\\S> be chosen independently and uniformly. Then the probability that ,\,\|)>=0> is at most >. <\corollary> Let \>>. The probability that ,\,\|)>=0> for some ,s|}>> is at most />. <\proof> We apply the lemma to ,\,x|)>*P,\,x|)>*\*P,\,x|)>>. <\corollary> Let \>>. Let ,\,\\\>> and let ,\,\\\>> be chosen independently at random. Then the probability that *\,\,\*\|)>=0> for some ,s|}>> is at most >. <\proof> We apply the lemma to *x,\,\*x|)>*P*x,\,\*x|)>*\*P*x,\,\*x|)>>. Consider a polynomial \,\,x|]>> that is presented as a blackbox function. The task of is to recover the sparse representation() from a sufficient number of blackbox evaluations of . One may distinguish between the cases when the exponents ,\,\> of are already known or not. (Here \Pknown exponents\Q may be taken liberally to mean a superset of reasonable size of the set of actual exponents.) One popular approach for sparse interpolation is based on Prony's geometric sequence technique. This approach requires an =,\,\|)>\>|)>>, such that for any ,\,k\\>, there is an algorithm to recover ,\,k> from>*\*\>>. If =0>, then we may take > to be the -th prime number, and use prime factorization in order to recover ,\,k>. If =\> is a finite field, where is a smooth prime ( has many small prime divisors), then one may recover exponents using the tangent Graeffe method. Given an admissible ratio >, Prony's method allows for the sparse interpolation of using evaluations of at \,\,\|)>>> for ,2*s-1>, as well as *log s|)>> operations in > for determining >,\,\>>, and subsequent exponent recoveries. If =>, then the exponents can be recovered if max>, which can be ensured by working over a field extension >>> of > with =O>. If the exponents ,\,\>> are already known, then the coefficients can be obtained from evaluations of at ,\,\>> using one transposed univariate interpolation of cost *log s|)>>. If > is a finite field, then it can be more efficient to consider an > for which ,\,\> are roots of unity. When choosing these roots of unity with care, possibly in an extension field of >, sparse interpolation can often be done in time |)>> from > values of , using discrete Fourier transforms; see for details. In what follows, we will denote by > the cost of sparse interpolation of size , given> values of at a suitable geometric sequence. When using Prony's approach, we may thus take =O*log s|)>>, whenever the cost to recover the exponents ,\,k>> from >*\*\>> is negligible. If the discrete Fourier approach is applicable, then we may even take =O|)>>. <\remark> If we have a bound s> for the number of terms of , then we assume that our sparse interpolation method is deterministic and that it interpolates in time>. If we do not know the number of terms of , then we may run the interpolation method for a guessed number of terms. We may check the correctness of our guessed interpolation > by verifying that the evaluations of and > coincide at a randomly chosen point. By the Schwartz-Zippel lemma, this strategy succeeds with probability at least /N>. <\remark> The above interpolation methods readily generalize to the case when we use a geometric progression of the form ,\*\,\*\,\> with \>|)>> as the evaluation points, by considering the function ,\,x|)>=f*x,\,\*x|)>> instead of . Taking arandom > avoids certain problems due to degeneracies; this is sometimes called \Pdiversification\Q. If > is itself chosen at random, then it often suffices to simply take =\>. We will occasionally do so without further mention. <\remark> For many probabilistic proofs in the sequel of this paper, we will rely onCorollary. However, this requires the ratios > of geometric progressions to be picked at random, which excludes FFT ratios. Alternatively, we could have relied onCorollary and diversification of all input and output polynomials for a fixed random scaling factor \>|)>>> (see the above remark). Assume for instance that we wish to factor \,\,x|]>>. Then the factors \,\,x|]>>> of are in one-to-one correspondence with the factors *x,\,\*x|)>> of *x,\,\*x|)>>. If we rely on Corollary instead of in our complexity bounds for factoring (like the bounds in Theorems or below), then the cost of diversification adds an extra term >*d|)>>, where deg F> and >> is the total size of and the computed factors. On the positive side, in the corresponding bounds for the probability of failure, the quadratic dependence > on the number of evaluation points reduces to a linear one. Similar adjustments apply for other operations such as gcd computations. Opposite to sparse interpolation, one may also consider the evaluation of at points ,\,\> in a geometric progression. In general, this can be done in time *log s|)>>, using one transposed multi-point evaluation of size . If > is a suitable FFT ratio, then this complexity drops to |)>>, using a discrete Fourier transform of size >. In what follows, we will assume that this operation can always be done in time |>|)>>. More generally, we may consider the evaluation of at points ,\,\> in a geometric progression. If s>, we may do this in time *t/s+O>, by reducing to theevaluation of at |t/s|\>> progressions of size . To obtain the evaluations of at ,\,\>> for 0>, we can evaluate *x|)>> at ,\,\,\>. If t>, then we may cut into |s/t|\>> polynomials of size t>, and do the evaluation in time *s/t+O>. <\remark> If > is an FFT-ratio, then the bound for the case when t> further reduces to |)>> plus > bit operations on exponents, since the cyclic projections from reduce in linear time to cyclic polynomials with > terms before applying the FFTs. We did not exploit this optimization for the complexity bounds in this paper, since we preferred to state these bounds for general ratios >, but it should be straightforward to adapt them to the specific FFT case. In this paper, we will frequently need to evaluate at all but one or two variables. Assume for instance that <\equation*> F,\,x|)>=F,\,x|)>+F,\,x|)>*x+\+F>,\,x|)>*x>, where > has > terms for ,\> and s+\+s>>. Then using the above method, we can compute ,\,\,\|)>> for ,t-1> using *|s/t|\>+\+|s>/t|\>|)>+O\*+1|)>+O> operations. One traditional application of the combination of sparse evaluation and interpolation are probabilistic algorithms for multiplication and exact division of sparse multivariate polynomials. For the given \,\,x|]>>, we can compute the product by evaluating , and at a geometric progression ,\,\> with |)>> and recovering of in the sparse representation() via sparse interpolation. The total cost of this method is bounded by >|)>|)>> operations in>, where >\max,s,s|)>>. If and are known, then the exact quotient can be computed in a similar fashion and with the same complexity. If s\>>, then the quotient can actually be computed in time >*/s|)>>. Divisions by zero are avoided through diversification, with probability at least *|2>/N>, by Corollary. Consider a multivariate polynomial \,\,x|]>>. We define \> to be the convex hull of and we call it the of . Given another polynomial \,\,x|]>>>, it is well known that <\equation*> hull P*Q=hull P+hull Q, where the of two subsets \> is s\S,t\T|}>>. Let ,\,w|)>\|)>>> be a non-zero weight vector. We define the -degree>, valuation>, and -ecart> of a non-zeropolynomial \,\,x|]>> by <\eqnarray*> P>|>|,\,e|)>\supp F>*e+\+w*e|)>>>| P>|>|,\,e|)>\supp F>*e+\+w*e|)>>>| P>|>| P-val P.>>>> Note that P\-deg P> and P=ec P>, where we exploit the fact that we allow for negative weights. We say that is -homogeneous> if P=val P>. Any can uniquely be written asasum <\equation*> P=P P;w>+\+P P;w>, of its -homogeneous parts> <\eqnarray*> >|>|supp P,w*e+\+w*e=i>P*x.>>>> We call P\P P;w>> and P\P P;w>> the -leading> and -trailing> parts of . We say that is -regular> if P> consists of a single term >. In that case, we denote P\c>> and we say that is -monic> if . Given another non-zero polynomial \,\,x|]>>>, we have <\eqnarray*> P*Q>|| P|)>* Q|)>>>| P*Q>|| P|)>* Q|)>>>>> Setting ;w>\\\e*w+\+e*w=\|}>>, we also have <\eqnarray*> || P>||\ P;w>>>| P>||\ P;w>.>>>> The Newton polytopes P> and P> are of . In particular, they are contained in the boundary hull P>. Consider the rings \\\\,\,x|]>> and \\\\,x,\,x,x|]>=\*x>*\*x>> of ordinary polynomials and . Both rings are unique factorization domains, but the group of units of > is >>, whereas the group of units of > is >*x>*\*x>>. Factoring in > is therefore essentially the same as factoring in > up to multiplications with monomials in >*\*x>>. For instance, the factorization x\x\x\-x|)>\+x-x|)>> in> gives rise to the factorization *x|)>\-x|)>\+x-x|)>> in >. Conversely, the factorization *x|)>\*x-1|)>\+x*x-x*x|)>> in > gives rise to the factorization x\x\x\-x|)>\+x-x|)>> in>. Similarly, computing gcds in> is essentially the same problem as computing gcds in>. Given any n> matrix \n>>, we define the :\\\> by <\equation*> \,\,x|)>|)>=P>*\*x>,\,x>*\*x>|)>. This is clearly a homomorphism, which is injective (or surjective) if the linear map \\;a\M*a>> is injective (or surjective). Note also that =\\\> for any matrices \n>> and r>>. In particular, if \n>> is unimodular, then > is an automorphism of > with =\>>. Laurent polynomials are only slightly more general than ordinary polynomials and we already noted above that factoring in > is essentially the same problem as factoring in > (and similarly for gcd computations). It is also straightforward to adapt the definitions from Section and most algorithms for sparse interpolation to this slightly more general setting. The main advantage of Laurent polynomials is that they are closed under monomial maps, which allows us to change the geometry of the support of a polynomial without changing its properties with respect to factorization. Let |)>>> be a non-zero weight vector and let >\\,x,\,x,x,t,t|]>>. We define the -tagging map> by <\eqnarray*> :\>|>|>>|,\,x|)>>|>|*t>,\,x*t>|)>.>>>> This map is an injective monomial map. For any \,\,x|]>>, we have \=deg P>, \=val P>, >=s>, and \\deg \-val \=ec P>. Divisibility and gcds are preserved as follows: <\lemma> Let \> with > P=val> Q=val> G=0> for ,n>. Then <\enumerate-alpha> divides in > if and only if > divides > in >. > in > if and only if =gcd,\|)>> in >. <\proof> We claim that divides in > if and only if divides in >. One direction is clear. Assume that divides in >, so that with \>. We may uniquely write *A> with \> and \\> such that > A=0> for ,n>. Since val> Q=val> A+val> P=val>=e+val> A=e> for ,n>, it follows that . Hence divides in >. Our claim implies that divides in > if and only if divides in>. Now we may further extend > to a monomial automorphism of > \ by sending to itself. This yields(). The second property is an easy consequence. <\corollary> Let \> and >. Let =gcd,|)>>, where \\> and\\>. Let \> be such that \min> P,val> Q|)>-val> > for ,n>. Then <\eqnarray*> ,\,x|)>>||>*,\,x,1|)>.>>>> Given a -regular polynomial \,\,x|]>>, we note that any divisor F> must again be -regular. Hence, modulo multiplication with a suitable constant in >, we may always normalize such a divisor to become -monic. In the setting of Laurent polynomials, we may further multiply by a monomial in >*\*z>> such that P=1>. Similarly, when applying>, we can always normalize > to be monic as a Laurent polynomial in by considering P|)>*\>. Both for gcd computations and factorization, this raises the question of how to find weights for which a given non-zero polynomial \,\,x|]>> is -regular. In4.3>, a way was described to compute such a : let ,\,i|)>>\supp F> be such that +\+i> is maximal. In that case, it suffices to take i>, and we note that F\d>, where is the total degree of . For our applications in Sections and it is often important to find a for which F> is small. By trying a few random weights with small (possibly negative) entries, it is often possible to find a regularizing weight with P=O> or P=O>. <\example> Consider *y+3*x*y+x*y+3*y+2*z+4\>. Then, is not >regular for the natural weight \>. If we take \> instead, then is >regular with > F=5>, and we arrive at <\equation*> \>=*y|)>*t+|)>*t+*t+*t+2*z+4. Furthermore, >> can be normalized to be monic as a Laurent polynomial in by considering >/*y|)>>. Note that \> is also a regularizing weight for with > F=1>. Before studying the factorization problem for multivariate polynomials, it is interesting to consider the easier problem of gcd computations. In this section we introduce two approaches for gcd computations that will also be useful later for factoring polynomials. The first approach is iterative on the number of variables. It will be adapted to the factorization problem in Section. The second approach is more direct, but requires aregularizing weight (see Section ). Square-free factorization can be accomplished using a similar technique, as we shall see in Section. The algorithms from Section also draw some of their inspiration from this technique, but also rely on Newton polygons instead of regularizing weights. Let ,\,c> be random elements of >>. For any \,\,x|]>> and ,n>>, we define <\eqnarray*> >,\,x|)>>|>|,\,x,c,\,c|)>.>>>> Let \,\,x|]>>>and gcd>. As we will see below, >=gcd>,Q>|)>> for ,n> with high probability. We may easily compute the univariate greatest common divisor >\gcd>,Q>|)>>. In this subsection, we shall describe an iterative algorithm to compute >> from >> for ,n-1>. Eventually, this yields >>. Let =,\,\|)>> be an admissible ratio or an FFT ratio. For any \,\,x|]>> and any \>, let <\eqnarray*> |k+1,i|\>>>|>|>,\,\,u|)>>>|>>|>|>,\,\|)>.>>>> For any \>, we have |k+1,i|\>>=gcd|k+1,i|\>>,Q|k+1,i|\>>|)>> with high probability. Now these greatest common divisors are only defined up to non-zero scalar multiples in >>. Nevertheless, there exists a unique greatest common divisor >> of >> and >> whose evaluation at \c> coincides with >>. If >> is known, then>>, |k+1,i|\>>>, and |k+1,i|\>>> can be computed for successive >> using fast evaluation at geometric progressions. For any \>, we may then compute the univariate gcd |k+1,i|\>>> of |k+1,i|\>>> and |k+1,i|\>>>, under the normalization constraint that |k+1,i|\>>|)>=G>>. It finally suffices to interpolate >> from sufficiently many |k+1,i|\>>>. This yields the following algorithm: <\vgroup> <\specified-algorithm> \,\,x|]>>> > <|specified-algorithm> If 1>, then compute > using a univariate algorithm and return it Compute >> by recursively applying the algorithm to >> and >> Let s>>> Compute >>, |n,i|\>>>, |n,i|\>>> for ,m> using sparse evaluation Compute |n,i|\>>=gcd|n,i|\>>,Q|n,i|\>>|)>> with |n,i|\>>|)>=G>> for ,m> Recover from |n,1|\>>,\,G|n,m|\>>> using sparse interpolation Return Before we analyze this algorithm, we will need a few probabilistic lemmas. Assume that ,\,c> and ,\,\> are independently chosen at random from a subset of >> of size at least (if > is a small finite field, this forces us to move to a field extension). <\lemma> Let \,\,x|]>> be such that >> and >> are coprime. Then the probability that >> and >> are not coprime is bounded by *d/N>. <\proof> Let > with k> be a variable that occurs both in >> and in >>. Then <\equation*> R\Res>>,B>|)>\0. If > occurs in >,B>|)>>, then ,\,x,c|)>=0>, which can happen for at most \deg> A>*deg B>+deg A>*deg> B>\2*d*d> values of>. <\lemma> Let \,\,x|]>> and >. Then the probability that >\gcd>,Q>|)>> for some ,n|}>> is bounded by *d*d/N>. <\proof> Let us write and , where and are coprime. Then we have >\gcd>,Q>|)>> if and only if >> and >> are not coprime. The result now follows by applying the previous lemma for ,1>. <\theorem> Let s>, >\s+s+s>, max ,d|)>>, and \max ,\|)>>. Then Algorithm is correct with probability at least *d+n**\|)>/N> and it runs in time <\equation*> O>/s+\|)>*+s*|)>*log \|)>|)>. <\remark*> The probability bound implicitly assumes that n*d+n**\>, since the statement becomes void for smaller . In particular, we recall that this means that the cardinality of > should be at least *d+n**\>. <\proof> Assuming that >=gcd>,Q>|)>> and >\0> for ,n-1> and ,s>>, let us prove that Algorithm returns the correct answer. Indeed, these assumptions imply that \gcd|n,i|\>>,Q|n,i|\>>|)>> can be normalized such that \ |)>=G>> and that the unique such > must coincide with |n,i|\>>>. Now >=gcd>,Q>|)>> fails for some with probability at most *d/N>, by Lemma. Since \\>, the condition >\0> fails with probability at most *\/N> for some and , by Corollary. This completes the probabilistic correctness proof. As to the complexity, let us first ignore the cost of the recursive call. Then the sparse evaluations of >>, |n,i|\>>>, and |n,i|\>>> can be done in time >/s+\|)>*|)>>: see Section. The univariate gcd computations take |)>*log \|)>> operations. Finally, the recovery of using sparse interpolation can be done in time *|)>>. Altogether, the complexity without the recursive calls is bounded by >/s+\|)>*+s*|)>*log \|)>>. We conclude by observing that the degrees and numbers of terms of , , and can only decrease during recursive calls. Since the recursive depth is , the complexity bound follows. <\remark> When recovering from |n,1|\>>,\,G|n,m|\>>> using sparse interpolation, one may exploit the fact that the exponents of ,\,x> in are already known. <\example> Let \,\,x|]>> be random polynomials of total degree and consider A*B>, A*C>. With high probability, gcd=A>. Let us measure the overhead of recursive calls in Algorithm with respect to the number of variables . With high probability, we have <\equation*> s=*s>>,s=*s>>,s=*s>>. Assuming that n>, it follows that <\equation*> 2*s>>\s,3*s>>\s,3*s>>\s. This shows that the sizes of the supports of the input and output polynomials in Algorithm become at least twice as small at every recursive call. Consequently, the overall cost is at most twice the cost of the top-level call, roughly speaking. Algorithm has the disadvantage that the complexity bound in Theorem involves afactor . Let us now present an alternative algorithm that avoids this pitfall, but which may require a non-trivial monomial change of variables. Our method is a variant of the algorithm from4.3>. Given \,\,x|]>>, we first compute a regularizing weight for or , for which max P,ec Q|)>> is as small as possible. From a practical point of view, as explained in Section, we first try a few random small weights . If no regularizing weight is found in this way, then we may always revert to the following choice: <\lemma> For vectors \\>, let |\|>\+\+\>>. Let ,\,i|)>\supp P> be such that \d>> is maximal. Let ,\,j|)>>\supp Q> be such that \d>> is maximal. Let i> if \> and j> otherwise. Then max P,ec Q|)>\d*d>. <\proof> \ Assume that . Then k=i\k\*\*\d*d> for any \> with \0>. The case when is handled similarly. Now consider \\>, \\>, and =gcd,|)>> in ,x,\,x,x,t,t|]>>. We normalize > in such a way that =0> and such that > is monic as a polynomial in; this is always possible since > is -regular. Let =,\,\|)>\\> be an admissible ratio or an FFT ratio. For any \>, we evaluate at \\> and t>, which leads us to define the univariate polynomials <\eqnarray*> >>|>|,\,\,t|)>>>|>>|>|,\,\,t|)>>>|>>|>|,\,\,t|)>.>>>> With high probability, >=ec >, and >> is the monic gcd of >*t> and >*t>>, where val >> and \val >>. For sufficiently large (with >), we may thus recover > from >,\,>> using sparse interpolation. Finally, for 1>, we obtain >*\*x>*,\,x,1|)>>, where =min > P,val> Q|)>-val> > for ,n>. This leads to the following algorithm: <\vgroup> <\specified-algorithm> \,\,x|]>>> \,\,x|]>>, such that > <|specified-algorithm> Find a regularizing weight for or For > do <\indent> Compute >>, >> for ||\>+1,\,i> Compute >=gcd>,>|)>> with >> monic and >=0> for ||\>+1,\,i> If >,\,>> yield > through sparse interpolation, then <\indent> Let \min > P,val> Q|)>-val> > for ,n> Return >*,\,x,1|)>> <\remark> If > is normalized in ,x,\,x,x,t,t|]>> to be monic as a polynomial in , then we may need to interpolate multivariate polynomials with negative exponents in order to recover> from >,\,>>. In practice, many interpolation algorithms based on geometric sequences, like Prony's method, can be adapted to do this. As in the previous subsection, assume that ,\,\> are independently chosen at random from a subset of >> of size at least . We let max,d|)>>, s>, and >\s+s+s>. <\lemma> Assume that or is -regular. Let =gcd,|)>> with =0>> be monic as a polynomial in . Take >\,\,\,t|)>>>, >\,\,\,t|)>>>, and >\,\,\,t|)>>>. The probability that >=gcd>,>|)>> for all ,s> is at least */N.> <\proof> We have >=gcd>,>|)>> if and only if Res/,/|)>> does not vanish at>. Now the degree of is at most >, so the probability that |)>\0> for a randomly chosen\\>> and all ,s|}>> is at least*/N>, by Corollary. <\corollary> The probability that one can recover > from >,\,>> with > using sparse interpolation is at least *s/N|)>>. <\theorem> Let s>, >\s+s+s>, max ,d|)>>, and max P,ec Q|)>\d>. Algorithm is correct with probability at least *s/N|)>> and it runs in time <\equation> O>/s+e|)>*+s**log e|)>. <\proof> The correctness with the announced probability follows from Corollaries and, while also using Remark. The computation of >> and >> through sparse evaluation at geometric progressions requires >/s+e|)>*|)>> operations (see Section). The univariate gcd computations take *log e|)>> further operations. The final interpolation of > from >,\,>> can be done in time|)>>. <\example> Let ,\,x|]>>>. Consider the particular case when is monic as apolynomial in ,\,x|]>|]>>. Then, ,0|)>> is a regularizing weight for , and therefore also for gcd>. This situation can be readily detected and, in this case, we have max> P,deg> Q|)>> in the complexity bound(). <\remark> We may need fewer evaluation points to interpolate the gcd > in Algorithm in case the terms of > are distributed over the powers of . For instance, if the terms are distributed evenly, then we have s/e> in the complexity bound(). Lemma allows us to project the general problem of multivariate gcd computations down to the univariate case. For the polynomial factorization problem, no such reduction exists: given a random univariate polynomial of degree 2> over a finite field, there is a non-zero probability that this polynomial is not irreducible. For this reason, it is customary to project down to bivariate instead of the univariate polynomials (when applicable, an alternative is to project down to univariate polynomials with integer coefficients; see, for instance). This explains why it is interesting to study the factorization of bivariate polynomials in more detail. Throughout this section, is a bivariate polynomial in >> of degree > in and of degree > in. As in Sections and, random numbers will be drawn from a subset of >> of size at least . We will recall some classical results concerning the complexity of bivariate factorization, important techniques, and special cases: content-free factorization, root extraction, Hensel lifting, and square-free factorization. Recall that the of +\+F>*x>\\>> in is defined by <\equation*> cont F\gcd,\,F>|)>>\\. We say that is (or ) in if F=1>. Given two random shifts ,\\\>>>, we have F=gcd,y|)>>,F,y|)>|)>> with high probability. More precisely: <\proposition> The content F> can be computed in time *d+|)>*log d|)>> with aprobability of success of at least /N>. <\proof> Without loss of generality, we may assume that |\|>\N\2*d>. Let us first consider the case when F=1>. Then we claim that ,y|)>\\\\>|)>\1>. Indeed, for +1> pairwise distinct ,\,\>\\>>, the Vandermonde matrix |)>i,j\d>> is invertible, so ,y|)>,\,F>,y|)>|)>=,\,F>|)>>=1>. It follows that ,F|)>\0>, regarded as an element of >, is non-zero, and its total degree is bounded by >. By Lemma, it follows that ,y|)>,F,y|)>|)>\0> with probability at least /N>. In that case, ,y|)>>,F,y|)>|)>=1>. We have proved our probabilistic correctness claim in the particular case when F=1>. In general, we factor *cont F>. With probability at least /N>>, we have ,y|)>>,F,y|)>|)>=gcd,y|)>>,,y|)>|)>*cont F=1>. As to the complexity bound, the evaluations ,y|)>> and ,y|)>> require *d|)>> operations and the univariate gcd computation can be done in time |)>*log d>. Let >> and \2>. Assume that >> for some \>> and \>. Assume that |\|>\N\|2>+2>. Then can be computed efficiently as follows. After dividing out a suitable power of >>, we may assume without loss of generality that F=0>. For a random shift >, we next replace > with |)>>. With high probability, this ensures that \0>. Modulo division of > by >, we may then assume without loss of generality that =1>. Let \\>> be an admissible ratio or an FFT ratio. For any \>, we define the univariate polynomial >\F|)>>. With high probability, we have >\0>. Let >> be the unique univariate polynomial such that >|)>>=F>/F>>. Such >> can be found efficiently using univariate root extraction. For >, we may recover from >,\,R>>> using interpolation. <\proposition> With the above notations and assumptions, we may compute and in time *d|)>|)>>, with a probability of success of at least |2>+2*d|)>/N>. <\proof> The random shift \F|)>> and the corresponding backshift >\|)>>> can be computed in time *|)>|)>> using the so-called convolution method5>. The >> can also be computed in time *|)>|)>> using fast multipoint evaluation at geometric sequences. The same holds for the interpolation of from the >>. Finally, the univariate root extractions can be computed in time *|)>|)>>. The algorithm is correct as long as \0>> and |)>\0> for ,d>>. The probability that \0> and \0> for a random choice of > is at least /N>, by Lemma. In that case, \F\0> and the probability that |)>\0>> for ,d> is at least |2>/N>, by Corollary. Let \> be content-free in and assume that has a non-trivial factorization >, and F=1>. Assume that \ =d>> and that >> and > are known and coprime (in particular and are coprime). Using a random shift \F|)>>>, these assumptions can be enforced with high probability, provided that and are coprime. Without loss of generality we may also assume that we normalized the factorization of > such that> is monic. Under these assumptions, we may compute and as follows: <\itemize> We first use Hensel lifting to obtain a factorization *> with ,\\|]>> and =P>, =Q>, and such that > is monic in . We compute > and > modulo >> for =2*d+1>. For a random shift \\>>, we apply rational function reconstruction5.7> to ,y|)>> to obtain \> with ,y|)>=A/B+O>|)>> and =1>> and of the smallest possible degree with these properties. With high probability, we then have >. We may compute in a similar way. <\proposition> Given and =P*Q> satisfying the above assumptions, let =deg F>, =deg F>, and \max,d|)>>. We may lift the factorization of > into afactorization in time <\equation*> O*d|)>+|)>*log \|)>, with a probability of success of at least *d/N>. <\proof> We first observe that there is a unique factorization that lifts the factorization of >, thanks to our hypothesis that F=1>>. Since this hypothesis also implies that P=cont Q=1>, the denominator of > as an element of > coincides with the leading coefficient of as a polynomial in . Consequently, the denominator of ,y|)>> equals if and only if ,P,y|)>|)>\0>>. Since the degree of ,P|)>\\>> is bounded by*d>, this happens with probability at least *d/N>. Since the degrees of the numerator and denominator of ,y|)>\\> do not exceed>, it suffices to compute > modulo +1>|)>> in order to recover and . This completes the probabilistic correctness proof. As to the complexity bound, the Hensel lifting requires *d|)>+|)>*log d|)>> operations in >, when using a fast Newton iteration. The computation of ,y|)>> requires *d|)>> further operations and the rational function reconstruction can be done in time |)>*log d|)>> using the technique of half gcds11>. The proposition generalizes in a straightforward way to the case when has > pairwise coprime factors ,\,P>>. In that case, one may use fast multifactor Hensel lifting, to obtain the following: <\proposition> Let \> be such that F=1>> and =d>. Assume that can be factored as *\*P>>, where ,\,P>> are pairwise coprime and known. Assume also that ,\,P-1>> are monic. Then we may lift the factorization >=P*\*P>> into a factorization *\*P>> in time <\equation*> O*d|)>*log \+\*|)>*log \|)>, with a probability of success of at least *d*d/N>. <\example> Consider <\equation*> F\x*y-x+x*y+x+x*y+3*x*y-2*x+2*y-2*y with <\equation*> F=-x+x-2*x=+x-2|)>*x. This factorization lifts to the following factorization of in |]>>: <\equation*> F=*,=x++,=-1|)>*x+y-y. Taking=1>>, we obtain the following rational reconstruction of ,y|)>> up to the order|)>>: <\equation*> =1++=+3*y-2|y-1>. Consequently, -1|)>*> is the sought factor of in >|x,y|]>>. In a similar way, we find that -1|)>*>. Assume that \> is content-free in and of total degree . Assume also that \d>. Recall that the of is of the form <\equation*> F=P*P*\*P, where each > is the product of all irreducible factors of that occur with multiplicity. Note that some of the > are allowed to be units in > and that the > are unique up to multiplication by such units. The polynomials ,\,P> are pairwise coprime. Since \d>>, they must also be separable in both and ( ,\ P/\ x|)>=,\ P/\ y|)>>=1>). The square-free factorization of > can be computed efficiently as follows: <\itemize> For a random shift >, replace by |)>>. Compute the square-free factorization of >. Hensel lift this into the square-free factorization of using Proposition. Apply the shift in the opposite direction. <\proposition> We can compute the square-free factorization of in time <\equation*> O*d|)>*log \+|)>*\*log d+|)>*log d|)>, with a probability of success of at least *d*d/N>, where \i\d\P\\|}>|\|>>. <\proof> Given ,d|}>>, consider > and >\ P/\ x|)>*F/P>. The polynomials |)>> and >|)>>> are coprime if and only if ,>|)>\\> does not vanish at \>>. Since this resultant has degree at most *d>, this happens with probability *d/N>>. Therefore, the probability that all |)>> are pairwise coprime and all |)>>> are separable is at least *d*d/N>. In that case, |)>=P|)>*P|)>*\*|)>>> is the square-free decomposition of |)>>. Modulo normalization, we are thus in the position to apply Proposition. This proves the probabilistic correctness of the algorithm. The computation of the shift \F|)>> can be done in time *|)>|)>> using the algorithm from5> and the same holds for the shifts in the opposite direction in the last step. The square-free factorization of the univariate polynomial >> can be done in time |)>*log d|)>>: see and14.23>. We with Proposition. General bivariate factorization of > can often be reduced to Hensel lifting as in Section using a random shift y+\> and diversification \*x>, \*y>. Let =deg F>, =deg F>. The best currently known complexity bound is the following: <\theorem> 8>> Let \> be square-free and content-free in both and. Assume that =0> or \d*-1|)>>. Then we can compute the irreducible factorization of in time <\equation*> *d+d>|)>+|)> and with a probability of success of at least /N>. The actual proposition in also contains a similar result for finite fields of small characteristic. For > as in Theorem, square-freeness and content-freeness can be achieved with high probability and negligible cost using the algorithms from Sections and. \ In the bivariate setting of the previous section, we have presented several efficient algorithms for the computation of partial factorizations. In this section, we will generalize three of them to the multivariate setting: removal of content, root extraction, and square-free factorizations. The common feature of these generalizations is that they recover the answer directly from the corresponding univariate specializations of the problem, in asimilar fashion as the gcd algorithm from Section. Consider a polynomial \,\,x|]>\\> and a variable >. If, for every non-trivial factorization with \,\,x|]>\\>, both and depend on >, then we say that is (or ) in >. Note that this is always the case if > F\1>. If is contentfree in > for all ,n>, then we say that is >. For a given variable >, say >, we can efficiently test whether is content-free with respect to >: for random ,\,\\\>>, we form the bivariate polynomial F,\*t,\,\*t|)>>> and compute > B\\> using the method from Section. With high probability, is content-free with respect to > if and only if > B=1>>. Performing this test for each of the variables ,\,x> yields: <\proposition> We may check whether is content-free (and, if not, determine all variables> with respect to which is not content-free) in time +n*|)>*log d|)>> and with aprobability of success of at least /N>. <\proof> The proof is similar to the one of Proposition. This time, for the probability bound, we consider the resultant *t,\,c*t|)>,F*t,\,c*t|)>|)>> as a polynomial in ,\,c|]>>, of total degree at most >. If > F=1>, then this resultant does not vanish with probability at least /N> for random \>, \>, \\,\,c\\>. As to the complexity bound, for ,n>, let > and > be random and consider \F*t,\,\*t,\,\*t,\,\*t|)>> and \F*t,\,\*t,\,\*t,\,\*t|)>>. We compute the> simultaneously for ,n> in time +d|)>|)>> and similarly for the >. Finally, the computation of ,C|)>> for ,n> takes |)>*log d|)>> operations. Assume now that is not content-free, say with respect to >. With high probability, the content of with respect to > then equals the gcd of ,x,\,x|)>> and ,x,\,x|)>>, for two random shifts ,\\\>. This leads to a non-trivial factorization of for the cost of one gcd computation and one exact division. Given \,\,x|]>>> and \2>, multivariate >-th root extraction is the problem of determining \>> and \,\,x|]>>, such that >>, whenever such and exist. We devise an algorithm in the same vein as the algorithm for gcd computations from . We first compute a regularizing weight for such that F> is small. Recall that the regularity of ensures that F=\*x>> for some \\>> and \\>. We take \> and note that we then must have F=c* R|)>>>. Now let = F|)>*t>*\\\,x,\,x,x,t,t|]>> with \val \>, so that =0> and > is monic as a polynomial in . Let =,\,\|)>\\> be an admissible ratio or an FFT ratio. For any \>, we define the univariate polynomial >\,\,\,t|)>>. Let >> be the unique monic polynomial with >|)>>=>>. For sufficiently large (with |)>>), we may recover> from >,\,>> using sparse interpolation. Finally, we have >*,\,x,1|)>>, where \\> is such that >=val> F> for ,n>. <\proposition> Assume that is -regular with ec F\d>. Then we may compute \>>> and \,\,x|]>> with >>, whenever such and exist, in time <\equation*> O/s+e|)>*|)>+s*|)>. <\proof> The evaluations >\,\,\,t|)>> take /s+e|)>*|)>|)>> operations, whereas the sparse interpolation of > from the >> can be done in time |)>|)>>. The cost of the univariate >-th root extractions >\>|\>> is bounded by *|)>>. Consider \,\,x|]>> of total degree . Assume that is content-free and that =0>> or \d>>. The factorization of <\equation*> F=c*P*P*\*P into square-free parts can be done using a similar technique as for gcd computations in Section. We start with the computation of a regularizing weight for . Setting ec F>, we recall that d>, whence \e>. Let <\equation*> =\\\\\,x,\,x,x,t,t|]> and consider the normalized square-free factorization <\equation*> =c*x>*t>***\*, where \>>, \\>, \\>, and where ,\,\\> are monic and of valuation zero in. Let =,\,\|)>\\> be an admissible ratio or an FFT ratio. For any \>, we define the univariate polynomials <\eqnarray*> >>|>|,\,\,t|)>>>|>>|>|,\,\,t|)>,|k=1,\,d|\>.>>>> The normalized square-free factorization of >*t>> is of the form <\equation*> >*t>=c>*>*>|)>*\*>|)>, where >\\>>, and >,\,>> are monic polynomials in >. We recover ,\,> using sparse interpolation and then ,\,P> by setting 1> and multiplying by appropriate monomials in >*\*x>>. More precisely, =x>*,\,x,1|)>>, where =1> if > F=i> and =0> otherwise. <\proposition> Assume that is -regular with ec F\d>. Let max>,\,s>|)>> and \i\d\P\|}>|\|>>. Then we may compute asquare-free factorization of \ in time <\equation*> O*/s+e|)>*+s**log e|)>, with a probability of success of at least *d*s/N>. <\proof> The probabilistic correctness is proved in a similar way as in the bivariate case (see Proposition), while also using Corollary. The sparse evaluation and interpolation at a geometric sequence require /s>+e|)>*>|)>+\+/s>+e|)>*>|)>|)>=O*/s+e|)>*|)>> operations. The univariate square-free factorizations can be done in time *log e|)>>, using and14.23>. It is well known that a divisor of a sparse polynomial can have far more terms than the polynomial itself, because of the identity <\equation> x-1=*+\+1|)>, and the possibility to replace by any other sparse polynomial. For this reason, many problems on sparse polynomials turn out to be NP-hard. In a way that has been made precise in, this fundamental example is actually the main cause for such hardness results. The example() is less dramatic if we consider sparse polynomials for which the total degree is much smaller than the total number of terms, which is often the case in practice. But even then, it still has some unpleasant consequences. Recall from that <\equation*> gcd-1,x-x-x+1|)>=x+\+x+x+\+1 for coprime , with q\4>. This gcd contains exactly terms. Suchgcds can also occur during content-free factorizations. For instance, the content of <\equation*> F=x-1+-x-x+1|)>*y in is +\+x+x+\+1>. Now consider <\equation*> F\F,y|)>*\*P,y|)>. Then and \6>. The size of each individual factor in any irreducible factorization of is bounded by , which is sharp with respect to . However, the content of in has size =>. This means that content-free factorization as a preparation step (before launching a \Pmore expensive\Q factorization method) is a bad idea on this particular example. Let \,\,x|]>\\> be a content-free polynomial and recall that any factor of is again content-free. Let ,\,c> be random non-zero elements of >. For any \,\,x|]>>> and ,n>>, we define <\eqnarray*> >,\,x|)>>|>|,\,x,c,\,c|)>.>>>> In this section, we describe several algorithms for the factorization of , following a similar recursive approach as for the computations of gcds in Section. This time, we start with the computation of a non-trivial factorization of the bivariate polynomial>>. From this, we will recursively obtain non-trivial factorizations of >,F>,\,F>>. This will in particular yield a non-trivial factorization of >>>. We will separately study the cases when has a factorization into two or more coprime factors. In order to reconstruct factorizations of from factorizations of >>, it is important that the projection A>> be sufficiently generic. For ,n>, let us denote by > the projection A>>. We say that > is for \,\,x|]>> if >=,\,e|)>\e\supp A|}>> for ,n-1>. As usual, we assume that ,\,c> are independently chosen at random from a subset of >> of size at least . <\lemma> Given \,\,x|]>>>, the probability that > is faithful for is at least *deg> A/N>. <\proof> Given supp A>, let |)>=> A>A,\,e,i>*x>*\*x>*x>. Then ,\,e|)>>\supp A>> if and only if |)>=0>, which happens with probability at most > A/N>>. \ Now consider a factorization *\*P>> such that ,\,P>> are pairwise coprime. We say that > is for this factorization if > is faithful for ,\,P>> and |)>,\,\>|)>> are pairwise coprime. <\lemma> Given a factorization *\*P>> and ,n-1|}>>, the probability that > is faithful for this factorization is at least *>+\+s>>|)>+n*d|)>/N>. <\proof> This directly follows from Lemma (while using that j>d>*d>\d>) and the previous lemma (using induction on ). While faithful mappings preserve coprime factorizations in a predictable way, it may still happen that an irreducible polynomial is projected to a reducible one. In fact this may even happen with probability > for a random choice of ,\,c>. <\example> Let 3> and \\> for an odd prime 3>. Consider <\eqnarray*> |>|,x|)>-x>>|>|>|+x>>>> Then is irreducible, but >=+\|)>*-\|)>> whenever =\> is a square in >. If > is a random element of >>, then this happens with probability >. (Note that we may replace > by any other irreducible polynomial that involves both > and >.) This phenomenon is not so much of a problem if we want to recursively Hensel lift acoprime factorization >=A*B> for which we that there exist ,\,x|]>>> with >> and >> (see Algorithms and below). However, any algorithm for Hensel lifting will fail ifis irreducible or, more generally, if no such and exist(Algorithm below for the irreducible factorization of may therefore fail on Example). Consider a non-trivial factorization , where \,\,x|]>\\> are coprime. Assume that > is faithful for this factorization. Let us show how to recover >> and>> from >> and >>, for ,n-1>. Let =,\,\|)>> be an admissible ratio or an FFT ratio. For any \,\,x|]>> and any \>, let <\eqnarray*> |k+1,i|\>>>|>|>*t,\,\*t,u|)>>>>> and <\equation*> A>\A|k+1,i|\>>|)>=A>*t,\,\*t|)>. With high probability, we have F|k+1,i|\>>=deg F>>, >=deg P>>, >=deg Q>>, and the polynomials >> and >> are again coprime. It follows that each factorization <\eqnarray*> >>||>*Q>>>>> can be Hensel-lifted (see Section) into a factorization <\eqnarray*> |k+1,i|\>>>|||k+1,i|\>>*Q|k+1,i|\>>.>>>> We now recover >> and >> from |k+1,1|\>>,\,P|k+1,s>>|\>>> and |k+1,1|\>>,\,Q|k+1,s>>|\>>>, respectively, using sparse interpolation. \ In fact, if >>\s>>>, then we may interpolate >> and recover >> using one exact division. Moreover, we may exploit the assumption that the supports of >> and >> with respect to ,\,x>> coincide with the supports of >> and >>. In the algorithm below, this explains why evaluation points indeed suffice: <\vgroup> <\specified-algorithm> <\surround||> <\wide-tabular> ||||>|<\cell> \,\,x|]>\\> and coprime \,x|]>\\> with >=A*B> >|>|<\cell> \,\,x|]>\\> with >=A>, >=B>, and , whenever such afactorization exists (we raise an error if this is not the case) and > is faithful for this factorization >>> <|specified-algorithm> If , then return > Compute >,Q>> by recursively applying the algorithm to >,A,B> Permute >Q>> if necessary to ensure that s>>\s>>> Compute |n,i|\>>>, >>, and >> for ,m>, using sparse evaluation Deduce >\F>/P>> for ,m> For ,m> <\indent> Compute |n,i|\>>,Q|n,i|\>>> with |n,i|\>>=P|n,i|\>>*Q|n,i|\>>> using Hensel lifting (Section) Raise an error if this fails Recover from |n,1|\>>,\,P|n,m|\>>> using sparse interpolation Let F/P> and return > <\remark> The faithfulness assumption implies that supp P>\\>. If is small, then this support bound is tight. Consequently, we may use sparse interpolation with known supports in order to recover . <\theorem> Let min,s|)>>, \max,s|)>> >\max ,s|)>>, deg F>>, and \max> F,\,deg> F|)>>. Then Algorithm runs in time <\equation*> O>/s|)>*|)>+\*d*+s**d|)>+s**log d|)>|)> and returns the correct result with probability at least <\equation*> 1-O*d|N>|)>. <\proof> Assume that we correctly recovered >> and >> and let us investigate the probability that the results and are correct. Let us first examine the probability that the Hensel lifting method from Section works correctly. This is the case whenever the following three conditions are satisfied for,m>: <\enumerate> >> and >> are coprime; We have F|n,i|\>>=1>; We have F|n,i|\>>=deg F>>. Consider <\equation> R\Res>*t,\,x*t|)>|t>>>,>*t,\,x*t|)>|t>>>|)> with d>. We have 0> since >> and >> are coprime. The first condition fails for a given if and only if vanishes under the substitutions \\>,\,x\\>. This happens with probability at most */N>> for some , by Corollary. Let us next consider <\equation*> R\Res*t,\,x*t,u|)>,*t,\,x*t,u|)>>|)>, where ,\,x,t,t,u> are formal indeterminates. Since is content-free, we have \0>>. Now F|n,i|\>>=1>> whenever > does not vanish under the substitutions \\,\,x\\>. The second condition therefore fails for some with probability at most */N>>, by Corollary and using the fact that \4*d>. Finally, with probability at least /N>, we have <\equation*> deg F|n,i|\>>=deg F>=deg F*t,\,x*t,x|)> for ,m>, by Corollary. Let us now return to the correctness of the overall algorithm. Concerning the top-level call, we have the following: <\itemize> Obtaining >> from the evaluations >>, >> for ,m> by exact univariate polynomial division is possible as long as >=deg F>>. This condition fails with probability at most *d/N> by Corollary. We have shown above that \ the Hensel lifting strategy from Section can be applied with probability at least *s/N|)>>>. By adapting the proof of Proposition such that we can apply Corollary, the Hensel lifting itself also succeeds with probability at least *s/N|)>>, for ,m>. Altogether, we correctly determine and with probability at least *d/N|)>>>. Since there are > recursive levels and since the sizes of the supports of >>, >>, and>> are all smaller than those of , , and , the probabilistic correctness claim follows. As to the complexity bound, let us now study the cost when not counting the recursive calls: <\itemize> The computation of the |n,i|\>>>, >>, and >>, using sparse evaluation at sequences requires >/s+d*deg> F|)>*|)>=O>|)>+\*d*|)>> operations in>. The evaluations of >> are obtained by exact univariate polynomial division and require |)>> operations in total. Lifting the factorization for all of the evaluations requires *d|)>+*log d|)>|)>> further operations, by Proposition. We obtain +\+P>*x>> from |n,1|\>>,\,P|n,m|\>>> using sparse interpolation of the coefficients ,\,P>> in time >|)>+\+>>|)>|)>=O+s*\|)>=O*|)>>. The recovery of through sparse polynomial division takes >/s|)>*|)>|)>> further operations, as explained in Section . We conclude that the cost is >/s|)>*|)>+\*d*+s**d|)>+s**log d|)>>, when not counting the recursive calls. Since there are > recursive levels and since the sizes of the of >>, >>, and>> are all smaller than those of , , and , the complexity bound. <\example> Let , where \,\,x|]>> are coprime. Now consider the polynomial ,\,x|)>=F*x,x*x,\,x*x|)>>. When factoring using Algorithm, the last lifting steps with respect to ,\,x> all operate on a projection>> of size>. This is an example when the overhead in the complexity bound is sharp. However, the support of is very special, since it is contained in an affine subspace of dimensionn>. It is easy to detect this situation and directly obtain the exponents in the last variables as affine combinations of the known exponents in the first variables. More generally, it may happen that the fibers of the support under the projection with respect to the last variables are all small. It would be interesting to develop specific optimizations for this situation, directly apply sparse interpolation on the fibers. The lifting algorithm generalizes in a straightforward way to the case when is a product of more than two factors. This time, we wish to recover a factorization *P>*\*P>>> from \P>,\,A>\P>>>, assuming that ,\,A>> (hence ,\,P>>) are pairwise coprime. <\vgroup> <\specified-algorithm> <\surround||> <\wide-tabular> ||>|<\cell> \,\,x|]>\\>, irreducible and pairwise coprime ,\,A>\\,x|]>\\>, \2>, \\>>, and ,\,\>\\>, such that >=\*A>*\*A>>>> >|>|<\cell> irreducible and pairwise coprime ,\,P>\\,\,x|]>\\> with *P>*\*P>>>> and >=A,\,P>>=A>>, whenever such afactorization exists (we raise an error if this is not the case) and > is faithful for this factorization >>> <|specified-algorithm> If , then return ,\,A>|)>> Recursively apply the algorithm to >,A,\,A>> to compute >,\,P>>> Let max>>,\,s>>>|)>> Compute |n,i|\>>>, >,\,P>>> for ,m>, using sparse evaluation Deduce >|)>>,\,>>|)>>>> for ,m> For ,m> <\indent> Compute |n,i|\>>,\,P>|n,i|\>>> with |n,i|\>>=\*|n,i|\>>|)>>*\*>|n,i|\>>|)>>>> using Hensel lifting Raise an error if this fails Recover > from the |n,i|\>>> using sparse interpolation, for ,\> Return ,\,P>>|)> <\remark> More precisely, we compute >|)>>> using binary powering and >> from >|)>>> using dense bivariate >-th root extraction, for ,\>. As an optimization, we may first sort the factors of >> such that >>\s>>\\\s>>>> and then compute >>|)>>>\F>/>|)>>*\*-1>>|)>-1>>|)>> using exact division. <\theorem> Let max>,\,s>>|)>>, >\max |)>>, \max> F,\,deg> F|)>>, and deg F>. Then Algorithm runs in time <\equation*> O>/s+\*d|)>*+s**d|)>*log \+s**log d|)>|)> and returns the correct result with probability at least <\equation*> 1-O*s*d|N>|)>. <\proof> The proof is similar to that of Algorithm . Assume now that we correctly recovered >,\,P>>> and let us investigate the probability that the results ,\,P>> are correct. To apply the Hensel lifting method from Section, the following three conditions must be satisfied for ,m>: <\enumerate> >,\,P>>> are pairwise coprime; We have F|n,i|\>>=1>; We have F|n,i|\>>=deg F>>. The analysis is similar as in the proof of Theorem, except that() now becomes <\equation*> R\i\j\\>Res>*t,\,x*t|)>|t>>>,>*t,\,x*t|)>|t>>>|)> and the probability that vanishes for one of the substitutions is now bounded by *s*d/N|)>>, since 2*d*\>. Using the fact there are n> recursive levels, this completes the probabilistic correctness proof. For the cost analysis, we again start by analyzing the cost of the algorithm without the recursive calls: <\itemize> The evaluation of the factors >,\,P>>> on the geometric sequence can be done in time >+\|)>*>|)>+\+>>+\|)>*>>|)>|)>=O*\*|)>=O*d*|)>>. The computation of the |n,i|\>>> and >> takes /s+\*d|)>*|)>> operations. The powers >|)>>,\,>>|)>>>> can be obtained in time *d>|)>+\+>*d>>|)>|)>|)>=O|)>>, using binary powering. The Hensel lifting is done using Proposition instead ofProposition, which contributes |)>*log \+\*|)>*log \|)>|)>> to the cost. The bivariate root extractions take *\*d>|)>+\+*\>*d>>|)>|)>|)>=O*d|)>|)>> operations, by Proposition. The recovery of the > from the |n,i|\>>> using sparse interpolation requires >|)>+\+>>|)>|)>=O|)>> operations. Summing these costs and multiplying with the recursive depths > yields the desired complexity bound. <\example> There are cases when the recursive application of Algorithm may lead to intermediate expression swell. For instance, for and \>, consider the polynomials <\eqnarray*> >|>|+y|)>-+v|)>>>|||+y-u-v|)>*Q>>|>|>|j\k>+y+u+v|)>>>>> and note that > has |)>> terms, whereas > has only > terms. Now consider <\equation*> F=P*P. Then a direct factorization of into irreducibles can be done in time |)>>, whereas recursively factoring out +y-u-v|)>> and then +y-u-v|)>> may lead us to consider intermediate expressions like *Q> of size |)>>. <\remark> The ideas behind Algorithm can readily be adapted to -adic lifting, in order to factor a polynomial \,\,x|]>> with rational coefficients. In that case, we start with a factorization >=>*>>*\*>>>>> of >\F mod p\\,\,x|]>> for some sufficiently large prime. The goal is to lift this into a factorization of >> for some sufficiently large > and then to recover a factorization of using rational number reconstruction5.10>. The relevant analogues of |n,i|\>>> and >> are |i|\>>\*t,\,\*t|)>>> and >\A|i|\>> mod p>, where the prime number plays asimilar role as the formal indeterminate . The bivariate Hensel lifting in |]>> is replaced by traditional univariate Hensel lifting in >. In lucky cases, given an irreducible factorization *P>*\*P>>>>, random choices of ,\,c>>> give rise with high probability to an irreducible factorization >=\*>|)>>*\*>>|)>>>>. For such , we may use the following algorithm to compute its irreducible factorization: <\vgroup> <\specified-algorithm> a content-free polynomial \,\,x|]>\\> an irreducible factorization *P>*\*P>>>> or an exception <|specified-algorithm> If 1>, then return the result of a univariate irreducible factorization Let ,\,c> be random elements of >> Compute an irreducible factorization >=\*A>*\*A>>>> of >> Apply Algorithm to and this factorization <\theorem> Let max>,\,s>>|)>>, >\max |)>>, \max> F,\,deg> F|)>>, and deg F>. Then Algorithm runs in time <\equation*> O>/s+\*d|)>*+s**d|)>*log \+s**log d|)>|)>+|)>+|)> and returns the correct result (when no exception is raised) with probability at least <\equation*> 1-O*s**d|N>|)>. <\proof> This follows from Theorems,, and Lemma. <\remark> We have seen in Section that the size of the content of a multivariate polynomial can be much larger than the size of the polynomial itself, in pathological cases. In such cases, we may wish to avoid content-free factorization as a first step of ageneral algorithm for irreducible factorization. This can be achieved by adapting Algorithm so as to factor out the content in > at the top-level and performing the recursive call and bivariate lifting to instead of . Incorporating the content-free factorization directly into the main algorithm in this way yields a similar complexity bound as in Theorem, but with > instead of |)>>. <\remark> An alternative approach for reducing to the content-free case, which also works for the algorithms from Section below, is to tag according to a regularizing weight . This has the advantage of \Pexposing\Q the entire factorization of with respect to the tagging variable . Of course, this requires to replace the degree > in the complexity bound by F\d>. <\remark> The problem from Remark can be partially remedied by amending the bivariate lifting step: instead of raising an error when |n,i|\>>\\*|n,i|\>>|)>>*\*>|n,i|\>>|)>>>>, we may continue the Hensel lifting to a higher precision (the |n,i|\>>> are now power series in |]>>) and determine which factors need to be combined in order to obtain afactorization of |n,i|\>>> (using the techniques from). Doing this for all leads to a finest partition \\\J>> of ,\|}>> such that |n,i|\>>\J>P|n,i|\>>> is a polynomial factor of|n,i|\>>> for ,m> and ,\>. We next apply the sparse interpolation to the polynomials|n,i|\>>> instead of the series |n,i|\>>>. This may require more than interpolation points, so we also double until the interpolation step succeeds. Combined with Remark, this yields to an algorithm of complexity <\equation*> O>/s+\*d|)>*+s*|)>|)>|)>+, where is the maximal size of an irreducible factor of >> for ,n|}>>. Unfortunately, we have not yet been able to perform a clean probabilistic analysis for this method. Indeed, we still need to prove that the algorithm terminates in reasonable expected time for irreducible polynomials. Now consider the example <\equation> F=x+x-x, for which we obtain <\equation*> F|3,i|\>>=+\|)>*t-u. Whenever =\> with 3> and +\> is a square in >, the projected polynomial|3,i|\>>> is not irreducible. In principle, this only happens with probability >, so this is unlikely to happen for all values of ,m>. However, we were unable so far to prove ageneral bound. We also note that this probabilistic argument is different from traditional Hilbert\UBertini style arguments6.1>; see also and6>. <\remark> Another way to turn Algorithm into a method that always succeeds with high probability would be to apply random monomial transformation to . For instance, after the change of variables =y*y*y>, =y*y>, =y>, we have <\equation*> F=*y+y-1|)>*y, for the polynomial from example(). With high probability, Algorithm returns the correct irreducible factorization of after this rewriting. The iterative approach from Sections and has the disadvantage of introducing adependence on the dimension in the complexity bounds. In the case of gcd computations, the idea of regularizing weights allowed for the more direct approach in Section. Unfortunately, direct adaptations of this approach to factorization only work in very special cases, because it is unclear how to recombine the factors found at different evaluation points. One notable exception is when \,\,x|]>\\> factors, say, into two irreducible factors of degrees one and two in one of the variables; in that case, we can recombine based on degree information. In this section, we will develop another \Pdirect\Q approach for the factorization of \,\,x|]>\\>> that avoids iteration on the dimension . Except for precomputations in the algorithm from Section, the algorithms in this section do not rely on regularizing weights, but exploits more subtle properties of the Newton polytope of . We will present three versions of our approach in order to deal with Newton polytopes of increasing complexity. For simplicity, we only present them in the case when is the product of two factors. As we shall see in Section, even the last and most elaborate version of our approach is not fully general. We will conclude with a theoretical variant that is less efficient in practice, but which has the advantage of providing a full algorithm for the computation of irreducible factorizations. Assume that the unique factorization of contains exactly two factors <\equation> F,\,x|)>=P,\,x|)>*Q,\,x|)>, where \,\,x|]>> are irreducible and distinct and both depend on the \Pmain\Q variable, say, >. In particular, this implies that is content-free and square-free. Assume also that the following conditions hold: <\description> > F,0,\,0|)>=deg> F>. ,0,\,0|)>> and ,0,\,0|)>> are coprime. Note that allows us to normalize the factorization <\equation*> F,0,\,0|)>=P,0,\,0|)>*Q,0,\,0|)> by requiring that ,0,\,0|)>> is monic. From now on we will always assume that we have done this. Under these assumptions, we claim that and can be computed from ,0,\,0|)>>> and ,0,\,0|)>> using Hensel lifting and sparse interpolation. In order to see this, let =,\,\|)>\>|)>> be an admissible ratio or an FFT ratio. For each\>>, we define bivariate polynomials >,P>,Q>\\,t|]>> by <\eqnarray*> >>|>|,\*t,\,\*t|)>>>|>>|>|,\*t,\,\*t|)>>>|>>|>|,\*t,\,\*t|)>.>>>> Then >,0|)>=P,0,\,0|)>> and >,0|)>=Q,0,\,0|)>> are coprime and we have >=P>*Q>>. This allows us to compute >> and >> from >>, >,0|)>>, and >,0|)>> using Hensel lifting. For sufficiently large , with ,s|)>|)>>, we may then use sparse interpolation to recover from >,\,P>> or from >,\,Q>>. This leads to the following algorithm: <\vgroup> <\specified-algorithm> <\wide-tabular> ||>|<\cell> \,\,x|]>> such that there exists a factorization() that satisfies and; we assume that ,0,\,0|)>> and ,0,\,0|)>> are given >|>|<\cell> \,\,x|]>> >>> <|specified-algorithm> For > do <\indent> Compute >> for ||\>+1,\,i> Compute >,Q>> for ||\>+1,\,i>, <\indent> using bivariate Hensel lifting for >>, >,0|)>>, >,0|)>> If >,\,P>> yield through sparse interpolation, then return > If >,\,Q>> yield through sparse interpolation, then return > <\theorem> Let min,s|)>>, \max ,s|)>>, >\max ,s|)>>, \deg> F>, and deg F>>. Then Algorithm is correct with probability at least |2>/N> and runs in time <\equation*> O>/s|)>*|)>+\*d*+s**d|)>+s**log d|)>. <\proof> The correctness is clear. Let us analyze the cost of the main steps of the algorithm: <\itemize> The computation of the >> takes /s+\*d|)>*|)>> operations. The Hensel lifting has a total cost of *d|)>+*log d|)>|)>>. The sparse interpolation of (or ) takes *d*|)>> operations. The sparse polynomial division to recover (or ) requires >/s|)>*|)>|)>> . Adding up these costs, the complexity bound follows. The algorithm is correct as long as the final division succeeds, which is the case with probability at least |2>/N>. The assumptions and are fairly strong: they are never satisfied both if is a homogeneous polynomial. Now the assumptions and essentially allow us to perform the bivariate Hensel lifting using the method from Section. The problem that we face in order to extend the approach from Algorithm is that random shifts \+y> are not allowed for the bivariate Hensel lifting from Section: we only have an efficient algorithm to compute > and > are given, not |)>> and |)>>. Instead, we need a way to generalize the algorithm from Section to the case when the Newton polygon of is non-trivial. In this subsection, we start with the simplest \Psingle slope\Q case. Since this material is a supplement to Section, we adopt the notation from there. Assume that \> has a non trivial factorization with \\\>. We define the of to be the \Plower border\Q of its Newton polytope: <\equation*> \\npol P\\ hull P\hull P\\\>|)>. It is the union of a finite number of edges ,\,E>> between ,j|)>,\,>,j>|)>\supp P> with =val P>>, >=deg P>, and \\\i>>. For each edge >, there is a corresponding weight \-i|)>/-j|)>,1|)>> such that =hull lt> P>. Assume that > has a single edge, let w>, and let \> and \>> be coprime such that -i|)>/-j|)>>. Now consider <\eqnarray*> >|>|,t|)>*t F>>>|>|>|,t|)>*t P>>>|>|>|,t|)>*t Q>.>>>> Then ,,\\> and =*>. Moreover, = F|)>,t|)>*t F>>, and we have similar expressions for > and >. If P> and Q> are known and if their transforms > and > are coprime, then this enables us to compute and by applying the Hensel lifting method from Section to >, >, and >. Let us now return to the factorization problem from Section and let us show how to generalize Algorithm using the material from the previous subsection. Let ,e+\+e|)>\e\supp F|}>> and let > be the lower boundary of its convexhull. With high probability, we have >=S> and >=\>, for any given. The last edge of > joins the points ,a|)>> and ,b|)>> for ,b\\> with \b=deg> F>. Let ,\,w|)>> with =p/q=/-a|)>> and =\=w=1>>, where \>, \>>, and =1>. Now consider the assumptions <\description> > tp F=deg> F>. P> and Q> are coprime. The hypotheses and correspond to the special case when . If P> and Q> are known ( through the recursive factorization of F> if is not -homogeneous), then the algorithm from Section allows us to Hensel lift the factorization F= P|)>* Q|)>> into a factorization . This leads to the following generalization of Algorithm: <\vgroup> <\specified-algorithm> <\wide-tabular> ||>|<\cell> \,\,x|]>> such that there exists a factorization() that satisfies and, together with P> and Q> such that F= P|)>* Q|)>> >|>|<\cell> \,\,x|]>> >>> <|specified-algorithm> For > do <\indent> Compute >>, P|)>>>, Q|)>>> for ||\>+1,\,i> Compute >>, >> for ||\>+1,\,i>, <\indent> using bivariate Hensel lifting from Section for >>, P|)>>>, Q|)>>> If >,\,P>> yield through sparse interpolation, then return > If >,\,Q>> yield through sparse interpolation, then return > <\theorem> Let min,s|)>>, \max ,s|)>>, >\max ,s|)>>, \deg> F>, and deg F>>. Then Algorithm is correct with probability at least |2>/N> and runs in time <\equation*> O>/s|)>*|)>+\*d*+s**d|)>+s**log d|)>. <\proof> The proof is similar to the proof of Theorem. The main change is that the generalized algorithm also requires the evaluations of P> and Q> on our sequence. This takes /s+\*d|)>*+/s+\*d|)>*|)>=O>/s+\*d|)>*|)>> additional operations, which is absorbed by the complexity bound. Note that the assumptions and are actually slightly more liberal than the statement that the Newton polygon should have a single edge. For this reason, Algorithm is very likely to apply as soon as there exists a variable > for which > F> is small (of course, we may then assume modulo a permutation of variables). This in particular the case when > F=2>, unless F> is not squarefree (one may need to replace \x> and multiply with >). Note that a single\Pgood\Q variable > suffices. <\remark> Both Algorithms and involve recursive factorizations of polynomials in less variables. However, the supports of the recursive calls are obtained through projection for Algorithm and through restriction for Algorithm. The second case is often more favorable in the sense that the recursive supports decrease faster in size. <\remark> Consider the case when *x> and *x>. Then F> coincides with , so the requested factorization of F> is not simpler than the desired factorization of . This is due to the fact that the exponents of all lie in a linear subspace of >. In particular, the degree in > of any term of can be determined as a function of the degrees of the other variables. In particular, we may recover a factorization of from afactorization of ,\,x|)>>. Using a straightforward induction on , this allows us to ensure that F> has strictly less terms than . As soon as > F\4>, it can happen that every factor of has a Newton polygon with at least two edges. In order to deal with this situation, the algorithm from Section may be further generalized to accommodate Newton polygons with multiple slopes. In order to explain how, we again adopt the notation from Sections and. So assume that \0> and \0>, that >has an arbitrary number of edges, and that > P> and > Q> are known for each edge>. Assume also that > P|)>> and > Q|)>> are coprime for ,\>, where :\\\\\\\> is the normalization mapping with \P/ P>*y P>|)>>. We will say that > P|)>*> Q|)>> is a of > F>. The aim of this subsection is to lift these factorizations efficiently into the global factorization . It is well known that a variant of the Newton polygon method can be used in order to factor over the ring |)>> of Laurent series. An efficient algorithm for this task was described in. One important subtask is distinct slope factorization: each edge > gives rise to a unique monic factor \\|)>> of such that > F=c*x*y*tp> A> for \>>>, \>, and the natural generalization of the notation >> to|)>>. The methods from allow for the efficient computation of the >: it takes time *d|)>*log d|)>> to compute *y A>\\|]>> at order > for ,\>. Now for each ,\|}>>, the known factor > P> of > F> induces a factor of > A> that can be Hensel lifted into the factor \gcd|)>> of >, by adapting the techniques from Section to Laurent series coefficients. For some \|)>>, we then have *\*B>>. We may determine in a similar way as in Section. The other factor > can be obtained using one bivariate division. The total cost of this method to compute and is bounded by *d|)>*log d+|)>*log d|)>>. We are now in a position to generalize Algorithm to the case when the bivariate Hensel lifting is done using the multiple slope method from the previous subsection. The general algorithm is fairly technical, so we found it more instructive to illustrate the main ideas on an example. Let <\eqnarray*> ||>|||*x>>|||*x.>>>> For generic ,\\\>>, consider =P*t,\*t|)>>, =Q*t,\*t|)>>, and =*>. Then <\eqnarray*> >||,,|}>>>|>||,,|}>>>|>||,,,,,|}>,>>>> whence > is the closed triangle with vertices >, >, and >. Its lower boundary consists of the edge from > to > and the edge from > to >, which correspond to the weights > and => respectively. The generalized algorithm starts with the recursive factorizations of F> and > F>, which yields <\equation*> || F>|| P|)>* Q|)>>>| P>||>| Q>||>>>>\||||> F>||> P|)>*> Q|)>>>|> P>||*x>>|> Q>||*x.>>>>> However, these factorizations do not tell us from which factors of they originate: the factorization of could have been of the form *Q>, with P=tp P> and > P=tp> Q>. In order to obtain the correct matches, the next idea is to consider the bivariate factorization of > for some sufficiently generic values of > and >. For instance, for =2> and =3>, we obtain <\equation*> ||>||>>|>||>>>>>\|| P|~>>||>| Q|~>>||>>>>\||> P|~>>||>>|> Q|~>>||.>>>>> From these computations, we deduce that the factor of F> comes from the same factor of as the factor *x> of > F>. We say that we have managed to the factors and *x> of the different slopes. In other words, if is a non-trivial factor of, then, up to constant scaling, we now know that either A,tp> A|)>>= P,tp> P|)>> or A,tp> A|)>= Q,tp> Q|)>>. For any \> and \>, let >=A*t,\*t|)>>. Having completed the above matching, we may now use the lifting algorithm from Section to deduce >> and>> from >>, P|)>>>, > P|)>>>, Q|)>>>, and > Q|)>>>. Doing this for sufficiently many , we may finally recover and using sparse interpolation. The approach from Section is fairly general. However, as we will show now, it is possible to construct pathological examples that can still not be treated with this method. <\example> Consider a polynomial \,\,x|]>> and a monomial >*\*x>> such that ,\,e|)>> lies in the interior of the Newton polytope . For instance, we may take <\eqnarray*> |>|*x+x*x+x*x+x*x*x+x*x*x+x*x*x>>||>|*x*x.>>>> Now consider <\equation*> F=*M|)>*\*>*M|)>, for pairwise distinct ,\,\>\\>. This polynomial cannot be factored using the techniques from this section, so far. In fact, it is not so much the factorization of the bivariate >> polynomials that is aproblem: instead of Hensel lifting, we may very well rely on Theorem (this only increases the exponent in in Theorems and, which is subdominant anyway if >>). The true problem is matching corresponding factors of >> for different , especially in the most difficult cases like Example. We conclude this section with an approach that completely solves this problem, modulo a polynomial overhead in . Let ,\,\>, ,\,\>, ,\,\> be random elements of >> and let > be new indeterminates. We define <\eqnarray*> ,\,x,t,u,\|)>>|>||)>+\*\|)>**u+\|)>*x,\,|)>+\*\|)>**u+\|)>*x|)>.>>>> For >, we also define <\eqnarray*> |i|\>>|)>>|>|,\,\,t,u,\|)>.>>>> If is irreducible, then |i|\>>> is irreducible with high probability, by Theorem, and so are |i|\>>> and |i|\>>>. For general , this also means that the factors of |i|\>>|)>>, |i|\>>>, and |i|\>>> are in effective one to one correspondence, with high probability. Moreover, by construction, <\eqnarray*> |i+1|\>>>|||i|\>>.>>>> Using this relation, we may therefore match corresponding factors of |i|\>>> and |i+1|\>>> with high probability. Having solved the matching problem, we still need to ensure that the factorizations of the |i|\>>> are normalized in a suitable way such that we can recover the factors of using sparse interpolation. For this, let be a regularizing weight for with ec F\d>. Let> be yet another indeterminate and consider <\eqnarray*> ,\,x,t,u,\,\|)>>|>||)>+\*\|)>**u+\|)>*x*\>,\,>>|)>+\*\|)>**u+\|)>*x*\>|)>>>||1|\>>,\|)>>|>|,\,\,t,u,\|)>.>>>> By construction, any factor > of|1|\>>> has leading coefficient |1|\>>*t>*u>*\>> with respect to>, for some ,\,\\>, >>, and some monomial x>*\*x>>. Thus, any such factor> can be normalized by dividing out the constant |1|\>>> in>>. Now consider the unique factorization of |1|\>>> into a product of normalized factors times anon-zero scalar in >>. This yields a factorization of |1|\>>> by setting =1>. The factorization of |1|\>>> can be lifted to the factorization of |2|\>>>, which is, in turn, lifted to the factorization of |3|\>>>, and so on. An irreducible factorization of > is recovered via interpolation from the factorizations of |1|\>>,\,F|m|\>>> for sufficiently large . Finally, to obtain a factorization of from a factorization of >, we can set u\\\0>, and apply the map \|)>*x>. This leads to the following algorithm: <\vgroup> <\specified-algorithm> \,\,x|]>\\> an irreducible factorization >*\*P>>>> of <|specified-algorithm> Compute > Let be a regularizing weight for Compute an irreducible factorization |1|\>>=c*|1|\>>|)>>*\*>|1|\>>|)>>>>, normalized as above For > do <\indent> Compute |i|\>>> for ||\>+1,\,m> For ||\>+1,\,m> do <\indent> Hensel lift |i-1|\>>=c*|i-1|\>>|)>>*\*>|i-1|\>>|)>>>> <\indent> into an irreducible factorization |i|\>>=c*|i|\>>|)>>*\*>|i|\>>|)>>>> Deduce |i|\>>,\,P>|i|\>>> from |i|\>>|)>>,\,>|i|\>>|)>>>> via root extraction Try to determine ,\,P>> from |i|\>>,\,P>|i|\>>> (,m>) using sparse interpolation <\indent> If successful, then set u\\\0>, \|)>*x> and return >*\*P>>>> <\theorem> Let max>,\,s>>|)>>, >\max |)>>, deg F>>, and ec F\d>. Assume that =0> or \2*d>. Then Algorithm runs in time <\equation*> O*>|)>+|)>*s*log d|)>+|)>+ and succeeds with probability at least *+2*s*d+3*+d|)>/N>. <\proof> We factor |1|\>>> as a dense polynomial in four variables of degree e+3*d> (after division by a suitable power of >) using the algorithm from5>. This requires |)>+> operations in > and the probability of success is at least /N>>. Let *>*\*>>>> be an irreducible factorization of . By our assumption on the characteristic, the factors ,\,>> are all separable. We will apply6.9> for each of the points in our geometric progression. By using Corollary instead of the Schwartz-Zippel lemma in the proof of6.9>, we deduce that the specializations |i|\>>>, |i|\>>>>, and thus |i|\>>> are irreducible for ,m> and ,\>>, with probability at least */N\1-360*d*/N>. Under this assumption, and modulo reordering the factors, the computed |i|\>>> are of the form |i|\>>=c*|i|\>>> for suitable scaling factors ,\,c>\\>>> that do not depend on . The check whether the computed factorization of is correct reports a false positive with probability at most>, by Remark or the Schwarz-Zippel lemma. Let us now analyze the complexity. We first observe that >\O*s|)>>, since >=O|)>> when > consists of a single monomial of total degree d>. Using5> in arecursive manner, we may compute > from in time |)>*s|)>=O*s|)>|)>>. We saw above that the factorization of |1|\>>> requires at most |)>+> operations in >. The computation of the specializations |i|\>>> for ,m> requires *d*m/s|)>=O*>|)>|)>> further operations. The Hensel lifting of the |i-1|\>>> can be done in time |)>*s*log d|)>> using Proposition and evaluation-interpolation in the remaining variable. The > Hensel lifts succeed with probability at least/N>. Adding up, we obtain the desired complexity bound, as well as the claimed bound for the probability of success. <\remark> Due to the |)>> overhead, Algorithm is mainly of theoretical interest. It is plausible that() can be replaced by a less, but still sufficiently, generic formula. This would reduce the overhead in . In practice, one may use Algorithm as a last resort, in the unlikely case that all other strategies from Sections and fail. <\bibliography|bib|tm-plain|> <\bib-list|106> F.Abu Salem, S.GaoA.G.B.Lauder. Factoring polynomials via polytopes. , 4\U11. New York, NY, USA, 2004. ACM. A.V.Aho, K.SteiglitzJ.D.Ullman. Evaluating polynomials on a fixed set of points. , 4:533\U539, 1975. M.Alberich-Carramiñana, J.Guàrdia, E.Nart, A.Poteaux, J.RoéM.Weimann. Polynomial factorization over henselian fields. , arXiv, 2022. . K.Belabas, M.van Hoeij, J.KlünersA.Steel. Factoring polynomials over global fields. , 21(1):15\U39, 2009. M.Ben-OrP.Tiwari. A deterministic algorithm for sparse multivariate polynomial interpolation. , 301\U309. New York, NY, USA, 1988. E.R.Berlekamp. Factoring polynomials over finite fields. , 46:1853\U1859, 1967. E.R.Berlekamp. Factoring polynomials over large finite fields. , 24:713\U735, 1970. L.Bernardin. . , ETH, Zürich, 1999. D.J.Bernstein. Scaled remainder trees. Available from , 2004. E.Bertini. . Giuseppe Principato, 1923. A.BorodinR.T.Moenck. Fast modular transforms. , 8:366\U386, 1974. A.Bostan, G.LecerfÉ.Schost. Tellegen's principle into practice. , 37\U44. Philadelphia, USA, August 2003. A.BostanÉ.Schost. Polynomial evaluation and interpolation on special sets of points. of Complexity>, 21(4):420\U446, August 2005. Festschrift for the 70th Birthday of Arnold Schönhage. P.Bürgisser, M.ClausenM.A.Shokrollahi. . Springer-Verlag, Berlin, 1997. 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. T.ChenM.Monagan. The complexity and parallel implementation of two sparse multivariate Hensel lifting algorithms for polynomial factorization. , 150\U169. Springer-Verlag, 2020. T.ChenM.Monagan. Factoring multivariate polynomials represented by black boxes: a maple + C implementation. , 16, 2022. G.ChèzeG.Lecerf. Lifting and recombination techniques for absolute factorization. of Complexity>, 23(3):380\U420, 2007. A.L.Chistov. Efficient factoring polynomials over local fields and its applications. , 1, 1509\U1519. Springer-Verlag, 1991. G.E.Collins. Subresultants and reduced polynomial remainder sequences. , 14(1):128\U142, 1967. A.CuytW.-S.Lee. Sparse interpolation of multivariate rational functions. , 412:1445\U1456, 2011. W.Decker, G.LecerfG.Pfister. Absolute factorization for characteristic . Singular library , 2005. J.Della Dora, C.DicrescenzoD.Duval. A new method for computing in algebraic number fields. , 174, 321\U326. Springer, 1985. M.Filaseta, A.GranvilleA.Schinzel. Irreducibility and greatest common divisor algorithms for sparse polynomials. , 352:155\U176, 2008. D.Ford. . , Ohio State University, 1978. A.FröhlichJ.C.Shepherdson. On the factorisation of polynomials in a finite number of steps. , 62:331\U334, 1955. A.FröhlichJ.C.Shepherdson. Effective procedures in field theory. , 248:407\U432, 1956. S.Gao. Factoring multivariate polynomials via partial differential equations. , 72(242):801\U822, 2003. J.vonzur Gathen. Irreducibility of multivariate polynomials. , 31:225\U264, 1985. J.vonzur GathenJ.Gerhard. . Cambridge University Press, New York, NY, USA, 3rd, 2013. J.vonzur GathenE.Kaltofen. Factoring sparse multivariate polynomials. , 31(2):265\U287, 1983. Proc. FOCS. J.vonzur GathenE.Kaltofen. Factorization of multivariate polynomials over finite fields. , 45(171):251\U261, 1985. P.GianniB.Trager. Square-free algorithms in positive characteristic. , 7(1):1\U14, 1996. M.GiesbrechtD.S.Roche. Diversification improves interpolation. , 123\U130. New York, NY, USA, 2011. ACM. B.Grenet. Bounded-degree factors of lacunary multivariate polynomials. , 75:171\U192, 2016. B.Grenet, J.vander HoevenG.Lecerf. Randomized root finding over finite fields using tangent Graeffe transforms. , 197\U204. New York, NY, USA, 2015. ACM. J.Guàrdia, J.MontesE.Nart. Newton polygons of higher order in algebraic number theory. , 364(1):361\U416, 2012. Jr.H. W. Lenstra. Finding small degree factors of lacunary polynomials. , 1, 267\U276. De Gruyter, Zakopane-Ko±cielisko, 1999. D.HarveyJ.vander Hoeven. Polynomial multiplication over finite fields in time >. , HAL, 2019. . K.Hensel. Neue Grundlagen der Arithmetik. , 127:51\U84, 1904. D.Hilbert. Über die Irreducibilität ganzer rationaler Functionen mit ganzzahligen Coefficienten. , 110:104\U129, 1892. M.van Hoeij. Factoring polynomials and the knapsack problem. , 95(2):167\U189, 2002. J.vander Hoeven. Faster Chinese remaindering. , HAL, 2016. . J.vander Hoeven. Probably faster multiplication of sparse polynomials. , HAL, 2020. . J.vander Hoeven. . Scypress, 2020. J.vander HoevenG.Lecerf. On the bit-complexity of sparse polynomial multiplication. , 50:227\U254, 2013. J.vander HoevenG.Lecerf. Sparse polynomial interpolation. Exploring fast heuristic algorithms over finite fields. , HAL, 2019. . J.vander HoevenG.Lecerf. Directed evaluation. of Complexity>, 60, 2020. Article ID 101498. J.vander HoevenG.Lecerf. Fast multivariate multi-point evaluation revisited. of Complexity>, 56, 2020. Article ID 101405, 38 pages. J.vander HoevenG.Lecerf. On sparse interpolation of rational functions and gcds. , 55(1):1\U12, 2021. J.vander HoevenG.Lecerf. Approximate contact factorization of germs of plane curves. , HAL, 2022. . J.vander HoevenG.Lecerf. Univariate polynomial factorization over large finite fields. , 2022. . J.HuM.B.Monagan. A fast parallel sparse polynomial GCD algorithm. S.A.Abramov, E.V.ZimaX.-S.Gao, , 271\U278. ACM, 2016. Q.-L.HuangX.-S.Gao. Bit complexity of polynomial gcd on sparse representation. Preprint available from , 2022. M.JavadiM.Monagan. A sparse modular gcd algorithm for polynomial gcd computation over algebraic function fields. , 187\U194. 2007. E.Kaltofen. A polynomial reduction from multivariate to bivariate integral polynomial factorization. , 261\U266. ACM, 1982. E.Kaltofen. Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. , 14(2):469\U489, 1985. E.Kaltofen. Sparse Hensel lifting. , 4\U17. Berlin, Heidelberg, 1985. Springer. E.Kaltofen. Factorization of polynomials given by straight-line programs. S.Micali, , 5, 375\U412. JAI Press Inc., Greenwhich, Connecticut, 1989. E.Kaltofen. Effective noether irreducibility forms and applications. , 50(2):274\U295, 1995. E.KaltofenG.Lecerf. , Factorization of multivariate polynomials, 383\U392. Discrete Mathematics and its Applications. Chapman and Hall/CRC, 2013. E.KaltofenM.B.Monagan. On the genericity of the modular polynomial gcd algorithm. , 59\U66. 1999. E.KaltofenV.Shoup. Subquadratic-time factoring of polynomials over finite fields. , 67(223):1179\U1197, 1998. E.KaltofenB.M.Trager. Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators. , 9(3):301\U320, 1990. E.KaltofenL.Yagati. Improved sparse multivariate polynomial interpolation algorithms. , 467\U474. Springer Verlag, 1988. K.S.KedlayaC.Umans. Fast polynomial factorization and modular composition. , 40(6):1767\U1802, 2011. G.Lecerf. Sharp precision in Hensel lifting for bivariate polynomial factorization. , 75:921\U933, 2006. G.Lecerf. Improved dense multivariate polynomial factorization algorithms. , 42(4):477\U494, 2007. G.Lecerf. Fast separable factorization and applications. , 19(2), 2008. G.Lecerf. New recombination algorithms for bivariate polynomial factorization based on Hensel lifting. , 21(2):151\U176, 2010. G.Lecerf. , 3, Factorisation des polynômes à plusieurs variables. \ CEDRAM, 2013. Exp. No. 2, 85 pages, . G.Lecerf. On the complexity of the Lickteig\URoy subresultant algorithm. , 92:243\U268, 2019. A.K.Lenstra, H.W.LenstraL.Lovász. Factoring polynomials with rational coefficients. , 261:515\U534, 1982. M.MonaganB.Tuncer. Using sparse interpolation in Hensel lifting. , 9890, 381\U400. Springer, 2016. M.MonaganB.Tuncer. Factoring multivariate polynomials with many factors and huge coefficients. , 319\U334. Cham, 2018. Springer International Publishing. M.MonaganB.Tuncer. Sparse multivariate Hensel lifting: a high-performance design and implementation. , 10931, 359\U368. Springer, 2018. M.MonaganB.Tuncer. The complexity of sparse Hensel lifting and sparse polynomial factorization. , 99:189\U230, 2020. J.Montes. . , Universitat de Barcelona, Spain, 1999. G.Moroz. New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems. . Denver, United States, 2022. D.R.Musser. Multivariate polynomial factorization. , 22(2):291\U308, 1975. A.Novocin. . , Florida State University at Tallahassee, 2008. A.Novocin, D.StehléG.Villard. An LLL-Reduction algorithm with quasi-linear time complexity: extended abstract. , 403\U412. New York, NY, USA, 2011. V.Y.Pan. Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding. , 33(5):701\U733, 2002. C.H.Papadimitriou. . Addison-Wesley, 1994. D.A.Plaisted. Sparse complex polynomials and polynomial reducibility. , 14(2):210\U221, 1977. D.A.Plaisted. New NP-hard and NP-complete polynomial and integer divisibility problems. , 31(1-2):125\U138, 1984. R.Prony. Essai expérimental et analytique sur les lois de la dilatabilité des fluides élastiques et sur celles de la force expansive de la vapeur de l'eau et de la vapeur de l'alkool, à différentes températures. , 1:24\U76, 1795. Cahier 22. D.S.Roche. What can (and can't) we do with sparse polynomials? , 25\U30. New York, NY, USA, 2018. ACM. W.M.Ruppert. Reduzibilität ebener kurven. , 396:167\U191, 1986. K.RyanN.Heninger. Fast practical lattice reduction through iterated compression. , 3\U36. 2023. T.SasakiM.Sasaki. A unified method for multivariate polynomial factorizations. , 10(1):21\U39, 1993. N.Saxena. Closure of algebraic classes under factoring. , 2023. Talk at Recent Trends in Computer Algebra, Institut Henri Poincar\Ae, Paris. Th.Schönemann. Von denjenigen Moduln, welche Potenzen von Primzahlen sind. , 32:93\U105, 1846. See Ÿ59. A.Schönhage. Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients. J.Calmet, , 144, 3\U15. Marseille, France, April 1982. Springer. J.T.Schwartz. Fast probabilistic algorithms for verification of polynomial identities. , 27(4):701\U717, 1980. I.R.Shafarevich. . Springer, 3rd, 2013. V.Shoup. On the deterministic complexity of factoring polynomials over finite fields. , 261\U267, 1990. A.Steel. Conquering inseparability: primary decomposition and multivariate factorization over algebraic function fields of positive characteristic. , 40(3):1053\U1075, 2005. P.S.Wang. An improved multivariate polynomial factoring algorithm. , 32(144):1215\U1231, 1978. P.S.WangL.P.Rothschild. Factoring multivariate polynomials over the integers. , 29:935\U950, 1975. W.Wu, J.ChenY.Feng. Sparse bivariate polynomial factorization. , 57:2123\U2142, 2014. D.Y.Y.Yun. On square-free decomposition algorithms. , 26\U35. New York, NY, USA, 1976. ACM. H.Zassenhaus. On Hensel factorization, I. , 1(3):291\U311, 1969. R.Zippel. Probabilistic algorithms for sparse polynomials. , 216\U226. Springer, 1979. R.Zippel. Newton's iteration and the sparse Hensel algorithm (extended abstract). , 68\U72. New York, NY, USA, 1981. ACM. <\initial> <\collection> <\attachments> <\collection> <\associate|bib-bibliography> <\db-entry|+byKiFsUoTc7rBN|book|TeXmacs:vdH:book> <|db-entry> > <\db-entry|+qYhUkmR1lNMNvDT|article|vdH:sparsemult> <|db-entry> G. > <\db-entry|+1Hcl3U922Lc9q617|techreport|vdH:smul> <|db-entry> > > <\db-entry|+2GwKI2cC86Ig9ZI|article|vdH:sparserat> <|db-entry> G. > <\db-entry|+avB8kUtjRqVwSk|article|Pro1795> <|db-entry> > <\db-entry|+tw6KmG8XaVvRd|inproceedings|BenOrTiwari1988> <|db-entry> P. > <\db-entry|+qYhUkmR1lNMNv8R|inproceedings|Roche2018> <|db-entry> > <\db-entry|+tgCudvXqpzK6MJ|techreport|vdH:ffsparse> <|db-entry> G. > > <\db-entry|+1R5bwURZ1ScJxO5R|article|FS55> <|db-entry> J. C. > <\db-entry|+1R5bwURZ1ScJxO5S|article|FS56> <|db-entry> J. C. > <\db-entry|+1R5bwURZ1ScJxO62|article|Kaltofen85c> <|db-entry> > <\db-entry|+5FGQuqJ12ZAM1yH|article|Shoup90b> <|db-entry> > <\db-entry|+qYhUkmR1lNMNv4E|article|Lecerf2005> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO5P|article|Ber67> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO5Q|article|Ber70> <|db-entry> > <\db-entry|+qYhUkmR1lNMNuxX|article|CZ81> <|db-entry> H. > <\db-entry|+1R5bwURZ1ScJxO5T|article|KaltofenShoup1998> <|db-entry> V. > <\db-entry|+qYhUkmR1lNMNv3d|article|KU11> <|db-entry> C. > <\db-entry|+tw6KmG8XaVvRw|article|vdH:fffact> <|db-entry> G. > > <\db-entry|+qYhUkmR1lNMNuzt|book|GaGe13> <|db-entry> J. > <\db-entry|+5GSB9Vt1G7EHUle|inbook|KL13> <|db-entry> G. > D. > <\db-entry|+qYhUkmR1lNMNv8x|inproceedings|Sch82> <|db-entry> > > <\db-entry|+qYhUkmR1lNMNv74|article|Pan02> <|db-entry> > <\db-entry|+tw6KmG8XaVvRo|inproceedings|Mor22> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO5v|article|Schoenemann1846b> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO5K|article|Hensel04> <|db-entry> > <\db-entry|+1vfQiuSpDgyfKH|article|Zass69> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO5Y|phdthesis|Ford:phd> <|db-entry> > <\db-entry|+1tmOncbh1W9AYK08|inproceedings|Chistov1991> <|db-entry> > <\db-entry|+1lPhDapp2g8VYQc|phdthesis|Montes1999> <|db-entry> > <\db-entry|+1tmOncbh1W9AYK0G|article|GuardiaMontesNart2012> <|db-entry> J. E. > <\db-entry|+xziFYxu1hQbbSvQ|techreport|CarraminanaGuàrdiaNartPoteauxWeimann2022> <|db-entry> J. E. A. J. M. > > <\db-entry|+qYhUkmR1lNMNv4a|article|LLL82> <|db-entry> H. W. L. > <\db-entry|+22jpwSM91FqWXyZQ|article|vH02> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO5U|article|BHKS09> <|db-entry> M. van J. A. > <\db-entry|+1R5bwURZ1ScJxO5V|phdthesis|Nov:phd> <|db-entry> > <\db-entry|+1CQ02y1d169CJ0py|inproceedings|NSV11> <|db-entry> D. G. > <\db-entry|+1R5bwURZ1ScJxO5W|inproceedings|RH23> <|db-entry> N. > <\db-entry|+qYhUkmR1lNMNv01|article|Gao2003> <|db-entry> > <\db-entry|+qYhUkmR1lNMNv4C|article|Lecerf:2004:bivfact> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO6N|article|Lecerf2010> <|db-entry> > > <\db-entry|+1R5bwURZ1ScJxO5t|article|Rup86> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO5x|article|SS93> <|db-entry> M. > <\db-entry|+1R5bwURZ1ScJxO6C|article|Musser75> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO60|article|WangRothschild75> <|db-entry> L. P. > <\db-entry|+1R5bwURZ1ScJxO5M|article|Wang78> <|db-entry> > <\db-entry|+1sCAaiJh150ukTMw|inproceedings|Zippel81> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO61|inproceedings|Kaltofen82> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO5n|article|GK83> <|db-entry> E. > <\db-entry|+1R5bwURZ1ScJxO5o|article|GK85> <|db-entry> E. > <\db-entry|+1sCAaiJh150ukTMt|inproceedings|Kaltofen85> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO5j|phdthesis|Bernardin:phd> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO5f|inproceedings|MT18> <|db-entry> B. > <\db-entry|+1sCAaiJh150ukTMq|article|MonaganTuncer20> <|db-entry> B. > <\db-entry|+1R5bwURZ1ScJxO5d|inproceedings|MonaganChen20> <|db-entry> M. > <\db-entry|+1R5bwURZ1ScJxO5p|article|Hilbert1892> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO5k|book|Bertini1923> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO5Z|inbook|Lecerf:jncf> <|db-entry> > > <\db-entry|+tcmXoQxjJnaZvi|book|Shafarevich2013> <|db-entry> > <\db-entry|+qYhUkmR1lNMNuua|book|BCS97> <|db-entry> M. M. A. > <\db-entry|+1R5bwURZ1ScJxO67|incollection|Kaltofen89> <|db-entry> > > <\db-entry|+1ZAGXYG4238WXVut|article|KaltofenTrager1990> <|db-entry> B. M. > <\db-entry|+1R5bwURZ1ScJxO64|article|Gathen85> <|db-entry> > <\db-entry|+1sCAaiJh150ukTMp|article|MonaganChen22> <|db-entry> M. > <\db-entry|+1sCAaiJh150ukTMr|inproceedings|MonaganTuncer18> <|db-entry> B. > <\db-entry|+1R5bwURZ1ScJxO5e|inproceedings|MT16> <|db-entry> B. > <\db-entry|+1R5bwURZ1ScJxO6A|incollection|Lenstra99> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO65|article|Grenet16> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO6D|misc|Saxena23> <|db-entry> > > <\db-entry|+1R5bwURZ1ScJxO63|article|Col67> <|db-entry> > <\db-entry|+qYhUkmR1lNMNvBt|inproceedings|Zip79> <|db-entry> > <\db-entry|+1R5bwURZ1ScJxO68|inproceedings|KaltofenMonagan99> <|db-entry> M. B. > <\db-entry|+1R5bwURZ1ScJxO6H|inproceedings|JaMo07> <|db-entry> M. > <\db-entry|+qYhUkmR1lNMNux8|article|CL11> <|db-entry> W.-S. > <\db-entry|+qYhUkmR1lNMNv23|inproceedings|HM16> <|db-entry> M. B. > E. V. X.-S. > <\db-entry|+1R5bwURZ1ScJxO6O|article|Lecerf19> <|db-entry> > <\db-entry|+17kjZR2z7yOyhjI|unpublished|HuangGao22> <|db-entry> X.-S. > > <\db-entry|+1R5bwURZ1ScJxO66|article|GT96> <|db-entry> B. > <\db-entry|+1R5bwURZ1ScJxO6E|article|Steel05> <|db-entry> > <\db-entry|+qYhUkmR1lNMNv4F|article|Lecerf:2007:fsfa> <|db-entry> > <\db-entry|+5FGQuqJ12ZAM1xp|article|Kaltofen1995> <|db-entry> > <\db-entry|+avB8kUtjRqVwSP|article|ChLe:2005:lrtaf> <|db-entry> G. > of Complexity> <\db-entry|+5FGQuqJ12ZAM1xJ|misc|Absfact2005> <|db-entry> G. G. > > > <\db-entry|+haC4GcdToVz5Fy|inproceedings|DDD85> <|db-entry> C. D. > <\db-entry|+MeJq26v1bFbPi2k|article|vdH:direval> <|db-entry> G. > of Complexity> <\db-entry|+1sCAaiJh150ukTMs|inproceedings|AGL04> <|db-entry> S. A. G. B. > <\db-entry|+1sCAaiJh150ukTMv|article|WCF14> <|db-entry> J. Y. > <\db-entry|+qYhUkmR1lNMNuwz|article|CK91> <|db-entry> E. > <\db-entry|+2MmazzPzwkzLNWc|techreport|vdH:ffnlogn> <|db-entry> J. van der > >> > <\db-entry|+qYhUkmR1lNMNv77|book|Pap94> <|db-entry> > <\db-entry|+qYhUkmR1lNMNuva|article|BM74> <|db-entry> R. T. > <\db-entry|+hBZGeaDhNIZyGe|inproceedings|KaltofenYagati1988> <|db-entry> L. > <\db-entry|+1CQ02y1d169CJ0pZ|inproceedings|BoLeSc2003> <|db-entry> G. É. > <\db-entry|+22jpwSM91FqWXyZ3|misc|Bern04> <|db-entry> > > <\db-entry|+1Hcl3U922Lc9q60c|techreport|vdH:chinese> <|db-entry> > > <\db-entry|+1CQ02y1d169CJ0qE|article|vdH:kucomp> <|db-entry> G. > of Complexity> <\db-entry|+tw6KmG8XaVvS5|article|Schw80> <|db-entry> > <\db-entry|+qYhUkmR1lNMNvEW|inproceedings|vdH:rmodroots> <|db-entry> J. van der G. > <\db-entry|+qYhUkmR1lNMNv0n|inproceedings|GR11> <|db-entry> D. S. > <\db-entry|+qYhUkmR1lNMNutw|article|ASU75> <|db-entry> K. J. D. > <\db-entry|+1CQ02y1d169CJ0pb|article|BS05> <|db-entry> É. > of Complexity> <\db-entry|+6WngoxZOt05dLS|inproceedings|Yun76> <|db-entry> > <\db-entry|+DvVv4ff1EWHR2|article|Plaisted77> <|db-entry> > <\db-entry|+DvVv4ff1EWHR3|article|Plaisted84> <|db-entry> > <\db-entry|+DvVv4ff1EWHR4|article|FMG08> <|db-entry> A. A. > <\db-entry|+MeJq26v1bFbPi2l|techreport|vdH:pfact> <|db-entry> G. > > <\references> <\collection> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|bib> TeXmacs:vdH:book vdH:sparsemult vdH:smul vdH:sparserat Pro1795 BenOrTiwari1988 Roche2018 vdH:ffsparse vdH:smul Kaltofen85c Shoup90b Lecerf2005 FS55 FS56 Ber67 Ber70 CZ81 KaltofenShoup1998 KU11 vdH:fffact GaGe13 KL13 Sch82 Pan02 Mor22 Schoenemann1846b Hensel04 Zass69 Ford:phd Chistov1991 Montes1999 GuardiaMontesNart2012 CarraminanaGuàrdiaNartPoteauxWeimann2022 LLL82 vH02 BHKS09 Nov:phd NSV11 RH23 Gao2003 Lecerf:2004:bivfact BHKS09 Lecerf2010 Rup86 SS93 Musser75 WangRothschild75 Wang78 Zippel81 Kaltofen82 GK83 GK85 Kaltofen85 Kaltofen85c Bernardin:phd Lecerf2005 MT18 MonaganTuncer20 MonaganChen20 Hilbert1892 Bertini1923 Lecerf2010 Lecerf:jncf Shafarevich2013 Kaltofen82 Lecerf2005 BCS97 Kaltofen89 KaltofenTrager1990 Gathen85 MonaganChen20 MonaganChen22 GK83 Bernardin:phd MonaganTuncer18 MonaganTuncer20 Kaltofen85 Bernardin:phd MT16 MT18 MonaganTuncer20 MonaganChen20 Lenstra99 Grenet16 Saxena23 GaGe13 Col67 Zip79 KaltofenTrager1990 KaltofenMonagan99 JaMo07 CL11 HM16 Lecerf19 vdH:sparserat HuangGao22 GT96 Steel05 Lecerf:2007:fsfa KL13 Kaltofen1995 ChLe:2005:lrtaf Absfact2005 DDD85 vdH:direval vdH:sparserat AGL04 WCF14 BCS97 BCS97 CK91 vdH:ffnlogn Pap94 GaGe13 GaGe13 BM74 KaltofenYagati1988 BoLeSc2003 Bern04 vdH:chinese vdH:chinese CZ81 KU11 vdH:kucomp vdH:fffact Schw80 Zip79 Pro1795 BenOrTiwari1988 vdH:rmodroots vdH:ffsparse vdH:smul GR11 vdH:smul vdH:ffsparse vdH:sparserat vdH:sparserat MonaganTuncer18 ASU75 ASU75 BS05 GaGe13 GaGe13 GaGe13 GaGe13 ASU75 Yun76 GaGe13 Lecerf2010 Lecerf2010 Yun76 GaGe13 Plaisted77 Plaisted84 FMG08 FMG08 GaGe13 Lecerf2010 Shafarevich2013 Lecerf2010 Lecerf:jncf vdH:pfact vdH:pfact Lecerf2005 Lecerf:jncf Lecerf:jncf ASU75 <\associate|toc> |math-font-series||font-shape||1.Introduction> |.>>>>|> |1.1.Motivation and main goals |.>>>>|> > |1.2.Overview of univariate and bivariate factorization methods |.>>>>|> > |1.3.Overview of multivariate factorization methods |.>>>>|> > |1.4.Outline of our contributions |.>>>>|> > |1.5.Notation |.>>>>|> > |math-font-series||font-shape||2.Preliminaries> |.>>>>|> |2.1.Basic complexities |.>>>>|> > |2.2.The Schwarz\UZippel lemma |.>>>>|> > |2.3.Sparse polynomial interpolation |.>>>>|> > |2.4.Sparse evaluation at geometric progressions |.>>>>|> > |2.5.Newton polytopes |.>>>>|> > |2.6.Laurent polynomials |.>>>>|> > |2.7.Tagging |.>>>>|> > |math-font-series||font-shape||3.Multivariate gcd computations> |.>>>>|> |3.1.Iterative computation of gcds |.>>>>|> > |3.2.Gcd computations through regularizing weights |.>>>>|> > |math-font-series||font-shape||4.Bivariate factorization> |.>>>>|> |4.1.Content-free factorization |.>>>>|> > |4.2.Root extraction |.>>>>|> > |4.3.Hensel lifting |.>>>>|> > |4.4.Square-free factorization |.>>>>|> > |4.5.General bivariate factorization |.>>>>|> > |math-font-series||font-shape||5.Efficient reductions> |.>>>>|> |5.1.Content-free factorization |.>>>>|> > |5.2.Root extraction |.>>>>|> > |5.3.Square-free factorization |.>>>>|> > |5.4.A pathological example |.>>>>|> > |math-font-series||font-shape||6.Factoring using iterated Hensel lifting> |.>>>>|> |6.1.Faithful projections |.>>>>|> > |6.2.Lifting a coprime decomposition into two factors |.>>>>|> > |6.3.Simultaneous lifting of multiple factors |.>>>>|> > |6.4.Irreducible factorization |.>>>>|> > |math-font-series||font-shape||7.Factoring using projective Hensel lifting> |.>>>>|> |7.1.A favorable special case |.>>>>|> > |7.2.Single slope bivariate Hensel lifting |.>>>>|> > |7.3.Single slope factorization |.>>>>|> > |7.4.Multiple slope bivariate Hensel lifting |.>>>>|> > |7.5.Multiple slope factorization |.>>>>|> > |7.6.A torture example |.>>>>|> > |7.7.Factor matching through homotopies |.>>>>|> > |math-font-series||font-shape||Bibliography> |.>>>>|>