The auxiliary-prime reduction

Put \[ B=20+(n+1)(L+1). \tag{1}\] For a prime \(q\le n\), call a rational prime \(\ell\) an auxiliary prime for \((p,q)\) if \[ \ell\notin\{2,3,p,q\},\qquad \ell\equiv1\pmod{12q},\qquad p^{(\ell-1)/q}\not\equiv1\pmod\ell. \tag{2}\] Thus \(p\) is not a \(q\)th power modulo \(\ell\). The congruence modulo \(12q\) is convenient for the analytic construction in Section 11; the algebraic construction only requires the corresponding congruence modulo \(q\).

The dependence on \(E\) is on the numerical value of the auxiliary primes, not merely their bit lengths. Consequently Theorem 2 becomes a polynomial-time factorization theorem when these primes are bounded by a fixed power of \(B\). Upward search, trial division, and modular exponentiation then construct them within the same kind of bound. We prove this consequence from the cited zero-free theorem in Section 11. The reduction in Theorem 2 does not use that theorem.

History and the role of the construction

Berlekamp’s algorithms put linear algebra at the center of finite-field factorization: Frobenius-fixed elements in the quotient algebra encode its irreducible factors, and polynomial greatest common divisors turn suitable such elements into factors [2, 3]. Randomized algorithms, including Cantor–Zassenhaus [4], obtain expected polynomial running time by finding separating elements with random choices. The difficulty studied here is to make every such choice deterministically, with a bound polynomial in both the degree and the bit length of the characteristic.

Several deterministic results delineate this difficulty. Shoup’s algorithm has polynomial dependence on the degree and a \(p^{1/2+o(1)}\) dependence on the characteristic [28]. Under the generalized Riemann hypothesis, Rónyai obtained polynomial bounds when the number of irreducible factors is bounded [25], and Evdokimov obtained a bound \((n^{\log n}\log p)^{O(1)}\) for general degree [7]. The latter is quasipolynomial in \(n\). The reduction proved here, combined with the fixed-width zero-free strip that follows immediately from Hecke GRH, already gives a polynomial bound in both parameters under GRH. For Theorem 1, the companion supplies that strip without GRH. In particular, the hypotheses and parameters of a deterministic result matter: removing random choices alone does not establish a uniform polynomial bound in \((n+1)L\).

Geometric methods already have an important place in this history. Schoof’s elliptic-curve method computes a square root of a fixed integer \(a\) modulo a varying prime, when one exists, in time polynomial in \(\log p\); the uniform bound in the two parameters is polynomial in \(|a|\) and \(\log p\), rather than in their binary lengths [27]. Pila’s computation of Frobenius on abelian varieties yields deterministic construction of roots of unity of fixed odd prime order modulo primes congruent to \(1\) modulo that order, with a running-time exponent that may depend on the order and on the geometric presentation [22]. These results motivate careful accounting for the varying curve and prime in the present construction. We must bound the degrees of field extensions, the sizes of divisor representations, and the dimensions of all linear systems by fixed powers of the original input parameters.

For a single prime not dividing the discriminant of an integral lift, Rónyai obtained, under GRH, deterministic bounds involving the degree of that lift’s splitting field [26]. A different kind of uniformity arises when reductions modulo many primes are processed together. Altman’s unconditional algorithm takes a monic irreducible polynomial in \(\mathbb Z[x]\) of coefficient height at most \(H\ge2\), with splitting-field degree \(m\), and factors its reductions modulo every prime below \(X\) in total time \[\pi(X)(m\log H)^{O(1)}\log^5X.\] This is an amortized result over primes [1]. The parameter \(m\) can be as large as the factorial of the polynomial’s degree. Thus this result does not give the worst-case single-input bound sought here. Altman’s introduction also provides a recent account of the general deterministic problem and its remaining obstacles.

The algebraic techniques used below have substantial precedents. Computation at unknown roots by working in a quotient algebra and splitting it when a zero test distinguishes components is an instance of dynamic evaluation [5, 6]. The digit calculations in primary multiplicative groups are the prime-power part of the Pohlig–Hellman algorithm [23]. Rónyai already proved that a completely split polynomial of even degree can be split in polynomial time when a quadratic nonresidue is supplied [25]; we include an explicit tournament proof suited to our representation. The odd-degree construction uses cyclic curves \(Y^q=F(X)\). The cyclotomic action on their Jacobians and descriptions of its first torsion layer by ramification divisors are familiar from explicit descent, notably the work of Poonen and Schaefer [24].

Our effective treatment of divisors also builds on established computational geometry. Ideal representations on superelliptic curves, Riemann–Roch algorithms, and finite-dimensional linear algebra for Jacobian arithmetic appear in [8, 13, 16]. For norm equations, we use the relation between cyclic algebras and norms, and the approach through maximal orders and minimal left ideals developed in explicit matrix-algebra computations [9, 15, 14]. The general function-field algorithm of Ivanyos, Kutas, and Rónyai uses a finite-field polynomial-factorization oracle. Here the cyclic presentation gives explicit local orders, and evaluation of their global sections at a rational point gives a rank-one idempotent by linear algebra. The structural explanation uses the splitting of vector bundles on the projective line [10, 12].

The substantive step of the present reduction is the odd-degree separator, together with a uniform implementation of the divisor-class divisions it requires. A filtration of lifted ramification classes keeps the necessary field extensions of polynomial degree. A lattice of divisors at infinity then forces two ramification points to receive different labels. We prove this mechanism and its algorithms directly; the earlier results just discussed provide their mathematical context. The separate step of finding sufficiently small auxiliary primes is isolated in Section 11, which is the only place the companion’s analytic theorem enters.

Proof strategy

The Berlekamp algebra reduces complete factorization to splitting a monic square-free polynomial \(F\) all of whose roots already belong to \(\mathbf F_p\). Write \(N=\deg F\ge2\). The unknown roots are represented simultaneously by the finite algebra \(\mathbf F_p[T]/(F)\); an operation whose outcomes differ between components immediately produces a factor by a greatest common divisor. We can therefore describe computations at an unspecified root and carry them out without first finding that root.

The auxiliary primes construct the multiplicative information needed in these computations. For each odd prime \(q\), they give a field \(K_q=\mathbf F_p(\zeta_q)\) and a generator of the full \(q\)-primary subgroup of \(K_q^*\). The entry for \(q=2\) is a generator of the full \(2\)-primary subgroup of \(\mathbf F_p^*\). Here the \(q\)-primary subgroup consists of the elements whose orders are powers of \(q\). These entries permit extraction of promised \(q\)th roots in finite algebras by small-prime discrete logarithms. Their construction proceeds in increasing \(q\): the only factorization needed to make the entry for \(q\) has degree \(q-1\).

When \(N\) is even, differences between pairs of roots and the \(2\)-primary entry orient the complete graph on the roots. Opposite differences have opposite orientations. The vertex scores cannot all be equal when \(N\) is even, so they provide a separator. The more substantial construction handles odd \(N\).

Choose an odd prime \(q\mid N\), and write \(r=v_q(N)\). Over an explicitly constructed field \(k\) of degree at most \(N(q-1)\) over \(\mathbf F_p\), consider the smooth projective curve with affine equation \[C:\quad Y^q=F(X).\] Its ramification points are \(P_i=(x_i,0)\), where the \(x_i\) are the unknown roots of \(F\). There are \(q\) rational points at infinity. The automorphism \(\sigma(X,Y)=(X,\zeta_qY)\) acts on degree-zero divisor classes; write \(\lambda=1-\sigma\). Degree-zero divisors supported at infinity form a lattice on which \(\lambda\) is injective. In contrast, \(\lambda\) is surjective on the geometric Jacobian.

