> <\body> over large finite fields>|>|<\doc-note> This paper is part of a project that has received funding from the French \PAgence de l'innovation de défense\Q. ||<\author-affiliation> CNRS, École polytechnique, Institut Polytechnique de Paris Laboratoire d'informatique de l'École polytechnique (LIX, UMR 7161) 1, rue Honoré d'Estienne d'Orves Bâtiment Alan Turing, CS35003 91120 Palaiseau, France > \; >>||<\author-affiliation> CNRS, École polytechnique, Institut Polytechnique de Paris Laboratoire d'informatique de l'École polytechnique (LIX, UMR 7161) 1, rue Honoré d'Estienne d'Orves Bâtiment Alan Turing, CS35003 91120 Palaiseau, France |>>||<\doc-note> > The best known asymptotic bit complexity bound for factoring univariate polynomials over finite fields grows with the input degree to a power close to , and with the square of the bitsize of the ground field. It relies on a variant of the Cantor\UZassenhaus algorithm which exploits fast modular composition. Using techniques by Kaltofen and Shoup, we prove a refinement of this bound when the finite field has a large extension degree over its prime field. We also present fast practical algorithms for the case when the extension degree is smooth. > The usual of the finite field > with >> elements is /|)>>> with prime and \\> irreducible and monic of degree\1>. For this representation, von zur Gathen, Kaltofen, and Shoup proposed several efficient algorithms for the irreducible factorization of a polynomial of degree in >. One of them is a variant of the Cantor\UZassenhaus method for which large powers of polynomials modulo are computed using modular composition2>. Now Kedlaya and Umans designed a theoretically efficient algorithm for modular composition>. Consequently, using a probabilistic algorithm of Las Vegas type, the polynomial can be factored in expected time <\equation> d>*log> q+ q|)>. It turns out that the second term of is suboptimal when becomes large. The purpose of the present paper is to prove the expected complexity bound <\equation*> >+\|)>>+log p|)>*, where =O|)>|)>>; see Corollary. For this, we rely on ideas by Kaltofen and Shoup from. In addition, we present improved complexity bounds for the case when the extension degree > is smooth. These bounds rely on practically efficient algorithms for modular composition that were designed for this case in. Given a commutative ring > and \>, let d>\\:deg f\d|}>>. Given \>, we define |x|\>\max \\n\x|}>> and |x|\>\min \\n\x|}>>. For any positive integer, we set <\equation*> lg n\|log n|\>, so that 2|log n|\>>>\n>. We will freely use the notation: =|)>> means that =g*|)>>>>, as in. Until section, we assume the standard complexity model of a Turing machine with a sufficiently large number of tapes. For probabilistic algorithms, the Turing machine is assumed to provide an instruction for writing a \Prandom bit\Q to one of the tapes. This instruction takes a constant time. All probabilistic algorithms in this paper are of Las Vegas type; this guarantees that all computed results are correct, but the execution time is a random variable. Until section we consider >, whose internal representations are not necessarily prescribed, and we rely on the following assumptions and notations: <\itemize> Additions and subtractions in > take linear time. >> denotes an upper bound for the bit complexity of polynomial products in degree d> over >. It is convenient to make the regularity assumptions that >/d> is nondecreasing as a function of and that >=O>|)>> for >. >> upper bounds the time needed to invert one element in >. >> is an upper bound for the time to compute \g mod h> for \d>> and monic \> of degree . >> is an upper bound for the time to compute \g,\,f\g> modulo> for ,\,f,g\\d>> and monic \> of degree . >>> is an upper bound for the time to compute >>, given \> and ,2>|}>>. For general algorithms for finite fields, we recommend the textbooks and more specifically14>, as well as for historical references. In this paper we adopt the asymptotic complexity point of view, while allowing for randomized algorithms of Las Vegas type. Early theoretical and practical complexity bounds for factorizing polynomials over finite fields go back to the sixties. In the eighties, Cantor and Zassenhaus popularized distinct-degree and equal-degree factorizations. Improved complexity bounds and fast implementations were explored by Shoup. He and von zur Gathen introduced the iterated Frobenius technique and the \Pbaby-step giant-step\Q for the distinct degree factorization. They reached softly quadratic time in the degree via fast multi-point evaluation. Together with Kaltofen, they also showed how to exploit modular composition and proved sub-quadratic complexity bounds. In 2008, Kedlaya and Umans showed that the complexity exponent of modular composition over finite fields is arbitrarily close to one. As a corollary, the complexity exponent of polynomial factorization in the degree is arbitrarily close to . Von zur Gathen and Seroussi showed that factoring quadratic polynomials with arithmetic circuits or straight-line programs over > requires > operations in >. However, this does not provide a lower bound q|)>> for boolean arithmetic circuits. In fact, subquadratic upper bounds indeed exist for the stronger model of arithmetic circuits over the prime subfield > of >: the combination of3> and fast modular composition from allows for degree factorization in > in expectedtime <\equation*> |)>>+log p|)>**log p|)>. This bound is indeed subquadratic and even quasi-optimal in >. In this paper, we also achieve a subquadratic dependence on . In order to save modular compositions, Rabin introduced a randomization process that uses random shifts of the variable. This turns out to be useful in practice, especially when the ground field > is sufficiently large. We briefly revisit this strategy, following Ben-Or and14.17>. Unfortunately, Kedlaya and Umans' fast algorithm for modular composition has not yet given rise to fast practical implementations. In, we have developed alternative algorithms for modular composition which are of practical interest when the extension degree > of > over > is composite or smooth. In section, we study the application of these algorithms to polynomial factorization. The probabilistic arguments that are used to derive the above complexity bounds become easier when ignoring all hidden constants in the \P\Q. Sharper bounds can be obtained by refining the probability analyses; we refer to for details. In this paper we heavily rely on known techniques and results on polynomial factorization (by von zur Gathen, Kaltofen, Shoup, among others) and modular composition (by Kedlaya, Umans, among others). Through a new combination of these results, our main aim is to sharpen the complexity bounds for polynomial factorization and irreducibility testing over finite fields. The improved bounds are most interesting when factoring over a field > with a large and smooth extension degree > over its prime field >. Let us briefly mention a few technical novelties. Our finite field framework is designed to support a fine grained complexity analysis for specific modular composition algorithms, for sharing such compositions, and for computing factors up to a given degree. We explicitly show how complexities depend on the degrees of the irreducible factors to be computed. Compared to the algorithm of Kaltofen and Shoup, our Algorithm for equal-degree factorization successively computes pseudotraces over > and then over >. The computation of Frobenius maps is accelerated through improved caching. Our approach also combines a bit better with Rabin's randomization; see section. We further indicate opportunities to exploit shared arguments between several modular compositions, by expressing our complexity bounds in terms of >> instead of>>, when possible. We clearly have >\N*>>, but better bounds might be achievable through precomputations based on the shared arguments. We refer to> for partial evidence in this direction under suitable genericity assumptions. Our main complexity bounds are stated in section. The remainder of the paper is devoted to corollaries of these bounds for special cases. In section, we start with some theoretical consequences that rely on the Kedlaya\UUmans algorithm for modular composition and variants from. We both consider the case when > is presented as a primitive extension of > and the case when =\>, where =\\\\\=\> is a\Ptriangular tower\Q. At the time being, it seems unlikely that Kedlaya and Umans' algorithm can be implemented in a way that makes it efficient for practical purposes; see. In our final section, we consider a more practical alternative approach to modular composition, which requires the extension degree > to be composite, and which is most efficient when > is smooth. We present new complexity bounds for this case, which we expect to be of practical interest when > becomes large. The central ingredient to fast polynomial factorization is the efficient evaluation of Frobenius maps. Besides the absolute Frobenius map \\;a\a> of > over its prime field>, we will consider pseudo-Frobenius maps. Consider an extension \\/|)>>, where \> is monic of degree and not necessarily irreducible. The >-linear map a> is called the of >. The map a> is called the of>; it is only >-linear. Recall that >> and consider a primitive representation \\/|)>> for >. Let us show how to evaluate iterated Frobenius maps a>> of > using modular composition. We introduce the auxiliary sequence <\equation*> \>\|)>i\lg \> where <\eqnarray*> >|>|>> mod \,i=0,\,lg \.>>>> The sequence >> enables us to efficiently compute >>-th powers and then general >th powers, as follows: <\lemma> Let >> be given. For all \\\>> and i\lg \>, we have <\eqnarray*> >> mod \>||\\ mod \.>>>> In particular, <\eqnarray*> >>>||>|)>+O.>>>> <\proof> We verify that <\equation*> a\\ mod \=a\z>> mod \ and that <\equation*> a\z>>=a>>|)>=a>>. The cost analysis is straightforward from the definitions. The cost function >>> corresponds to the time needed to iterate the absolute Frobenius map a> a number of times that is a power of two. For an arbitrary number of iterations we may use the following general lemma. <\lemma> For all \> and ,\-1|}>>> with binary expansion >+\+2>> with \\\i>, we have <\eqnarray*> >>||>>>|)>>>>|)>>|)>>>>.>>>> In particular, computing >> takes >>*log \|)>> operations. <\proof> The proof is straightforward since |)>>. The computation of >> can be done efficiently with the following algorithm. <\specified-algorithm> <\description> \\/|)>>. >=|)>i\lg \>>. <|specified-algorithm> <\enumerate> Compute \z mod \> using binary powering. For ,lg \>, compute > as \\ mod \>. Return |)>i\lg \>>. <\lemma> Algorithm is correct and runs in time <\equation*> O>|)>*log \+>|)>*log p|)>. <\proof> We prove the correctness by induction on . For , we clearly have =z mod \>. Assume therefore that 0> and let > be such that <\equation*> \=z>>+h*\. We verify that <\eqnarray*> \\>||>>+h*\|)>\>>+h*\|)> mod \>>|||>>+h*\|)>\z>> mod \>>|||>>+*\|)>>>|)> mod \>>||| mod \.>>>> This completes the correctness proof. The first step takes time >|)>*log p|)>>, whereas the loop requires > modular compositions, whence the complexity bound. For the efficient application of the absolute pseudo-Frobenius map, we introduce the auxiliary sequence \|)>i\lg \>> with <\eqnarray*> >|>|>> mod f,i=0,\,lg \.>>>> <\lemma> Let > be given. For all =a+\+a*x\\d>> and i\lg \>, wehave <\eqnarray*> >> mod f>||a>>*x|)>\\ mod f.>>>> In particular, we may compute >> mod f> in time >+d*>>+O>. <\proof> We verify that <\eqnarray*> >> mod f>||a>>*x|)>\x>> mod f>>|||a>>*x|)>\\ mod f.>>>> The cost is straightforward from the definitions. Once > has been computed, the pseudo-Frobenius map can be iterated an arbitrary number of times, using the following variant of Lemma. <\lemma> Let > be given. For all \> and ,\|}>>> with binary expansion >+\+2>>> with \\\i>, we have <\eqnarray*> >>||>>>|)>>>>|)>>|)>>>>,>>>> that can be computed in time <\eqnarray*> ||>+d*>>|)>*log e|)>.>>>> <\proof> The proof is straightforward from Lemma. The auxiliary sequence > can be computed efficiently as follows. <\specified-algorithm> <\description> A monic polynomial \> of degree . =|)>i\lg \>>. <|specified-algorithm> <\enumerate> Compute \x mod f> using binary powering. For ,lg \-1>: <\enumerate> Write =a*x>, Compute > as a>>*x|)>\\ mod f>. Return |)>i\lg \>>. <\lemma> Algorithm is correct and runs in time <\equation*> O>+d*>>|)>*log \+>*log p|)>. <\proof> Let us prove the correctness by induction on . The result clearly holds for . Assume that it holds for a given and let > be such that =x>>+h*f>. Then <\eqnarray*> >||>> mod f>>|||>>+h>>*f>>|)> mod f>>|||>> mod f>>|||a>>*|)>>> mod f>>|||a>>*x|)>\x>> mod f.>>>> As to the complexity bound, the binary powering in step1 takes >*log p|)>> time. In step2, we compute > powers of the form >>> and we perform > modular compositions of degree d> over >. For the efficient application of the pseudo-Frobenius map, we introduce another auxiliary sequence \|)>i\lg d>> with <\eqnarray*> >|>|>> mod f,i=0,\,lg d.>>>> <\lemma> Let > be given. For all \\d>> and i\lg d>, we have <\eqnarray*> >> mod f>||\\ mod f.>>>> In particular, we may compute >> mod f> in time >+O>. <\proof> The proof is straightforward from the definitions. Once > has been computed, the pseudo-Frobenius map can be iterated an arbitrary number of times by adapting Lemma, but this will not be needed in the sequel. The sequence > can be computed efficiently as follows. <\specified-algorithm> <\description> A monic polynomial \> of degree , and >. =|)>i\lg d>>. <|specified-algorithm> <\enumerate> Compute =x mod f> using Lemma. For ,lg d>, compute =\\\ mod f>. Return |)>i\lg d>>. <\lemma> Algorithm is correct and runs in time <\equation*> O>*log|)>+d*>>*log \|)>. <\proof> The correctness is proved in a similar way as for Algorithm. Step1 takes >+d*>>|)>*log \|)>> operations, by Lemma, whereas step2 takes >*log d|)>> operations. Let >> be still as above. Recall that the trace of an element \> over >, written /\>>, is defined as <\equation*> Tr/\>=a-1>>+a-2>>+\+a+a. For a monic, not necessarily irreducible polynomial \> of degree , it is customary to consider two similar kinds of maps over /|)>>, which are called : one over > and one over >. In this section, we reformulate fast algorithms for pseudo-traces by Kaltofen and Shoup, and make them rely on the data structures from the previous section for the computation of Frobenius maps. Let \d>>. We define the of > of order 1> modulo > over > by <\equation*> Tr;q>|)> mod f\a>+\+a+a mod f. We may compute pseudo-traces using the following algorithm: <\specified-algorithm> <\description> >, \\d>>, and d>. ;q>|)> mod f>. <|specified-algorithm> <\enumerate> Let *2+e*2+\+e> be the binary expansion of . Let \a> and <\eqnarray*> >|>|+|)>>> mod f,i=1,\,l.>>>> Let \0> and <\eqnarray*> >|>|*b+|)>*2>> mod f,i=0,\,l.>>>> Return >. <\lemma> Algorithm is correct and runs in time <\equation*> O>*log e|)>. <\proof> By induction on , we verify that <\eqnarray*> >||>;q>|)> mod f>>|>||*2+\+e>;q>|)> mod f.>>>> The cost follows from Lemma. We define the of > modulo > of order by <\equation*> Tr;p>|)> mod f\a>+\+a>>+a mod f. We may compute absolute pseudo-traces using the following variant of Algorithm: <\specified-algorithm> <\description> >, \\d>>, and \>. ;p>|)> mod f>. <|specified-algorithm> <\enumerate> Let *2+e*2+\+e> be the binary expansion of . Let \a> and <\eqnarray*> >|>|+|)>>> mod f,i=1,\,l.>>>> Let \0> and <\eqnarray*> >|>|*b+|)>*2>> mod f,i=0,\,l.>>>> Return >. <\lemma> Algorithm is correct and runs in time <\equation*> O>+d*>>|)>*log e|)>. <\proof> By induction on , we have <\eqnarray*> >||>;p>|)> mod f>>|>||*2+\+e>;p>|)> mod f.>>>> The cost then follows from Lemma. We follow the Cantor\UZassenhaus strategy, which subdivides irreducible factorization in> into three consecutive steps: <\itemize> the decomposes into square-free factors along with their respective multiplicities, the separates irreducible factors according to their degree, the completely factorizes a polynomial whose irreducible factors have the same degree. For the distinct-degree factorization, we revisit the \Pbaby-step giant-step\Q algorithm due to von zur Gathen and Shoup6>, later improved by Kaltofen and ShoupD>. For the equal-degree factorization, we adapt another algorithm due to von zur Gathen and Shoup5>, while taking advantage of fast modular composition as in1>. Throughout this section, we assume that \> is the polynomial to be factored and that is monic of degree . The square-free factorization combines the separable factorization and -th root extractions. <\proposition> The square-free factorization of a monic polynomial \\> of degree takes time <\equation*> O>*log d+d*>>+d*>>*log \|)>. <\proof> Let \> and let \>. The >-th root of in > can be computed as >=a-k>>> in time >>*log \|)>> by Lemma. The separable factorization of takes time >*log d+d*>>|)>>; see. This yields <\equation*> f=f>>|)>>, where the > are monic and separable, the >>|)>> are pairwise coprime, and does not divide the>. In order to deduce the square-free factorization of it remains to extract the >>th roots of the coefficients of >, for ,r>. The cost of these extractions is bounded by <\equation*> Odeg f*>>*log \|)>=O>>*log \|)>. In this subsection is assumed to be monic and square-free. The distinct-degree factorization is a partial factorization *\*g> of where > is the product of the monic irreducible factors of of degree . The following algorithm exploits the property that >-x,f|)>> is the product of the irreducible factors of of a degree that divides. The \Pbaby-step giant-step\Q paradigm is used in order to avoid the naive computation of the > mod f> in sequence for ,d>. As a useful feature, our algorithm only computes the irreducible factors up to a given degree. <\specified-algorithm> <\description-compact> \\> monic and square-free of degree 1>, d>, >. ,\,g> such that > is the product of the irreducible factors of of degree . <|specified-algorithm> <\enumerate> Let \|D|\>>. Compute mod f> by using >. Compute > mod f> for ,\>, via modular compositions. Compute >> mod f> for ,|D/\|\>>, via modular compositions. Compute \-1>>|)> mod f>, where denotes a new variable. Compute \A>>|)> mod f> for ,|D/\|\>>. Set f>. For ,|D/\|\>> do: Compute \gcd,b|)>>, b/h>. For ,\-1>, compute > mod h> for ,|D/\|\>>. For ,|D/\|\>>, compute >> mod h> for ,|D/\|\>>. For ,|D/\|\>> do: Set h>. For from -1> down to 0 do: Compute -k>\gcd>>-x> mod h|)>>, b/g-k>>. Return ,\,g>. <\proposition> Algorithm is correct and takes time <\equation*> O>|D|\>+1|)>+D*>*log d+d*>|)>+>+d*>>|)>*log \|)>. <\proof> First note that any positive integer D> writes uniquely as -k> with k\\> and l\|D/\|\>\|D|\>+1>. Then note that <\eqnarray*> >||-1>>>-x>|)> mod f>>|||-1>-k>>-x|)>> mod f,>>>> so =g--1|)>>*\*g>> for ,>|D/\|\>>. This shows that ,\,g> are computed correctly. Lemma allows us to perform step2 in time <\equation*> O>+d*>>|)>*log \|)>. Step3 requires -1> modular compositions of the form \\ mod f> for which \x mod f> is fixed. The same holds for step 4, this time with \x>> mod f>. Consequently, steps 3 and 4 can be done in time <\equation*> O>|D|\>+1|)>|)>. For steps5 and6, we use the classical \Pdivide and conquer\Q technique based on \Psubproduct trees\Q, and Kronecker substitution for products in >; see10>. These steps then require >*d|)>*log D|)>> operations. Our assumption on >> yields >*d|)>*log D|)>=O*>*log d|)>>. Step7 incurs <\equation*> O*>*log d+D*d*>|)> operations by means of the half-gcd algorithm. By construction, the > are pairwise coprime and their product equals . Steps8 and9 take *>*log d|)>> operations, by applying the fast multi-remainder algorithm10> to the results of steps3 and4. Finally, the cost of step10 is bounded by <\equation*> O|D/\|\>>D*>|)>*log|)>+deg h*>|)>|)>=O*>*log d+d*>|)>|)>. We now turn to the factorization of a polynomial \> having all its factors of the same known degree >. This stage involves randomization of Las Vegas type: the algorithm always returns a correct answer, but the running time is a random variable. <\specified-algorithm> <\description-compact> A monic, square-free polynomial \\> of degree , which is the product of> irreducible factors of degree >, as well as > and >. The irreducible factors of . <|specified-algorithm> <\enumerate> If > then return . Otherwise set \> if 2>, or \> if .\ Take at random in d>>. Compute \Tr>;q> mod f> by Algorithm. Compute \Tr>;p>|)> mod f> by Algorithm. If 2>, then compute h> mod f>. Otherwise, set h>. Compute \gcd>, \gcd>,h-1|)>>, and \f/*f|)>> if 2>. Compute |)>> as mod f>, |)>> as the |)>+1> first entries of mod f>, for \>. For \> call recursively the algorithm with input >, |)>> and |)>>. Return the union of the irreducible factors of > for \>. <\proposition> Algorithm is correct and takes expected time <\equation> O>*log*\|)>+>*log*p|)>+d*>+d*>>*log \|)>*log|)>|)>. <\proof> The proof is well known. For completeness, we repeat the main arguments. Let ,\,\> with d/\> be the irreducible factors of . The Chinese remainder theorem yields an isomorphism <\equation*> \:\/\\/|)>\\\\/|)>, where each /|)>> is isomorphic to >>>. For any in >, let <\equation*> mod \,\,g mod \|)>\\. Now <\equation*> \ mod f|)>=\>;q> mod f|)>=>>/\>|)> mod \,\,Tr>>/\>|)> mod \|)> and <\eqnarray*> mod f|)>>||/\>>>/\>|)> mod \|)>,\,Tr/\>>>/\>|)> mod \|)>|)>>>|||>>/\> mod \|)>,\,Tr>>/\> mod \|)>|)>,>>>> where each >>/\> mod \|)>> belongs to > regarded as the prime subfield of /|)>>>. Hence > is a vector ,\,b|)>> in >, and > is the product of the> with =\>, for \\>. Let ,r|}>> be a fixed index. If 2>, then the probability that =0> is , the probability that =-1> is />, and the probability that =1> is />. If , then the probability that =0> is , the probability that =1> is . We now apply4.1(i)> with =|\|>> and . This lemma concerns the probability analysis of a game of balls and bins where the bins are > for \> and the balls are the irreducible factors ,\,\> of . The lemma implies that the expected depth of the recursive calls is =O|)>|)>>. Other proofs may be found in14, Exercise14.16>, 20, section4>, or3 and4>. Step3 takes >*log \|)>> operations, by Lemma. Step4 takes >+d*>>|)>*log \|)>> operations, by Lemma. Step5 requires >*log p|)>> further operations. The rest takes >*log|)>+d*>|)>> operations. Cantor and Zassenhaus' original algorithm uses the map h>-1|2>> mod f> instead of pseudo-traces whenever 2>. For it uses a slightly different map combined with an occasional quadratic extension of >. The use of pseudo-traces appeared in early works by McEliece14>. The modern presentation is due to. Our presentation has the advantage to distinguish the pseudo-traces over > from those over>, and to avoid recomputing > and > during recursive calls. <\remark> If >=\>*log q|)>> for some \0>, then >*log*\|)>> does not need to be multiplied by |)>> in; see4.1(ii)>. We are now ready to summarize the main complexity bounds for an abstract field >, in terms of the cost functions from section. <\theorem> The computation of the irreducible factors of degree D> of a polynomial of degree in > can be done in expected time <\equation*> |||>+log|)>*log d|)>*>++log *p|)>|)>*>*log d>>|+log d|)>*d*>+d*>>*log d*log \||>.>>>>> <\proof> This bound follows by combining Lemmas and, Propositions, , and. Following14.35> from 6>, a polynomial \> of degree 1> is irreducible if, and only if, divides >-x> and >-x,f|)>=1> for all prime divisors of . This technique was previously used in over prime fields. <\theorem> A polynomial of degree in > can be tested to be irreducible in time <\equation*> O>*|)>+>* d+log p|)>+d*>*log d+d*>>*log \|)>. <\proof> Computing the prime factorization >*\*p>> takes negligible time >. On the other hand, we can compute > in time <\equation*> O>+d*>>|)>*log \+>*log p|)>, by Lemma. Then mod f> can be obtained in time <\equation*> O>+d*>>|)>*log \|)>, by Lemma. The \Pdivide and conquer\Q strategy of6.1> allows us to compute >>,\,x>>>> in time >*log d*log r|)>>; see the proof of6.2>. Finally each gcd takes >*log d+d*>|)>> operations. We finish this section with a digression on known optimizations for the equal-degree factorization algorithm that will not be used in the rest of the paper. These optimizations are based on a randomization strategy due to Rabin that saves pseudo-norm and pseudotrace computations. Here we focus on the case 2>; in the case when >, similar but slightly different formulas can be used. A concise presentation of Rabin's method is given in14.17>, but for pseudo-norms instead of pseudo-traces. For this reason, we briefly repeat the main arguments. We follow the notation of Algorithm. Assume that \> is monic and square-free of degree and a product of monic irreducible factors ,\,\> of degree =d/r>. Consider a polynomial \> such that \\> for ,r>. We say that the irreducible factors of if \h mod \> for all j>. <\specified-algorithm> <\description-compact> A monic, square-free polynomial \\> of degree , which is the product of monic irreducible factors of degree =d/r>, a polynomial \\> with \\>> for ,r>, and an integer 0>. A partial factorization of . <|specified-algorithm> <\enumerate> If > or , then return . \ Take > at random in >. Compute +\|)>> mod f>. Compute \gcd>, \gcd>,h-1|)>>, and \f/*f|)>>. For , call recursively the algorithm with input >, mod f>, and . Return the union of the factors of ,f,f> collected during step5. <\proposition> Algorithm is correct and takes time <\equation*> O>*log+d*>|)>*t|)>. In addition the following assertions hold: <\enumerate-roman> For taken at random in d>>, \Tr>;p>>;q>|)> mod f> does not separate the factors of with probability*>. If > separates the irreducible factors of , then Algorithm, called with such that \>*>, returns all the irreducible factors of with probability 1-\>. <\proof> The proof of the complexity bound is straightforward. A random yields > such that mod \=h mod \> for j> with probability >. Therefore a random > yields a polynomial > that does not separate the irreducible factors of with probability at most/p>>. That proves assertion(>). Now assume that > separates the irreducible factors of . Given j> in ,r|}>>, wehave <\equation> +\|)>> mod \=+\|)>> mod \ for at most -1> values of >. With > taken at random in >, the probability that does not hold is therefore at least >. Let > denote the probability that all the irreducible factors are not found after the call of Algorithm with input . There exist j> such that holds for random values of > with probability at most >. Considering the > possible pairs >, we obtain \/2>. We may benefit from Rabin's strategy within Algorithm as follows, whenever >*>. A polynomial > as in Proposition() separates the factors of with probability 1-\>. We call Algorithm with the first value of such that \>*>, so the irreducible factors of are found with probability 1-\>. When > and > can be taken sufficiently small, we derive a similar complexity bound as in Proposition, but where the factor |)>> does not apply to the terms >>*log \> and >*log*\|)>>, which correspond to the costs of steps3 and4 of Algorithm. If is too small to find a suitable value for >, then we may appeal to Rabin's strategy a few rounds in order to benefit from more splittings with a single pseudo-trace over>. If is actually too small for this approach, then we may consider the case >*> and apply Rabin's strategy over > instead of >. More precisely, from > and a random \\> we compute <\equation*> h\Tr>;p>+\|)> mod f, then h> mod f>, and obtain the splitting >, >, > on which to recurse. This approach yields a complexity bound similar to the one from Proposition, but where the factor |)>> does not apply to the term >*log*\|)>>. This latter term corresponds to the cost of step3 of Algorithm. This section first draws corollaries from section, which rely on Kedlaya and Umans' algorithm for modular composition. Note however that it seems unlikely that this algorithm can be implemented in a way that makes it efficient for practical purposes: see. We first consider the case when > is a primitive extension over > and then the more general case when > is given via a \Ptriangular tower\Q. Assume that \\/|)>> is a primitive extension of >. Then we may take: <\itemize> >=O*4>>|)>=>: see. Under a plausible number theoretic conjecture, one even has >=O|)>>. >=O>|)>*log \|)>=>: see. From, <\equation> >=d>*, where =o>; The refined bound with <\equation*> \=O|)>|)> is proved in6>. <\corollary> Let \\/|)>> be as above. The computation of the irreducible factors of degree D> of a polynomial of degree in > takes an expected time <\equation*> *d>+\|)>>+log p|)>*. <\proof> By means of the precomputation involved in Lemma takes <\equation*> O>|)>*log \+>|)>*log p|)>=|)>>+log p|)>*. Then >>=\|)>>*> holds by Lemma. So the bound follows from Theorem. <\corollary> Let \\/|)>> be as above. A polynomial of degree in > can be tested to be irreducible in time <\equation*> >+\|)>>+log p|)>*. <\proof> This follows fromTheorem, in a similar way as above. Now we examine the case where \\>, where |)>t>> a of height of field extensions \\> such that \\> and <\equation*> \\\|]>/|)>|)>,i=1,\,t, for irreducible polynomials \\|]>>. We write \deg \>>, so \m*\*m>, and assume that \2> for ,t>. Using1.2>, we will describe how to compute an isomorphic primitive representation of >, and how to compute the corresponding conversions. This will allow us to apply the results from section. In this subsection, we assume the boolean RAM model instead of the Turing model, in order to use the results from. <\corollary> Fix \0>. Let \\> be given as above for a triangular tower |)>t>> and assume that \>. Then the computation of the irreducible factors of degree D> of a polynomial of degree in > takes an expected time <\equation*> *d>+\>+log p|)>*. <\proof> The number of monic irreducible polynomials of degree > over > is >-2*p/2>|\>>; see for instance14.38>. Therefore the number of elements > in > that generate > is p>-2*p/2>>. The probability to pick up a generator of > over > is uniformly lower bounded, since \\2>. The assumption \> allows us to apply1.2> to the following data: <\itemize> The tower |)>t>> extended with <\equation*> \\\|]>/-\|)>, where > is an element picked up randomly in >; The \Ptarget order\Q \z\\\z>. When > generates > over > we obtain an isomorphic primitive element presentation of > of the form |]>\\/|)>>, where > denotes the defining polynomial of> over >. If > is not primitive then the algorithm underlying1.2> is able to detect it. In all cases, the time to construct |]>> is >*>. If > is primitive, then1.2> also ensures conversions between > and |]>> in time >*>. Consequently the result follows from Corollary. An alternative approach for modular composition over > was proposed in. The approach is only efficient when the extension degree > over> is composite. If > is smooth and if mild technical conditions are satisfied, then it is even quasi-optimal. It also does not rely on the Kedlaya\UUmans algorithm and we expect it to be useful in practice for large composite>. The main approach from can be applied in several ways. As in, we will first consider the most general case when > is presented via a triangular tower. In that case, it is now possible to benefit from accelerated tower arithmetic that was designed in. We next examine several types of \Pprimitive towers\Q for which additional speed-ups are possible. In order to apply the results from, all complexity bounds in this section assume the boolean RAM model instead of the Turing model. As in section, a over > is a tower of algebraic extensions <\equation*> \\\\\\\\\\\. such that > is presented as a primitive extension over >. In other words, for ,t>>, we have <\equation*> \\\|]>/|)>|)> for some monic irreducible polynomial \\|]>> of degree \2>. Alternatively, each> can be presented directly over > as a quotient ,\,x|]>/|\>,\,|\>|)>>, where |\>\\,\,x|]>> is monic of degree > in > and of degree m> in > for each i>. Triangular towers have the advantage that > is naturally embedded in > for each. We set <\equation*> >\max,\,m|)>. <\proposition> There exists a function <\equation*> \|)>=O>>|)>, such that |)>>> is a non-decreasing function of>, and <\eqnarray*> >>|||)>>*>>|>>|||)>>*.>>>> <\proof> If |2>>, then2.7 and Corollary4.11> imply <\eqnarray*> >>|||)>>*>>|>>|||)>>*.>>>> Now consider the case when |2>>. Since >\|2>> there exists a smallest integer t> such that *\*m>\|2>>, and <\equation*> l=O|)>. For any constant 1> we note that =log> \>, so 2.4 and2.7> yield <\eqnarray*> >>||*\*m*log p|)>*log> \>>|>>||*\*m*log p|)>*log> \.>>>> On the other hand, applying 2.7 and Corollary4.11> to the sub-tower <\equation*> \\\\\, we obtain <\eqnarray*> >>||*\*m|)>*\*m|)>>**\*m*>+>|)>|)>>>|||*\*m|)>*\*m|)>>**log p|)>>>||||)>>*>>|>>||>+*\*m|)>*\*m|)>>**\*m*>|)>>>|||*\*m|)>*\*m|)>>**log p|)>>>||||)>>*.>>>> In order to compute iterated Frobenius maps we extend the construction from section. For this purpose we introduce the following auxiliary sequences for ,t>: <\equation*> \>\>> mod \|)>|)>i\lg \>. Since we wish to avoid relying on the Kedlaya\UUmans algorithm, the best available algorithm for modular composition is based on the \Pbaby-step giant-step\Q method. It yields the following complexity bound: <\eqnarray*> >>||>*>|)>,>>>> where\1.5> is a constant such that the product of a > matrix by a\>> matrix takes >|)>> operations; the best known theoretical bound is \1.667>10.1>. In practice, one usually assumes =2>. <\lemma> Let >> be given for ,t>. For all \> and i\lg \>, we can compute>>> in time <\equation*> >-1>*\|)>>*. <\proof> For t>, let > be the time needed to compute >>> for any \> and lg \>. Let <\equation*> -1>a*z\\|]>m> denote the canonical representative of \>. We have <\equation*> a>> =-1>a>>*z>> mod \|)>=-1>a>>*z|)>\>>|)> mod \|)>. Now >>> can be computed recursively in time >, so <\equation*> =m*+O>*>|)>. From Proposition it follows that <\equation*> =m*+m-1>**\*m|)>*\*m|)>>**\*m*log p|)>. We conclude by unrolling this identity. The auxiliary sequences >> are computed by induction using the following adaptation of Algorithm. <\specified-algorithm> <\description> >, >>,,>>. >>. <|specified-algorithm> <\enumerate> Compute |)>\z mod \|)>> using binary powering. For ,lg \>, write |)>=-1>a*z> and compute |)>> as <\equation*> -1>a>>*z|)>\\|)> mod \|)>. Return |)>|)>i\lg \>>. <\lemma> Algorithm is correct and runs in time <\equation*> >-1>*log \+log p|)>*\|)>>**\*m*log p|)>. <\proof> We prove the correctness by induction on . The case is clear. Assume that1>> and let |)>\\|]>> be such that <\equation*> \|)>=-1>a*z=z>>+h|)>*\|)>. Then we have <\eqnarray*> -1>a>>*z|)>\\|)> mod \|)>>||-1>a>>*z|)>\>>|)> mod \|)>>>|||-1>a>>*z>> mod \|)>>>|||-1>a*z|)>>> mod \|)>>>|||>>|)>>> mod \|)>>>||||)> mod \|)>.>>>> This completes the correctness proof. Concerning the complexity, the first step takes time >|)>*log p|)>>, whereas the loop requires > modular compositions and *lg \> computations of >>th powers in>. By Lemma, the total running time is therefore bounded by <\eqnarray*> ||>|)>+m*>-1>*\|)>>**\*m*log p|)>|)>*log \+>|)>*log p|)>>>|||>|)>+>-1>*\|)>>**\*m*log p|)>|)>*log \+>|)>*log p|)>.>>>> Using the bounds <\eqnarray*> >|)>>|||)>>**\*m*log p|)>>>|>|)>>||-1>*\|)>>**\*m*log p|)>>>>> from Proposition, this yields the claimed cost. <\corollary> Let \\> for a triangular tower as above. The computation of the irreducible factors of degree D> of a polynomial of degree in > takes an expected time <\equation*> *d-1>+>-1>+log p|)>*\|)>>*. <\proof> By Lemma, the auxiliary sequences >>,,>> can be computed in time >-1>+log p|)>*\|)>>*>. By Proposition and Lemma, we may take <\eqnarray*> >>>||>-1>*\|)>>*>>|>>||-1>*\|)>>*.>>>> The bound now follows from Theorem. <\corollary> Let \\> for a triangular tower as above. A polynomial of degree in > can be tested to be irreducible in time <\equation*> -1>+>-1>+log p|)>*\|)>>*. <\proof> This follows fromTheorem, in a similar way as above. If >*d*log p=O>|)>>, then we note that the bounds in Corollaries and further simplify into >>, which has an optimal complexity exponent in terms of the input/output size. In the case when the extension degree > of > over > is composite, we proposed various algorithms for modular composition that are more efficient than the traditional \Pbaby-step giant-step\Q method. As before, these methods all represent > as the top field of atower of finite fields <\equation> \\\\\\\\\\\. Such towers can be built in several ways and each type of tower comes with its own specific complexity bounds for basic arithmetic operations and modular composition. In this section, we briefly recall the complexity bounds for the various types of towers and then combine them with the results of section. The arithmetic operations in the fields > of the tower() are most efficient if each> is presented directly as a primitive extension \\|]>/|)>|)>> over >, where \\|]>> is amonic polynomial of degree *\*m>. Towers of this type are called . The primitive representations will be part of the precomputation. In, we studied the following types of primitive towers: <\description> For ,t>, we have =\\\> , where \\> is a polynomial of degree> (more generally, for a suitable generalization of composition, > may even be a rational function of degree >); see 7.3> for details. The > are pairwise coprime and there exist monic irreducible polynomials ,\,\>\\> of degrees ,\,m> such that =\> and =\\\> for ,t>. Here > stands for the composed product of irreducible polynomials; see7.4>. We have =\=m=p> and the minimal polynomials of the successive extensions are given by <\eqnarray*> |)>>||-z-1>>||)>>||-z-\>>||)>>||-z-\|)>,>>>> where > is a root of > in > for ,t>. Composed towers and Artin\USchreier towers suffer from the inconvenience that they can only be used in specific cases. Nested towers are somewhat mysterious: many finite fields can be presented in this way, but we have no general proof of this empiric fact and no generally efficient way to compute such representations. From an asymptotic complexity point of view, nested towers are most efficient for the purposes of this paper, whenever they exist. In, we have shown that one composition modulo > can be done in time <\eqnarray*> /\>>||>>*\|)>*\>,\,t|)>|)>,>>>> where the overhead >,\,t|)>> depends as follows on the particular type of tower: <\eqnarray*> >,\,t|)>>||>||>>|>*log \>||>>|>*log \>||>>>>>>>>> In the case of Artin\USchreier towers, we actually have /\>=O*\*log \|)>>, which yields the announced value for >,\,t|)>> under the mild assumption that <\equation*> >=\|)>. By Lemma, the sequence >> can be computed in time <\equation*> O>>*\|)>*\>,\,t|)>*log \+>|)>*log p|)>. By Lemma, we may take <\eqnarray*> >>>||>>*\|)>*\>,\,t|)>|)>.>>>> Since we wish to avoid relying on the Kedlaya\UUmans algorithm, we again use <\eqnarray*> >>||>*>|)>.>>>> Plugging these bounds into Theorems and, we obtain: <\corollary> Let \\> for a primitive tower of one of the above types. Then the computation of the irreducible factors of degree D> of a polynomial of degree in > can be done in expected time <\equation*> *d-1>+>*\>,\,t|)>+log p|)>*. <\corollary> Let \\> for a primitive tower of one of the above types. Then a polynomial of degree in > can be tested to be irreducible in time <\equation*> -1>+>*\>,\,t|)>+log p|)>*. In the particular case when >*log p=|)>>>, we note that both bounds further simplify into >, which is quasi-optimal. We have revisited probabilistic complexity bounds for factoring univariate polynomials over finite fields and for testing their irreducibility. We mainly used existing techniques, but we were able to sharpen the existing bounds by taking into account recent advances on modular composition. However, the following major problems remain open: <\itemize> Do their exist practical algorithms for modular composition with a quasi-optimal complexity exponent? The existing bit complexity bounds for factorization display a quadratic dependency on the bit size of the prime field. Is this optimal? Is it possible to lower the complexity exponent in for irreducible factorization? This problem is equivalent to several other ones, as explained in. The improvements from this paper are most significant for finite fields of a large smooth extension degree over their prime field. Indeed, fast algorithms for modular composition were designed for this specific case in. It would be interesting to know whether there are other special cases for which this is possible. Applications of such special cases would also be welcome. <\bibliography|bib|tm-plain|> <\bib-list|37> M.Ben-Or. Probabilistic algorithms in finite fields. , 394\U398. Los Alamitos, CA, USA, 1981. IEEE Computer Society. 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. A.Bostan, F.Chyzak, M.Giusti, R.Lebreton, G.Lecerf, B.SalvyÉ.Schost. . Frédéric Chyzak (self-published), Palaiseau, 2017. Electronic version available from . D.G.CantorH.Zassenhaus. A new algorithm for factoring polynomials over finite fields. , 36(154):587\U592, 1981. Ph.Flajolet, X.GourdonD.Panario. The complete analysis of a polynomial factorization algorithm over finite fields. , 40(1):37\U81, 2001. Ph.FlajoletJ.-M.Steyaert. A branching process arising in dynamic hashing, trie searching and polynomial factorization. M.NielsenE.Schmidt, , 140, 239\U251. Springer\UVerlag, 1982. J.vonzur Gathen. Who was who in polynomial factorization. , 1\U2. New York, NY, USA, 2006. ACM. J.vonzur GathenJ.Gerhard. . Cambridge University Press, New York, 3rd, 2013. J.vonzur GathenG.Seroussi. Boolean circuits versus arithmetic circuits. , 91(1):142\U154, 1991. J.vonzur GathenV.Shoup. Computing Frobenius maps and factoring polynomials. , 2(3):187\U224, 1992. Z.Guo, A.K.NarayananCh.Umans. Algebraic problems equivalent to beating exponent 3/2 for polynomial factorization over finite fields. , 2016. D.HarveyJ.vander Hoeven. Faster polynomial multiplication over finite fields using cyclotomic coefficient rings. Complexity>, 54:101404, 2019. D.HarveyJ.vander Hoeven. Polynomial multiplication over finite fields in time >. , HAL, 2019. . J.vander Hoeven. . Scypress, 2020. J.vander HoevenG.Lecerf. Modular composition via factorization. Complexity>, 48:36\U68, 2018. J.vander HoevenG.Lecerf. Accelerated tower arithmetic. Complexity>, 55:101402, 2019. J.vander HoevenG.Lecerf. Fast amortized multi-point evaluation. , HAL, 2020. . J.vander HoevenG.Lecerf. Fast multivariate multi-point evaluation revisited. Complexity>, 56:101405, 2020. X.HuangV.Y.Pan. Fast rectangular matrix multiplication and applications. Complexity>, 14(2):257\U299, 1998. E.Kaltofen. Polynomial factorization: a success story. , 3\U4. New York, NY, USA, 2003. ACM. E.KaltofenV.Shoup. Subquadratic-time factoring of polynomials over finite fields. , STOC '95, 398\U406. New York, NY, USA, 1995. ACM. E.KaltofenV.Shoup. Fast polynomial factorization over high algebraic extensions of finite fields. , ISSAC '97, 184\U188. New York, NY, USA, 1997. ACM. E.KaltofenV.Shoup. Subquadratic-time factoring of polynomials over finite fields. , 67(223):1179\U1197, 1998. K.S.KedlayaC.Umans. Fast modular composition in any characteristic. , 146\U155. Los Alamitos, CA, USA, 2008. IEEE Computer Society. K.S.KedlayaC.Umans. Fast polynomial factorization and modular composition. Comput.>, 40(6):1767\U1802, 2011. G.Lecerf. Fast separable factorization and applications. , 19(2):135\U160, 2008. G.L.MullenD.Panario. . Chapman and Hall/CRC, 2013. V.Neiger, J.RosenkildeG.Solomatov. Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation. A.Mantzaflaris, , ISSAC '20, 388\U395. New York, NY, USA, 2020. ACM. M.S.PatersonL.J.Stockmeyer. On the number of nonscalar multiplications necessary to evaluate polynomials. Comput.>, 2(1):60\U66, 1973. A.PoteauxÉ.Schost. Modular composition modulo triangular sets and applications. , 22(3):463\U516, 2013. M.O.Rabin. Probabilistic algorithms in finite fields. , 9(2):273\U280, 1980. V.Shoup. Fast construction of irreducible polynomials over finite fields. , 17(5):371\U391, 1994. V.Shoup. A new polynomial factorization algorithm and its implementation. , 20(4):363\U397, 1995. V.Shoup. . Cambridge University Press, 2nd, 2008. <\initial> <\collection> <\attachments> <\collection> <\associate|bib-bibliography> <\db-entry|+2dXiKvosB5WaTKV|article|KaltofenShoup1998> <|db-entry> V. > <\db-entry|+2dXiKvosB5WaTKW|inproceedings|KedlayaUmans2008> <|db-entry> C. > <\db-entry|+NuHCznHJqSBdAP|article|KedlayaUmans2011> <|db-entry> C. > Comput.> <\db-entry|+78JfxnbGAPNu1f|inproceedings|KaltofenShoup1997> <|db-entry> V. > <\db-entry|+NuHCznHJqSBdAo|article|vdH:ffcomp> <|db-entry> G. > Complexity> <\db-entry|+jZzyy9fWllYOxp|book|GathenGerhard2013> <|db-entry> J. > <\db-entry|+1GTQc2TG9oDov9W|book|aecf-2017-livre> <|db-entry> F. M. R. G. B. É. > > <\db-entry|+VGDrIFx6jkaxRX|book|MullenPanario2013> <|db-entry> D. > <\db-entry|+1GTQc2TG9oDov9P|book|Shoup2008-book> <|db-entry> > <\db-entry|+1GTQc2TG9oDov9X|inproceedings|Gathen2006> <|db-entry> > <\db-entry|+1OIyeUPkc8pGWaw|inproceedings|Kaltofen2003> <|db-entry> > <\db-entry|+VGDrIFx6jkaxbT|article|Berlekamp1967> <|db-entry> > <\db-entry|+1OIyeUPkc8pGWas|article|Berlekamp1970> <|db-entry> > <\db-entry|+1OIyeUPkc8pGWat|article|CantorZassenhaus1981> <|db-entry> H. > <\db-entry|+VGDrIFx6jkaxjp|article|Shoup1995> <|db-entry> > <\db-entry|+1GTQc2TG9oDov9V|article|GathenShoup1992> <|db-entry> V. > <\db-entry|+1OIyeUPkc8pGWay|inproceedings|KaltofenShoup1995> <|db-entry> V. > <\db-entry|+1GTQc2TG9oDov9U|article|GathenSeroussi1991> <|db-entry> G. > <\db-entry|+RNqwNFXZRxKPPF|article|vdH:kucomp> <|db-entry> G. > Complexity> <\db-entry|+1OIyeUPkc8pGWaz|article|Rabin1980> <|db-entry> > <\db-entry|+1lHVqjWrA4JQ1eO|inproceedings|BenOr1981> <|db-entry> > <\db-entry|+VGDrIFx6jkaxRg|article|FlajoletGourdonPanario2001> <|db-entry> X. D. > <\db-entry|+VGDrIFx6jkaxRh|inproceedings|FlajoletSteyaert1982> <|db-entry> J.-M. > E. > <\db-entry|+2N2z5Dwc1ioW8ngz|techreport|vdH:amp> <|db-entry> G. > > <\db-entry|+1GQhZkrScfYODlE|inproceedings|NeigerRosenkildeSolomatov2020> <|db-entry> J. G. > > <\db-entry|+1GIl46OCkUAK86r|article|Lecerf2008> <|db-entry> > <\db-entry|+1GTQc2TG9oDov9e|article|Shoup1994> <|db-entry> > <\db-entry|+2EIRPFE3ONuyFfN|article|vdH:cyclomult> <|db-entry> J. van der > Complexity> <\db-entry|+DNmIiTvtd3nbV7|techreport|vdH:ffnlogn> <|db-entry> J. van der > >> > <\db-entry|+1GIl46OCkUAK86R|article|PoteauxSchost2013-cc> <|db-entry> É. > <\db-entry|+2EIRPFE3ONuyFfG|article|vdH:tower> <|db-entry> G. > Complexity> <\db-entry|+1xqpRSxg16lxOweJ|article|PaSt73> <|db-entry> L. J. > Comput.> <\db-entry|+hVCFX8u1Hzgyugv|article|HuangPan1998> <|db-entry> V. Y. > Complexity> <\db-entry|+2TrWOVNO2T9sRaNO|unpublished|GuoNarayananUmans2016> <|db-entry> A. K. Ch. > > <\db-entry|+byKiFsUoTc7rBN|book|TeXmacs:vdH:book> <|db-entry> > <\references> <\collection> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > |\>|22>> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|bib> TeXmacs:vdH:book KaltofenShoup1998 KedlayaUmans2008 KedlayaUmans2011 KaltofenShoup1997 vdH:ffcomp GathenGerhard2013 aecf-2017-livre GathenGerhard2013 MullenPanario2013 Shoup2008-book GathenGerhard2013 Gathen2006 Kaltofen2003 Berlekamp1967 Berlekamp1970 CantorZassenhaus1981 Shoup1995 GathenShoup1992 KaltofenShoup1995 KaltofenShoup1998 KedlayaUmans2008 KedlayaUmans2011 GathenSeroussi1991 KaltofenShoup1997 vdH:kucomp Rabin1980 BenOr1981 GathenGerhard2013 vdH:ffcomp FlajoletGourdonPanario2001 FlajoletSteyaert1982 KaltofenShoup1997 vdH:amp NeigerRosenkildeSolomatov2020 KedlayaUmans2011 vdH:kucomp vdH:kucomp vdH:ffcomp KaltofenShoup1997 GathenShoup1992 KaltofenShoup1998 KaltofenShoup1998 GathenShoup1992 KaltofenShoup1997 Lecerf2008 GathenGerhard2013 GathenGerhard2013 GathenShoup1992 GathenGerhard2013 Shoup2008-book GathenShoup1992 CantorZassenhaus1981 GathenGerhard2013 GathenShoup1992 GathenShoup1992 GathenGerhard2013 Shoup1994 Rabin1980 Shoup1994 Shoup1994 Rabin1980 BenOr1981 Rabin1980 GathenGerhard2013 vdH:kucomp vdH:cyclomult vdH:ffnlogn GathenGerhard2013 KedlayaUmans2008 KedlayaUmans2011 vdH:kucomp PoteauxSchost2013-cc PoteauxSchost2013-cc GathenGerhard2013 PoteauxSchost2013-cc PoteauxSchost2013-cc PoteauxSchost2013-cc vdH:ffcomp vdH:ffcomp vdH:ffcomp vdH:tower vdH:ffcomp vdH:tower vdH:tower vdH:tower vdH:tower PaSt73 HuangPan1998 vdH:ffcomp PaSt73 vdH:ffcomp vdH:ffcomp vdH:ffcomp vdH:ffcomp GuoNarayananUmans2016 vdH:ffcomp <\associate|toc> |math-font-series||font-shape||1.Introduction> |.>>>>|> |1.1.Notations |.>>>>|> > |1.2.Related work |.>>>>|> > |1.3.Contributions |.>>>>|> > |math-font-series||font-shape||2.Pseudo-Frobenius maps> |.>>>>|> |2.1.Absolute Frobenius maps |.>>>>|> > |2.2.Iterated absolute pseudo-Frobenius maps |.>>>>|> > |2.3.Iterated pseudo-Frobenius |.>>>>|> > |math-font-series||font-shape||3.Pseudo-traces> |.>>>>|> |3.1.Pseudo-traces over the ground field |.>>>>|> > |3.2.Absolute pseudo-traces |.>>>>|> > |math-font-series||font-shape||4.Polynomial factorization> |.>>>>|> |4.1.Square-free factorization |.>>>>|> > |4.2.Distinct-degree factorization |.>>>>|> > |4.3.Equal-degree factorization |.>>>>|> > |4.4.Irreducible factorization |.>>>>|> > |4.5.Rabin's strategy to save pseudo-trace computations |.>>>>|> > |math-font-series||font-shape||5.Theoretical complexity bounds> |.>>>>|> |5.1.Factoring over primitive extensions |.>>>>|> > |5.2.Factoring over towers of finite fields |.>>>>|> > |math-font-series||font-shape||6.Practical complexity bounds> |.>>>>|> |6.1.Factoring over triangular towers |.>>>>|> > |6.1.1.Basic arithmetic |.>>>>|> > |6.1.2.Frobenius maps |.>>>>|> > |6.1.3.Irreducible factorization |.>>>>|> > |6.2.Factoring over special primitive towers |.>>>>|> > |math-font-series||font-shape||7.Conclusion> |.>>>>|> |math-font-series||font-shape||Bibliography> |.>>>>|>