This difference is the source of the splitting argument. We lift each class \([P_i-\infty_0]\) repeatedly through \(\lambda\), keeping track of an infinity divisor at every stage. A filtration argument shows that all the classes required for these lifts are rational over the field \(k\); the extension degree stays polynomial even though the number of possible classes is large. Summing the lifted classes and applying explicit label tests forces a distinction between ramification points. If every test gave one common label, a fixed nonzero infinity divisor would become divisible by one more power of \(\lambda\) than its lattice valuation allows.

The geometric existence argument is accompanied by a constructive division algorithm. A promised \(\lambda\)-division reduces to a norm equation in \(k(C)/k(X)\). We solve that equation by constructing maximal orders in a split cyclic algebra and computing their global sections on the projective line. A rank-one idempotent in this algebra yields the norm solution. All computations use polynomial and matrix arithmetic; Riemann–Roch reduction controls divisor sizes, and arithmetic circuits store principal functions arising from large infinity multiplicities. Figure 1 records the roles of these ingredients.

The technical results are uniform in the degree of the curve and the prime \(q\). This uniformity is essential: a running-time exponent depending on the genus would not suffice for Theorem 2. We give the finite-field tools first, then the auxiliary table, the geometry, and the effective divisor and norm calculations. The splitter and the factorization driver assemble these ingredients. The final two sections prove the bit bounds and the analytic implication.

Simultaneous execution and zero tests

Let \(k\) be an explicitly represented finite extension of \(\mathbf F_p\), and let \(F\in\mathbf F_p[T]\) be monic, square-free, and totally split, of degree \(N\). Write its roots as \(x_1,\ldots,x_N\) for the proof; the algorithm does not know these roots. The algebra \[ A=k[T]/(F)\simeq\prod_{i=1}^N k, \qquad a(T)\longmapsto(a(x_1),\ldots,a(x_N)) \tag{3}\] lets us carry out arithmetic on all components simultaneously.

This is the dynamic-evaluation principle [5]; we call its use here simultaneous execution. In particular, a divergent pivot or a divergent polynomial degree is useful information: it already supplies the required factor. The convention also applies to nested procedures whose coefficient field is being simulated by \(A\).

Logarithms in primary subgroups

Let \(q\) be a prime, and suppose \(u\) generates a cyclic group of order \(q^s\). For \(a\in\langle u\rangle\), its logarithm \(\ell\in[0,q^s)\) can be recovered one base-\(q\) digit at a time, as in the prime-power logarithm algorithm of Pohlig and Hellman [23]. If \(\ell_j\equiv\ell\pmod{q^j}\) is already known, the next digit is the unique \(c\in\{0,\ldots,q-1\}\) satisfying \[ (au^{-\ell_j})^{q^{s-j-1}} =(u^{q^{s-1}})^c, \qquad 0\le j<s. \tag{4}\] Set \(\ell_{j+1}=\ell_j+cq^j\) and begin with \(\ell_0=0\). Indeed, if \(\ell-\ell_j=q^j(c+qv)\), raising to \(q^{s-j-1}\) removes the term \(qv\) and leaves exactly Equation (4). This uses \(q\) equality tests per digit, rather than an enumeration of \(q^s\) group elements.

The same calculation works in a product of fields when \(u\) has order \(q^s\) in every component. When the product is presented as \(k[X]/H\) with \(H\) square-free, gcds with \(H\) partition the components at each digit according to the equality in Equation (4); retain each nonempty piece and its current digit string. There are at most \(\deg H\) pieces at every level. Keep each final integer logarithm together with its polynomial modulus. Algebra elements subsequently computed from these logarithms can be recombined by polynomial Chinese remaindering. Alternatively, when zero components are represented by idempotent masks, perform the same partitions using those masks. These two implementations will be used below.

Root extraction in a finite reduced algebra

We next give the root procedure used in the norm equations later in the paper. Its input already includes a generator over the constant field, but it does not include generators in extension fields, nor a factorization of the modulus.

We denote this procedure by \(\mathsf{UnitRoot}\). To extract a root in \(k\) itself, apply it with the linear modulus \(H=X\). The proof explains why distinct-degree decomposition suffices: every subsequent partition is obtained by an equality test, and full irreducible factorization is never invoked.

Splitting an even number of roots

Rónyai proved that a supplied quadratic nonresidue suffices to split a completely split polynomial of even degree in polynomial time [25]. A quadratic nonresidue gives a full \(2\)-primary generator by raising it to the odd part of \(p-1\). We give the pair-orientation argument in the form needed here. A primary generator forces a distinction among an even number of roots. The mechanism is an orientation of the pairs of distinct roots: each pair contributes one to precisely one of its two row counts. Equal row counts would then have the nonintegral value \((N-1)/2\).

A degree-\(q\) field without factoring a cyclotomic polynomial

Fix \(q\) and \(\ell=\ell_q\). Put \[R_\ell=\mathbb F_p[T]/(1+T+\cdots+T^{\ell-1}),\qquad \Gamma_\ell=(\mathbb Z/\ell\mathbb Z)^*,\qquad H_q=\{a^q:a\in\Gamma_\ell\}.\] For \(a\in\Gamma_\ell\), let \(\tau_a\) be the automorphism of \(R_\ell\) defined by substitution \(T\mapsto T^a\). Enumerate \(H_q\) by taking \(q\)th powers modulo \(\ell\), and compute \[ U_q=R_\ell^{H_q} =\bigcap_{a\in H_q}\ker(\tau_a-\mathrm{id}) \tag{10}\] by \(\mathbb F_p\)-linear algebra. Products of basis elements of this space, reduced in \(R_\ell\) and expressed in its computed basis, give the multiplication constants of \(U_q\).

This construction is useful precisely because the computation of \(U_q\) never asks for the individual irreducible factors of the degree \(\ell-1\) cyclotomic polynomial. Its field property follows from the verified power-residue test on the integer prime \(\ell\).

Extracting the primary generators

For \(q=2\), solve the \(\mathbb F_p\)-linear equation \[v^p=-v\qquad(v\in U_2)\] and take a nonzero solution. The trace map \(v\mapsto v+v^p\) from the quadratic field \(U_2\) to \(\mathbb F_p\) is nonzero, because it sends \(1\) to \(2\). Its kernel has dimension one, so this instruction succeeds. Then \(c=v^2\) lies in \(\mathbb F_p^*\) and \[c^{(p-1)/2}=v^{p-1}=-1.\] Thus \(c\) is a nonsquare. With \(s=v_2(p-1)\), set \[ \omega_2=c^{(p-1)/2^s}. \tag{11}\] The order of a nonsquare in a cyclic group of even order has the full \(2\)-part of that order. The odd exponent in (11) therefore leaves \(\omega_2\) of exact order \(2^s\).

For odd \(q\), first factor \[\Phi_q(Z)=1+Z+\cdots+Z^{q-1}\] over \(\mathbb F_p\). The smaller-degree nature of this call will be justified below. Choose the first monic irreducible factor in a fixed coefficient order, form its quotient field \(K_q\), and let \(\zeta_q\) be the image of \(Z\). Every root of \(\Phi_q\) has order \(q\), because \(p\ne q\). Writing \(d_q=[K_q:\mathbb F_p]\), finite-field theory gives \[d_q=\operatorname{ord}_q(p)\mid q-1,\] where \(\operatorname{ord}_q(p)\) is the multiplicative order of \(p\) modulo \(q\). In particular \(\gcd(d_q,q)=1\). The tensor product \[V_q=U_q\otimes_{\mathbb F_p}K_q\] is therefore a field of degree \(q\) over \(K_q\): finite fields of coprime degrees intersect in \(\mathbb F_p\), so they are linearly disjoint. Its multiplication table is obtained directly from those of its two factors.

Set \(Q_q=|K_q|\) and \(s_q=v_q(Q_q-1)\). Solve the \(K_q\)-linear system \[ u^{Q_q}=\zeta_q u\qquad(u\in V_q) \tag{12}\] and choose a nonzero solution. To prove existence, the homomorphism \(x\mapsto x^{Q_q-1}\) on \(V_q^*\) has image equal to the norm-one subgroup for \(V_q/K_q\). Indeed both subgroups have order \((Q_q^q-1)/(Q_q-1)\). The norm of \(\zeta_q\) equals \(\zeta_q^{1+Q_q+\cdots+Q_q^{q-1}}=\zeta_q^q=1\). Thus \(\zeta_q\) lies in this image, proving that (12) has a nonzero solution.

For odd \(q\) and \(Q_q\equiv1\pmod q\), the lifting-the-exponent identity is \[ v_q(Q_q^a-1)=s_q+v_q(a)\qquad(a\ge1). \tag{13}\] This is Equation (5). In particular \(v_q(Q_q^q-1)=s_q+1\). Equation (12) says that \(u^{Q_q-1}\) has order exactly \(q\), so the \(q\)-part of the order of \(u\) is exactly \(q^{s_q+1}\). Consequently \[w=u^{(Q_q^q-1)/q^{s_q+1}},\qquad \omega_q=w^q\] have orders \(q^{s_q+1}\) and \(q^{s_q}\), respectively. The unique subgroup of \(V_q^*\) of order \(q^{s_q}\) lies in \(K_q^*\), since \(q^{s_q}\mid Q_q-1\). Therefore \(\omega_q\in K_q\), as required. Its coordinates in \(K_q\) are obtained by solving the linear equations for the known inclusion \(K_q\hookrightarrow V_q\).

All integer valuations used here are found by repeated division by the specified prime \(q\). All powers use binary exponentiation. Neither construction requires an integer factorization of \(p-1\) or \(Q_q-1\).

The increasing-degree construction

The only call above to an as yet unspecified factoring procedure is the factorization of \(\Phi_q\), whose degree is \(q-1\). The interface with the rest of the paper is the following.

Section 9 proves that Factor has exactly this interface. Its correctness and the table construction are established by a common induction: the entry for \(q\) invokes factorization only below \(q\), whereas factorization in degree \(b\) invokes entries only at most \(b\). Thus the table uses no factorization oracle. The only external data in this construction are the verified auxiliary primes.

The curve and its infinity lattice

Let \(K\) be a finite field of characteristic \(p\), let \(q\ne p\) be an odd prime, and suppose that \(K\) contains a primitive \(q\)-th root of unity \(\zeta\). Let \(F\in K[X]\) be monic and square-free, of degree \(N\ge q\) divisible by \(q\), and suppose that all its roots \(x_1,\ldots,x_N\) belong to \(K\). Consider the smooth projective curve \(C/K\) with function field \[K(C)=K(X,Y),\qquad Y^q=F(X).\] The roots \(x_i\) serve only as mathematical indices here; their values need not be known to an algorithm.

A simple root of \(F\) has valuation one, so \(F\) is not a \(q\)-th power even over \(\overline K(X)\). Thus \(C\) is geometrically integral and the map \(X:C\longrightarrow\mathbb P^1\) has degree \(q\). The affine equation is smooth: a singularity would have \(Y=0\) and \(F(X)=F'(X)=0\). At infinity, put \[z=X^{-1},\qquad U=Yz^{N/q},\qquad U^q=z^N F(z^{-1}).\] At \(z=0\) the right side is \(1\), and its \(q\) roots are simple. There are therefore exactly \(q\) rational points at infinity, \[I=\{\infty_j:0\le j<q\},\qquad U(\infty_j)=\zeta^j.\] The ramification points are \(P_i=(x_i,0)\). Each is totally and tamely ramified, and there is no other ramification. The tame Riemann–Hurwitz formula [29] consequently gives \[ g(C)=\frac{(q-1)(N-2)}2. \tag{14}\]

Let \(\sigma\) send \((X,Y)\) to \((X,\zeta Y)\) on points. We let it act on functions by \[ (\sigma h)(X,Y)=h(X,\zeta^{-1}Y), \tag{15}\] so that \(\operatorname{div}(\sigma h)=\sigma\operatorname{div}(h)\). In particular, \(\sigma P_i=P_i\) and \(\sigma\infty_j=\infty_{j+1}\), with subscripts taken modulo \(q\).

Write \(J=\operatorname{Pic}^0(C_{\overline K})\) for the group of geometric degree-zero divisor classes, and put \[\Lambda=\left\{\sum_{j=0}^{q-1}a_j\infty_j: a_j\in\mathbb Z,\ \sum_j a_j=0\right\}.\] For a degree-zero divisor \(D\), its class is denoted by \([D]\). The orbit sum \(1+\sigma+\cdots+\sigma^{q-1}\) acts as zero on both \(J\) and \(\Lambda\). For \(J\), this follows because the orbit sum of a divisor is the pullback of its pushforward to \(\mathbb P^1\), and a degree-zero divisor on \(\mathbb P^1\) is principal. For \(\Lambda\), it follows by summing its coefficients.

Let \(R=\mathbb Z[\xi]\), where \(\xi\) is an abstract primitive \(q\)-th root of unity, and let \(\xi\) act as \(\sigma\). The preceding orbit-sum identity makes \(J\) and \(\Lambda\) into \(R\)-modules. Set \[ \lambda=1-\xi,\qquad e=(\sigma-1)\infty_0. \tag{16}\] The differences \(\sigma^j e\) generate \(\Lambda\). The resulting map \(R\longrightarrow\Lambda\), \(a\longmapsto ae\), is an isomorphism: it is surjective between free abelian groups of the same rank \(q-1\). In particular, multiplication by \(\lambda\) is injective on \(\Lambda\). On divisors and divisor classes, multiplication by \(\lambda\) means \(1-\sigma\).

We shall use \[ q=u\lambda^{q-1}\quad\text{for some }u\in R^*, \qquad R/(\lambda)=\mathbb F_q. \tag{17}\] Indeed, \(q=\prod_{a=1}^{q-1}(1-\xi^a)\), and each quotient \((1-\xi^a)/(1-\xi)\) is an algebraic integer of norm one, hence a unit. The quotient-ring assertion follows by setting \(\xi=1\) in the cyclotomic polynomial \(1+T+\cdots+T^{q-1}\). Multiplication by \(\lambda\) is surjective on \(J\). To see this, identify \(J\) with the geometric points of the Jacobian of \(C\) [19]. Multiplication by \(q\), which is prime to the characteristic, is a surjective isogeny [18]. Equation (17) then implies the surjectivity of multiplication by \(\lambda\).

Recording a class together with an infinity divisor

Ramification divisors and the deck-transformation operator \(1-\sigma\) also underlie explicit descent on Jacobians of cyclic covers; see Poonen and Schaefer [24]. Here we record the infinity divisor as an additional coordinate, so that successive divisions retain its integral divisibility information.

For \(t\ge1\), define the \(R\)-module \[ T_t= \frac{\{(d,W)\in J\times\Lambda:\lambda^t d=[W]\}} {\{([W'],\lambda^t W'):W'\in\Lambda\}}. \tag{18}\] A pair in the numerator will also denote its image in the quotient when there is no ambiguity. The quotient identifies changes obtained by adding an infinity divisor to a representative of \(d\). Keeping \(W\) itself, instead of only its class, will allow us to test divisibility in the free module \(\Lambda\).

The first module has an explicit description in terms of the ramification points. This description will serve twice: it controls Frobenius on all higher modules, and it provides the labels used to distinguish roots.

In particular, if all the labels in (20) agree, then \(([D],W)=0\) in \(T_1\). This implication does not require the labels to be unique. Replacing \(\gamma\) by another \(q\)-th root shifts all of them by the same constant, which has no effect because of (19).

Frobenius and rational divisions

Let \(\Pi\) denote the \(|K|\)-power Frobenius acting on geometric points, divisors, and divisor classes. It commutes with \(\sigma\) and fixes \(\Lambda\) pointwise. Lemma 9 shows that it also fixes \(T_1\) pointwise, since all \(P_i\) and all infinity points are \(K\)-rational. We next propagate this information through the filtration.

For computation we need divisors and functions over \(k\), not just fixed geometric classes. The following finite-field descent fact supplies them. We include its proof to make the distinction explicit.

Why the labels must separate ramification points

Set \(r=v_q(N)\) in Corollary 12 and sum the last members of its lift families. The resulting class \(d_m=\sum_i d_{i,m}\) satisfies \(\lambda^m d_m=[Ne]\). This single relation is enough to force a distinction between ramification points; the particular choices of lifts no longer matter. We now prove that assertion before turning to the algorithms that construct the divisors and evaluate their labels.

Figure 2 separates the two traversals in this proof. The class \(d_m\) determines the class chain by applying \(\lambda\); the divisor \(Ne\) determines the infinity chain by dividing by \(\lambda\). The label tests compare their progress and would force one impossible extra lattice division if every test were constant.

The geometric mechanism is now complete: Corollary 12 supplies the class \(d_m\), and Proposition 13 forces distinct labels using that class. The next sections implement divisor arithmetic, class division, and evaluation without recovering the roots of \(F\) or factoring the finite supports of divisors.

Fractional ideals and finite linear algebra

Smoothness of the affine curve implies that \(O\) is a Dedekind domain. It is a free \(k[X]\)-module with basis \(1,Y,\ldots,Y^{q-1}\). The finite part of a divisor \(D\) is represented by the fractional ideal \[ I(D)=\{a\in\mathcal L:v_P(a)\geq v_P(D) \text{ at every finite point }P\}. \tag{30}\] The zero function is included in this definition. The rest of the representation is the integer vector \((v_{\infty_0}(D),\ldots,v_{\infty_{q-1}}(D))\).

To store a fractional ideal \(I\), choose a monic polynomial \(H\in k[X]\) such that \[ HO\subseteq I\subseteq H^{-1}O. \tag{31}\] Store the image of \(I\) as a \(k\)-subspace of \(H^{-1}O/HO\). Multiplication by \(H\) identifies this quotient with \(O/H^2O\), of dimension \(2q\deg H\). Thus a subspace basis consists of polynomial vectors modulo \(H^2\) in the standard \(Y\)-basis. Lifting this basis and adjoining \(H\) gives a finite list of \(O\)-generators of \(I\). Conversely, from such generators and a bound (31), take their images and repeatedly enlarge their \(k\)-span under multiplication by \(X\) and \(Y\). The process stabilizes in at most \(2q\deg H\) strict enlargements and gives the required ideal image. The convention \(H=1\) represents \(I=O\) with a zero-dimensional quotient.

The identities \[\begin{align*} I(D+E)&=I(D)I(E),& I(-D)&=I(D)^{-1},\\ I(\min(D,E))&=I(D)+I(E),& I(\max(D,E))&=I(D)\cap I(E) \end{align*}\] reduce the first group of operations to finite linear algebra. For a product, take pairwise products of generators and use the bound \(H_DH_E\). For a sum or intersection, embed both subspaces using that same common bound, and take their sum or intersection. For inversion, retain the bound \(H\): an element \(a\in H^{-1}O\) belongs to \(I^{-1}\) precisely when \(au\in O\) for every generator \(u\) of \(I\). These are linear conditions on \(H^{-1}O/HO\). They are independent of the chosen representative of \(a\), since \(HI\subseteq O\). The action of \(\sigma\) is substitution of \(\zeta^{-1}Y\) for \(Y\) in the generators. The corresponding operations on the infinity vectors are immediate.

A known ramification point \(P=(x,0)\) has ideal \((X-x,Y)\), with bound \(H=X-x\). For a nonzero function \(a\), arithmetic in \(\mathcal L\) uses rational coefficients in \(k(X)\) in the standard \(Y\)-basis. Inversion is linear algebra over \(k(X)\). Clearing denominators in both \(a\) and \(a^{-1}\) gives a polynomial \(H\) for which \(aO\) satisfies (31); hence the finite part of \(\operatorname{div}(a)\) is computable without finding any of its points.

Intermediate bound polynomials need not be minimal. The following compression both controls their degrees and supplies the norm data used in class division.

Local expansions and Riemann–Roch reduction

The ideal representation controls all finite points collectively. At the few specified points where a value or inequality is required, local expansions give the additional information.

At infinity use \(z=X^{-1}\) and \(U=Yz^{N/q}\). The equation \[U^q=z^NF(z^{-1}),\qquad U(0)=\zeta^j\] determines the expansion at \(\infty_j\) by simple-root Hensel lifting. At \(P=(x,0)\) use \(Y\) as uniformizer and solve \(F(X)=Y^q\) with \(X(0)=x\); the derivative \(F'(x)\ne0\) again permits coefficient-by-coefficient lifting. The valuation and leading coefficient of a nonzero function are then found by substitution and division of the leading terms.

Here is an explicit precision bound. Write a function as \(A(X,Y)/B(X)\), where \(\deg_Y A<q\) and every coefficient in \(X\), as well as \(B\), has degree at most \(E\). The polynomial \(A\) has poles only at infinity, with total pole degree at most \(q(E+N)\); the same bound holds for \(B\). The degree of its zero divisor equals its pole degree, so no nonzero numerator or denominator can have an order of vanishing greater than this bound at a rational point. Consequently local substitutions through precision \[ 8q(E+N+1) \tag{33}\] suffice to identify their first nonzero Laurent coefficients, even after the possible pole at infinity has been removed. For a represented divisor, its coefficient at a specified finite point is the minimum of the valuations of a list of ideal generators; zero generators may be discarded.

We next turn Riemann–Roch existence into a linear computation. Recall that \[L(V)=\{a\in\mathcal L:\operatorname{div}(a)+V\geq0\}\cup\{0\}\] is a finite-dimensional \(k\)-vector space. Given \(D\) and \(\ell\geq0\), choose a bound \(H\) for \(I(-D)\). Every function in \(L(D+\ell\infty_0)\) has the form \[ a=H^{-1}\sum_{j=0}^{q-1}a_j(X)Y^j, \qquad \deg a_j\leq \deg H+\|D\|+\ell. \tag{34}\] To justify the degree bound, put \[M=\max_{a_j\ne0}\bigl(\deg a_j+jN/q-\deg H\bigr).\] The coefficient of \(z^{-M}\) in the expansions at infinity is a nonzero polynomial of degree less than \(q\) evaluated at the \(q\) distinct values \(1,\zeta,\ldots,\zeta^{q-1}\). It cannot vanish at all of them. Thus at one infinity point the pole order, interpreted as \(-v_{\infty_j}(a)\), is exactly \(M\). The defining inequalities for \(L(D+\ell\infty_0)\) give \(M\leq\|D\|+\ell\), which implies (34).

In this finite ansatz, membership in \(I(-D)\) is a subspace condition, and \[v_{\infty_j}(a)\geq-v_{\infty_j}(D)-\ell\,\mathbf1_{j=0} \qquad(0\leq j<q)\] is a list of linear conditions on Laurent coefficients. Expansions to the bound (33), increased by \(8q(\|D\|+\ell+1)\), suffice. Solving the resulting linear system therefore computes the whole space \(L(D+\ell\infty_0)\).

For degree-zero \(D\), the Riemann–Roch inequality [29] gives \(\dim_kL(D+g\infty_0)\geq1\). Choose a nonzero solution \(a\) by a fixed pivot convention and define \[ \operatorname{ReduceDivisor}(D)=D'=D+\operatorname{div}(a). \tag{35}\] Since \(D'+g\infty_0\) is effective of degree \(g\), we have \(\|D'\|\leq2g\). Retain \(a\) whenever a later computation needs the linear equivalence. If a degree-zero divisor \(D\) is known to be principal, taking \(\ell=0\) instead produces a nonzero \(a\) with \(D+\operatorname{div}(a)=0\): the effective divisor on the left has degree zero.

All vector spaces and polynomial degrees in these constructions are polynomial in the parameters in Proposition 14. Dense polynomial operations, fraction reduction over \(k(X)\), and linear algebra therefore prove its complexity assertion. For example, the ideal quotient has dimension \(2q\deg H\), and the ansatz (34) has at most \(q(\deg H+\|D\|+\ell+1)\) unknowns. Rational linear algebra does not cause uncontrolled degree growth: after common denominators are cleared, minors of an \(s\times s\) matrix with polynomial entries of degree at most \(d\) have degree at most \(sd\). Reduced elimination entries and solutions are ratios of such minors. This completes the proof of Proposition 14.

Summing divisors given over a product algebra

The odd-degree splitter first produces one divisor for each root of \(F\), through a computation over \(A=k[T]/F(T)\). The next lemma computes their sum over \(k\), while the roots remain unknown. A norm from the finite algebra \(A\) will replace the unavailable product over its components.

For the application \(s=N\). The number \(b\) can be bounded by \(2q\deg H_i+1\) in the compressed representation, and the characteristic cutoff in Section 10 guarantees the required distinct scalars. Matrix determinants and ideal closure have sizes polynomial in these parameters.

Binary coefficients at infinity and function circuits

Riemann–Roch reduction has cost polynomial in absolute degree. It must not be applied directly to an infinity divisor whose coefficients are exponentially large integers. We instead perform the class arithmetic by binary additions and retain the accompanying rational function as a circuit.

The cyclic algebra and its local matrix models

The polynomial \(Y^q-F\) is irreducible over \(K_0\): a place at which \(F\) has valuation one is Eisenstein for it. Thus \(\mathcal L\) is a field, cyclic of degree \(q\) over \(K_0\). Form the \(K_0\)-algebra \[ \mathcal E=\bigoplus_{b=0}^{q-1} \mathcal L V^b, \qquad V a=\rho(a)V\ (a\in \mathcal L),\qquad V^q=G. \tag{38}\] Its multiplication table in the basis \[W_{ab}=Y^aV^b,\qquad 0\le a,b<q,\] is explicit. The norm promise implies that \(\mathcal E\) is a full matrix algebra over \(K_0\), but does not initially give us an isomorphism. Indeed, if \(h_0\) is any norm solution, let \(\mathcal L\) act on itself by multiplication and let \(V\) act by \(h_0\rho\). These operators satisfy (38). Their linear independence follows by applying a putative relation between the operators \(\rho^b\) to \(1,Y,\ldots,Y^{q-1}\) and using the invertible matrix \((\zeta^{bj})_{b,j}\). Dimension then gives an isomorphism \[ \mathcal E\simeq M_q(K_0). \tag{39}\] This argument establishes existence only; the algorithm never uses \(h_0\) or this unspecified isomorphism.

A rank-one idempotent in \(\mathcal E\) is an element \(e\) with \(e^2=e\) whose image under (39) has rank one. The following observation explains why constructing such an element solves the original norm equation.

Our remaining task is to construct \(e\). We will impose local integrality conditions on elements of \(\mathcal E\), then find a rank-one matrix in their values at infinity.

Let \(v\) be a closed point of \(\mathbb P^1_k\). Write \(K_v\) for the completed rational function field, \(R_v\) for its valuation ring, \(\kappa_v\) for its residue field, and \(T\) for a uniformizer. A lattice in a finite-dimensional \(K_v\)-space is a free \(R_v\)-module of full rank. An order in \(\mathcal E\otimes K_v\) is a lattice that contains \(1\) and is closed under multiplication; it is maximal if no strictly larger order contains it. We construct one maximal order \(\mathcal A_v\) at every \(v\). Only the points dividing \(F\), the numerator or denominator of \(G\), and the point at infinity require nontrivial conditions.

We will repeatedly use the matrix trace \(\operatorname{tr}\) on the split algebra. It does not depend on the choice of isomorphism in (39). Conjugation by \(Y\) and \(V\) shows that every nonidentity basis monomial has trace zero, while \(\operatorname{tr}(1)=q\). Consequently \[ a=\sum_{a',b'} c_{a'b'}W_{a'b'} \quad\Longrightarrow\quad c_{ab}=q^{-1}\operatorname{tr}(aW_{ab}^{-1}). \tag{41}\] Here \(q\) is invertible by (37).

Why one fiber contains a rank-one matrix

Define the finite-dimensional \(k\)-algebra of global sections and its evaluation image by \[ \mathcal S=\{a\in\mathcal E:a\in\mathcal A_v\text{ for every }v\}, \qquad \mathcal B=\operatorname{ev}_\infty(\mathcal S)\subseteq M_q(k). \tag{45}\] We will compute both spaces by linear equations. First we establish the feature of \(\mathcal B\) that will make this useful: up to change of basis it is the algebra of all block upper triangular matrices. Its first block therefore contains the image of a rank-one idempotent.

Here is the geometric explanation, including the descent from completed local orders. Intersect \(\mathcal A_v\) with the rational algebra \(\mathcal E\). This is a full lattice over the ordinary local discrete valuation ring at \(v\), and its completion is \(\mathcal A_v\). Indeed the completed lattice lies between two powers of a rational uniformizer times a fixed rational lattice. Rational approximation to a basis, to sufficiently high precision, produces a basis of the same completed lattice. Equivalently, the finitely many congruences between these two bounds descend to the ordinary local ring. Maximality descends as well, since a larger ordinary order would yield a larger completed order.

For the following existence argument only, fix an isomorphism (39). An ordinary local maximal order in \(M_q(K_0)\) is the endomorphism ring of a lattice. In fact, apply the order to the standard local lattice \(R^q\) and take its span \(M\). The order is a finite module and contains the identity, so \(M\) is a full lattice stable under it. The containing order \(\operatorname{End}_R(M)\) must equal it by maximality. At all but finitely many places the standard rational basis matrices and their inverse change of coordinates are integral; there we may use \(M=R^q\). The resulting lattices glue to a vector bundle \(\mathcal V\) of rank \(q\) on \(\mathbb P^1_k\). Concretely, its local sections are rational column vectors satisfying the specified lattice conditions. A basis of one local lattice gives a trivialization on a neighborhood after excluding the finitely many poles and other exceptional points. We have proved \[ \mathcal S=H^0(\mathbb P^1_k,\operatorname{End}\mathcal V). \tag{46}\] The chosen matrix model at infinity identifies the endomorphism fiber with \(M_q(k)\). Any two such identifications differ by conjugation: an automorphism of a full matrix algebra sends matrix units to matrix units, from which a change of column basis is obtained. Thus its particular choice will not affect the asserted shape of \(\mathcal B\).

The following form of the projective-line splitting theorem holds over the original field, rather than only after extending its constants; see Hazewinkel–Martin [12].

Apply the lemma and order the summands by decreasing degree: \(\mathcal V=\bigoplus_{i=1}^q\mathcal O(d_i)\) with \(d_1\ge\cdots\ge d_q\). The \((i,j)\) entry of a global endomorphism is a section of \(\mathcal O(d_i-d_j)\). If \(d_i<d_j\) it is zero; otherwise its value at infinity is arbitrary, because a line bundle of nonnegative degree has a section with any prescribed value at that point. Grouping the equal degrees proves the promised block upper triangular description of \(\mathcal B\). This is an existence proof of the shape, not an algorithm for computing the splitting of \(\mathcal V\).

Figure 3 isolates the part of the vector-bundle argument that is actually computed. The splitting theorem guarantees the triangular shape; the trace pairing finds enough of that shape to construct a rank-one matrix without a factorization or a change of basis.

From the fiber idempotent to a norm solution

Lift the matrix \(a_0\) of Lemma 21 to any \(b\in\mathcal S\) with \(\operatorname{ev}_\infty(b)=a_0\). This is a linear solve once (45) has been computed. The coefficients of the generic characteristic polynomial of \(b\) are regular at every point, since \(b\) is a global endomorphism of \(\mathcal V\). A rational function regular on \(\mathbb P^1_k\) is constant. Evaluating at infinity consequently gives \[\det(T-b)=T^{q-1}(T-1).\] The primary decomposition for the relatively prime factors \(T^{q-1}\) and \(T-1\) shows that \[ e=b^q \tag{47}\] is the projection onto the one-dimensional \(1\)-eigenspace: it is zero on the nilpotent part and the identity on that eigenspace. Thus \(e\) is a rank-one idempotent in \(\mathcal E\).

Lemma 19 now recovers a norm solution by solving \(Ve=he\) over \(K_0\).

It remains to make the spaces in (45) computable with polynomially many coefficients. This is where the explicit local models, rather than an unspecified splitting of the cyclic algebra, are essential.

Computing all sections by finite linear systems

Write \(G=A/B\) with coprime nonzero polynomials \(A,B\in k[X]\). Square-free decomposition and gcds partition the finite places dividing \(FAB\) into pairwise coprime monic square-free polynomials \(H_i\) such that the two values \[\bigl(v(F),v(G)\bigr)=(\epsilon_i,w_i)\] are constant over the irreducible factors of each \(H_i\). No irreducible factorization is involved: decompose the multiplicity layers of \(A\) and \(B\) and refine their intersections with each other and with \(F\) by gcds. All these polynomials have degree less than \(p\) by (37), so derivative-based square-free decomposition has no inseparable residual case. Put \[ H=\prod_i H_i,\qquad d_H=\deg H\le N+2D, \qquad M=10q^2(N+D+1). \tag{48}\]

At every place in group \(i\) we may use the same rational uniformizer \(T=H_i\). Arithmetic modulo \(H_i^s\) carries out, simultaneously, all the required arithmetic modulo the \(s\)th power of these local uniformizers. The Chinese remainder theorem explains this statement without requiring the factors of \(H_i\) to be computed. When a local model requires a residue root, its residue is a unit modulo \(H_i\) and is a \(q\)th power in every residue-field component by the norm promise. Lemma 4 constructs the root in \(k[X]/H_i\). The characteristic bound supplies more than \(d_H^2\) distinct prime field scalars for that lemma. Hensel lifting then works modulo powers of \(H_i\), since the derivative \(qR^{q-1}\) or \(qS^{q-1}\) is a unit.

It follows that every global section is included in the ansatz \[ b=\sum_{a,b'=0}^{q-1}c_{ab'}W_{ab'},\qquad c_{ab'}=\frac{P_{ab'}(X)}{H(X)^M},\qquad \deg P_{ab'}\le M(d_H+1). \tag{49}\] Indeed the denominator clears every finite pole, and the bound at infinity says precisely that its numerator degree exceeds its denominator degree by at most \(M\). The polynomial coefficients in (49) are our scalar unknowns.

For each finite group impose membership in \(\mathcal A_v\) as follows. In a matrix model compute, modulo \(T^{2M+1}\), the integral quantities \(T^M c_{ab'}\) and every matrix entry of \(T^M W_{ab'}\). Their products and sums give \(T^{2M}\) times the matrix of the section. The section is integral exactly when all coefficients below order \(2M\) vanish. These are linear conditions over \(k\). In a scaled-basis order use the coordinates in that basis in place of matrix entries and impose the identical divisibility condition. At infinity make the same computation with \(T=z\) and the prescribed matrix model. The coefficient of \(z^{2M}\), after the lower ones vanish, is exactly the evaluated matrix in \(M_q(k)\).

For completeness, the truncated entries are computed without an infinite-series oracle. Each nonzero basis entry has the form \(T^e u\) for a known exponent \(e\) with \(|e|\le M\) and a unit \(u\) given by the diagonal and weighted-shift formulas. Lift the required unit roots to precision \(3M+3\) by the simple-root Hensel iteration. After multiplication by \(T^M\), this precision more than supplies all terms through \(T^{2M}\). For the rational coefficients of (49), cancelling \(T^M\) from the denominator leaves a unit denominator at the group, inverted by the polynomial Euclidean algorithm. At infinity replace \(X\) by \(z^{-1}\) and cancel the known powers of \(z\). The same finite-precision computation then applies.

Solving these linear equations gives a basis of \(\mathcal S\) together with the evaluated matrix of every basis vector. Taking their span gives \(\mathcal B\) and retains a linear map with which to lift its elements. The ansatz contains every section by Lemma 22; the imposed conditions are necessary and sufficient at every exceptional place, and elsewhere the ansatz is already integral. Thus the computed spaces are exactly those in (45).

Algorithm and polynomial bounds

The complete procedure can now be stated without any existential computational step.

1. Form the multiplication table of \(\mathcal E\) in the basis \(Y^aV^b\). Compute the square-free groups \(H_i\) and the local models, obtaining their residue roots by Lemma 4 and their needed precision by Hensel lifting.

2. Use (49) and the divisibility conditions above to compute \(\mathcal S\) and its evaluation map to \(M_q(k)\).

3. In the image \(\mathcal B\), compute the trace-pairing kernel, its common column kernel, and a rank-one idempotent \(a_0=vw\) as in Lemma 21.

4. Lift \(a_0\) to \(b\in\mathcal S\) by a linear solve and compute \(e=b^q\) with the multiplication table.

5. Solve \(Ve=he\) for \(h\in \mathcal L\) over \(k(X)\) and return \(h\).

Every step is deterministic after fixing a basis order and the first available pivot in each linear solve. The preceding arguments prove existence of the required roots, a nonzero vector in the common kernel, a lift of \(a_0\), and a solution of the last system; therefore the procedure terminates on every promised input.

We record bounds to ensure that this is also a uniform algorithm. There are at most \(d_H\) groups, and \[d_H\le N+2D,\qquad M=10q^2(N+D+1).\] The number of unknowns in (49) is \(q^2(M(d_H+1)+1)\). The total number of scalar local conditions is at most a constant times \(q^2M(d_H+1)\), since precision at a group of degree \(d_i\) contributes \(O(Md_i)\) coefficients. All quotient polynomial rings have dimension at most \((3M+3)d_H\) over \(k\). These are fixed polynomial bounds in \(q,N,D\). The finite-field root calculations also have polynomial complexity by Lemma 4; the bit lengths of their powering exponents are \(O(d_H\log|k|)\).

For explicit denominator control, compute \(b^q\) by successive multiplications by \(b\). Write \(P_*=M(d_H+1)\). The coefficients of \(b^s\) have the common denominator \[H^{Ms}B^{s-1}\] and numerator degrees at most \(sP_*+(s-1)(N+D)\). Indeed a product of two standard basis monomials introduces at most one factor of \(F\) and one factor of \(G=A/B\). Passing to the displayed common denominator at the next multiplication therefore adds at most \(P_*+N+D\) to numerator degree, including every addition of terms. This proves the assertion by induction for \(1\le s\le q\). The final system \(Ve=he\) has the same common denominator with at most one extra factor of \(B\); its cleared entries have polynomial degree. A solution of this consistent rank-\(q\) system is expressed by ratios of minors, of degrees at most \(q\) times the cleared entry degree. Fraction-reducing elimination or these minor formulas therefore bounds the output degree and the number of field operations by fixed polynomials. Standard dense polynomial arithmetic and Gaussian elimination convert these bounds to a fixed polynomial in \(q,N,D,\log|k|\) bit operations. The more generous common bound needed by the full factorization algorithm is recorded in Proposition 27.

Finally, polynomial gcds, Hensel lifting, and linear elimination use only field arithmetic and zero tests. Integer choices such as degrees and multiplicities are determined by those tests; the valuation groups are formed by polynomial gcds rather than by an unknown factorization. The finite-field root routine has the same property. Hence all steps are compatible with simultaneous execution, proving the last assertion of Theorem 18 and completing its proof.

The working field and the computational operations

Put \[ r=v_q(N),\qquad m=1+(q-1)r, \qquad Q_K=|K|,\quad s_K=v_q(Q_K-1). \tag{53}\] Construct \[ k=K[T]/(T^{q^r}-\omega_K), \qquad \omega=T\bmod(T^{q^r}-\omega_K). \tag{54}\] This quotient is a field. Indeed, every root of the binomial has exact order \(q^{s_K+r}\). For every positive integer \(b\), the elementary lifting-the-exponent identity gives \[v_q(Q_K^b-1)=s_K+v_q(b).\] Thus the smallest extension of \(K\) containing such a root has degree \(q^r\). The binomial has that degree and is irreducible. The same identity shows that \(\omega\) generates the entire \(q\)-primary subgroup of \(k^*\). Notice the bounds \[ q^r\le N,\qquad m\le q^r\le N, \qquad [k:\mathbb F_p]\le N(q-1). \tag{55}\] The middle inequality follows from \(q^r=(1+(q-1))^r\ge1+r(q-1)\).

Use the curve \(C/K\) and its base extension to \(k\) from Section 4.1. Thus \(Y^q=F(X)\), \(P_i=(x_i,0)\), \(\lambda=1-\sigma\), and \(e=(\sigma-1)\infty_0\). Work simultaneously over \[A=k[T_1]/F(T_1)\simeq\prod_{i=1}^N k.\] The element \(T_1\bmod F\) provides the known ramification point in each component computation. The labels \(i\) and values \(x_i\) are used only in the correctness proof.

Here are the precise divisor operations that the procedure uses. The divisor arithmetic of Proposition 14 adds divisors, applies \(\sigma\), and reduces a degree-zero divisor to an equivalent one of absolute degree at most \(2g\). Lemma 16 sums a simultaneously represented family across the components of \(A\), without finding those components. Lemma 17 finds a defining function for a principal divisor of the form \((1-\sigma)D-W\), even when the infinity divisor \(W\) has large integer coefficients. It handles those coefficients by addition and doubling circuits and retains the function as a product circuit. Valuations and leading values at \(P_i\) can be computed from this circuit.

The procedure \(\mathrm{LambdaDivide}\) of Proposition 23 takes a reduced degree-zero divisor \(D\) and a known ramification point \(P_i\). Its promise is that \([D]\) has a \(\lambda\)-division represented by a divisor over \(k\). It returns a reduced degree-zero divisor \(D'\) over \(k\) satisfying \[\lambda[D']=[D].\] All these procedures use field arithmetic and scalar zero tests, so they admit the simultaneous execution just described. At any test that distinguishes components, \(\mathrm{OddSplit}\) stops and returns the resulting factor.

The procedure

The algorithm has three stages: lift the ramification classes, sum the lifts, and test labels. We first give the complete instructions and then prove that the promise for every call holds and that a factor must be returned.

1. Lift each ramification class. In simultaneous execution over \(A\), start with \(D=P_i-\infty_0\) in component \(i\). Apply \(\mathrm{LambdaDivide}(D,P_i)\) successively \(m-1\) times, each time replacing \(D\) by its output. Write \(d_{i,t}\) for the class after \(t-1\) divisions, so \(d_{i,1}=[P_i-\infty_0]\).

2. Sum the lifts and apply successive powers of \(\lambda\). Use the simultaneous divisor-sum operation to obtain a divisor representing \[d_m=\sum_{i=1}^N d_{i,m}.\] Reduce it, obtaining \(D_m\). For \(t=m-1,m-2,\ldots,1\), reduce \((1-\sigma)D_{t+1}\) to obtain \(D_t\). Thus, writing \(d_t=[D_t]\), \[ d_t=\lambda^{m-t}d_m. \tag{56}\] Compute the integral infinity divisors \[ W_t=\lambda^{-(t-1)}Ne, \qquad 1\le t\le m. \tag{57}\] Here the inverse notation denotes the unique solution in the lattice \(\Lambda\), not division of divisor classes. These solutions exist because \(q^r\mid N\) and \(q\) is an associate of \(\lambda^{q-1}\). One may compute them successively by solving \((1-\sigma)W_{t+1}=W_t\) on the cyclic infinity coordinates.

3. Test the labels. For \(t=1,2,\ldots,m\), perform the following operations. The relation \(\lambda d_t=[W_t]\) will hold at every test that is reached. Find a function \(h_t\in k(C)^*\) satisfying \[ \operatorname{div}(h_t) =(1-\sigma)D_t-W_t. \tag{58}\] It may be stored by the product-circuit method above. Evaluate \(h_t(P_i)\) and \(v_{P_i}(D_t)\) simultaneously. The value \(h_t(P_i)^q\) is independent of \(i\); extract it as a scalar \(c_t\in k^*\) from \(A\). Use \(\mathrm{UnitRoot}\) from Lemma 4 to find \(\gamma_t\in k^*\) with \(\gamma_t^q=c_t\). For each component, compare \(h_t(P_i)/\gamma_t\) with \(1,\zeta,\ldots,\zeta^{q-1}\) and form \[ l_{i,t}=v_{P_i}(D_t) -\log_\zeta\bigl(h_t(P_i)/\gamma_t\bigr) \pmod q. \tag{59}\] If these labels differ, return a nontrivial proper gcd with \(F\) corresponding to one of their values. If they all agree, proceed to the next test.

Every factor obtained by simultaneous execution lies in \(\mathbb F_p[X]\). Indeed, although the gcd may be computed over \(k\), it is the monic product of \(X-x_i\) over a subset of roots \(x_i\in\mathbb F_p\). Thus no additional descent of the output factor is required.

Correctness and cost

Separating the factors through the Berlekamp algebra

Let \(h\in\mathbf F_p[X]\) be monic and square-free, of degree \(d\ge1\). The Berlekamp algebra [2] in \(R_h=\mathbf F_p[X]/h\) is \[ \mathcal B_h=\{a\in R_h:a^p=a\}. \tag{61}\] The Frobenius map is \(\mathbf F_p\)-linear, so a basis of \(\mathcal B_h\) is computed by powering the standard basis of \(R_h\) and taking the kernel of Frobenius minus the identity. Products of basis elements are computed in \(R_h\) and expressed in this basis by linear algebra.

If \(h=\prod_{i=1}^{r}h_i\) is its unknown irreducible factorization, the Chinese remainder theorem identifies \[R_h\simeq\prod_{i=1}^{r}\mathbf F_p[X]/h_i, \qquad \mathcal B_h\simeq\mathbf F_p^r.\] Indeed the Frobenius-fixed elements of each finite field component are exactly \(\mathbf F_p\). Thus \(r=\dim\mathcal B_h\), and \(h\) is irreducible if and only if \(r=1\).

The recursive driver

Fix the degree \(n\) of the original input, put \[ L=\lceil\log_2p\rceil, \qquad B=20+(n+1)(L+1), \tag{62}\] and use the same \(B\) throughout preprocessing and recursion. Call the characteristic small when \(p\le B^{200000}\). For larger \(p\), the inequalities needed for the separating-element search and all finite-field searches in the splitting procedures follow from the size bounds in Section 10.

The procedure \(\mathsf{Split}(F)\) receives a monic, square-free, totally split polynomial of degree \(N\ge2\) in the large-characteristic case. If \(N\) is even, use Proposition 5. If \(N\) is odd, use Proposition 24. In either case it returns a nontrivial proper monic divisor, and uses table entries only for primes at most \(N\).

Here is the complete recursive procedure. Its input \(h\) is monic; its output is a list of distinct monic irreducible factors with multiplicities. Repeated occurrences of the same monic polynomial are merged by comparing their coefficient lists.

Procedure \(\mathsf{Factor}(h)\).

1. If \(\deg h=0\), return the empty list. If \(\deg h=1\), return \(h\) with multiplicity one.

2. Compute the formal derivative \(h'\). If \(h'=0\), write \(h=g^p\) by retaining the coefficients in positions divisible by \(p\), recursively factor \(g\), multiply every returned multiplicity by \(p\), and return the resulting list.

3. If \(h'\ne0\), compute \(d_0=\gcd(h,h')\). When \(d_0\ne1\), recursively factor \(d_0\) and \(h/d_0\), merge the two lists by adding multiplicities of equal factors, and return the merged list.

4. Now \(h\) is square-free. Compute \(\mathcal B_h\) and \(r=\dim\mathcal B_h\). If \(r=1\), return \(h\) with multiplicity one.

5. If the characteristic is small and \(r\ge2\), choose a nonscalar \(b\in\mathcal B_h\). Test \(\gcd(h,b-a)\) for \(a=0,\ldots,p-1\) until a nontrivial proper gcd is found. Denote it by \(h_1\).

6. If the characteristic is large and \(r\ge2\), use Lemma 25 to obtain \(b(t)\) and \(F_t\). Compute \(S=\mathsf{Split}(F_t)\) and set \(h_1=\gcd(h,S(b(t)))\).

7. In either splitting case, recursively factor \(h_1\) and \(h/h_1\), and return the union of the resulting lists.

A nonscalar element in Step 5 is found by testing the computed basis against the one-dimensional space \(\mathbf F_p\cdot1\). In Step 2 the coefficient list is merely scanned; no loop of length \(p\) is needed to form \(g\).

Preprocessing and the original input

The table restriction in Proposition 26 closes the apparent dependency between factoring and constructing the table. Enumerate primes \(q\le n\) in increasing order by trial division. At prime \(q\), carry out Proposition 7 with the supplied auxiliary prime \(\ell_q\). Its only factorization call, for odd \(q\), is on the cyclotomic polynomial \(\Phi_q\) of degree \(q-1\). Proposition 26 therefore uses only table entries already constructed. At \(q=2\) no factorization call is required. Induction over these primes constructs the whole table before the final call on the input polynomial. A recursive \(\mathsf{Factor}\) call uses the available table and never restarts this preprocessing.

For the original nonzero polynomial \(f\), first read its degree and leading coefficient \(c\). A constant input returns \((c,\varnothing)\) immediately. For positive degree normalize to \(h=c^{-1}f\). Degrees zero and one require no table. In the small-characteristic case use the scalar-search driver directly. Otherwise construct the table once as above and apply \(\mathsf{Factor}(h)\). Its output \((g_i,e_i)\) satisfies \[f=c\prod_i g_i^{e_i},\] with distinct monic irreducible \(g_i\) and positive integer \(e_i\), exactly as required. Each exponent is at most \(n\) and is stored in binary.

Apart from the splitting calls, the driver consists of polynomial arithmetic and linear algebra of degree at most \(n\), together with the displayed parameter searches. Scalar enumeration in the small case costs at most \(B^{200000}\) trials per call. In the large case the separating-element search has at most \(n^3+1\) trials. Across the at most \(n\) table entries and the final factorization, Proposition 26 gives \(O((n+1)^3)\) recursive calls. Section 10 combines these bounds with the sizes of the norm, divisor, and table computations. Thus the complete algorithm has polynomial bit cost in \(n\), \(L\), and the largest supplied auxiliary prime; obtaining suitably small auxiliary primes is the separate arithmetic issue considered later.

A uniform smoothed prime-ideal estimate

Fix a nonzero nonnegative function \(\varphi\in C_c^\infty((1,2))\), and put \[\Phi(s)=\int_0^\infty\varphi(t)t^{s-1}\,dt.\] In particular \(\Phi(1)>0\). For a number field \(M\) of degree \(d_M\) and absolute discriminant \(D_M\), define \[\Psi_M(x)=\sum_{\mathfrak p}\sum_{j\ge1} \log\mathop{\mathrm{N}}\mathfrak p\, \varphi\bigl((\mathop{\mathrm{N}}\mathfrak p)^j/x\bigr),\] where \(\mathfrak p\) runs over nonzero prime ideals of its ring of integers.

Detecting failure of complete splitting

The argument also identifies a consequence of the algebraic reduction alone. GRH for finite-order Hecke \(L\)-functions places their nontrivial zeros on \(\Re s=1/2\), and therefore implies the strip used above. Thus the reduction yields deterministic polynomial-time factorization under GRH independently of the companion’s proof of Theorem 28. Theorem 1 uses the cited theorem to supply the same input without that assumption.