Deterministic Polynomial Factorization over Prime Fields

1 Introduction

Let p be a prime, given in binary, and let f\in\Fp[x] be a nonzero polynomial, given by its dense coefficient list. Write n=\deg f and L=\lceil\log_2 p\rceil. Complete factorization means computing the leading coefficient c and distinct monic irreducible polynomials g_i, with positive integer multiplicities e_i, such that

The empty product is permitted when n=0. The complexity parameter is (n+1)L, so an algorithm polynomial in p does not give a polynomial-time algorithm in the prescribed representation.

Finite-field factorization is a basic constructive problem in algebra. It also exposes a persistent distinction between randomized and deterministic computation: a random element of a product of finite fields often separates its components, whereas constructing a separator uniformly can require additional arithmetic information. The present paper isolates one form of that information and gives a deterministic splitting procedure once it is available. To supply it uniformly, we use the zero-free theorem for finite-order Hecke L-functions in the companion paper [21, Theorem 1.2]. We state that input precisely in Theorem 11.1 and prove its auxiliary-prime consequence here. The analytic theorem itself belongs to the companion.

The exponent is deliberately generous. The point is one fixed polynomial bound for all degrees and prime characteristics. We separate the algebraic construction from its analytic input in the following reduction.

1.1 The auxiliary-prime reduction

Put

For a prime q\le n, call a rational prime \ell an auxiliary prime for (p,q) if

Thus p is not a qth 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 1.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 1.2 does not use that theorem.

1.2 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.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, Section 4]. 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, Theorems A and D]. 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

This is an amortized result over primes [1, Theorem 1.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, Sections 4 and 6].

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.

1.3 Proof strategy

The Berlekamp algebra reduces complete factorization to splitting a monic square-free polynomial F all of whose roots already belong to \Fp. Write N=\deg F\ge2. The unknown roots are represented simultaneously by the finite algebra \Fp[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=\Fp(\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 \Fp^*. Here the q-primary subgroup consists of the elements whose orders are powers of q. These entries permit extraction of promised qth 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 \Fp, consider the smooth projective curve with affine equation

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 1.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.

2 Finite-field computations without known roots

The splitting procedures will manipulate all roots of a polynomial at once. Two elementary tools make this possible. First, a computation over a field can be executed in a product of fields until a zero test distinguishes two components. Second, a supplied generator of a primary multiplicative subgroup permits logarithms and root extraction by short digit calculations. We develop both tools explicitly, and then use them to split every totally split polynomial of even degree.

Finite fields are represented by a basis over their prime field and a multiplication table, or by an equivalent tower of polynomial quotients. Field arithmetic, binary powering, polynomial Euclidean algorithms, and linear algebra are therefore deterministic procedures with polynomial bit complexity in the representation lengths. All basis choices and pivot choices below use a fixed ordering. For a prime q and a positive integer m, write v_q(m) for its q-adic valuation. If k has cardinality Q and q\mid Q-1, its full q-primary subgroup is the unique subgroup of k^* of order q^{v_q(Q-1)}.

2.1 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

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.

2.2 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

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 (2.2). 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 (2.2); 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.

2.3 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.

2.4 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.

3 Auxiliary primes and primary generators

The splitting procedure needs explicit generators of small-prime parts of multiplicative groups. This section constructs those generators from the auxiliary primes supplied in Theorem 1.2. The construction uses linear algebra in cyclotomic algebras and calls the factorization procedure only in strictly smaller degrees. Existence of small auxiliary primes is a separate number-theoretic question; no size bound for them is assumed in this section.

We use the notation v_q(a) and the full q-primary subgroup introduced in Section 2.

Throughout the construction, p>n\ge2. For each prime q\le n, recall that the supplied auxiliary prime \ell_q satisfies

Recall the bound E=\max(2,\max_{q\le n}\ell_q) from Theorem 1.2. Supplied primes can be checked by trial division and modular exponentiation in time polynomial in E, n, and \log p. The same tests can search upward for the first suitable prime; if one exists below E, that search also takes time polynomial in these parameters. Factoring \ell_q-1 is unnecessary.

The table has the following contents:

• •

  for q=2, an element \omega_2\in\mathbb F_p^* of order 2^{v_2(p-1)};

• •

  for each odd prime q\le n, an explicitly represented field K_q/\mathbb F_p, an element \zeta_q\in K_q of order q with K_q=\mathbb F_p(\zeta_q), and an element \omega_q\in K_q^* of order q^{v_q(|K_q|-1)}.

An explicit field here consists of an \mathbb F_p-basis, its multiplication constants, and the coordinates of its identity. A quotient by a specified irreducible polynomial is an equivalent representation. Both descriptions support arithmetic and linear algebra in polynomial time. We use the standard structure theory of finite fields; see [17].

3.1 A degree-q field without factoring a cyclotomic polynomial

Fix q and \ell=\ell_q. Put

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 qth powers modulo \ell, and compute

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.

3.2 Extracting the primary generators

For q=2, solve the \mathbb F_p-linear equation

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

Thus c is a nonsquare. With s=v_2(p-1), set

The order of a nonsquare in a cyclic group of even order has the full 2-part of that order. The odd exponent in (3.3) therefore leaves \omega_2 of exact order 2^s.

For odd q, first factor

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

where \operatorname{ord}_q(p) is the multiplicative order of p modulo q. In particular \gcd(d_q,q)=1. The tensor product

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

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 (3.4) has a nonzero solution.

For odd q and Q_q\equiv1\pmod q, the lifting-the-exponent identity is

This is Equation (2.3). In particular v_q(Q_q^q-1)=s_q+1. Equation (3.4) 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

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.

3.3 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.

4 Divisions on a cyclic cover

The odd-degree splitting procedure will repeatedly divide divisor classes by 1-\sigma, where \sigma is a cyclic automorphism of a curve. Its first requirement is an existence statement: all the needed divisions must be rational over an extension of polynomial degree. Its second requirement is a test that eventually distinguishes two ramification points. We establish the geometric inputs here. The essential device is to retain a divisor supported at infinity together with a chosen division of its class in the Jacobian. Equality of classes may lose information about that divisor; retaining the divisor makes a final divisibility obstruction visible.

4.1 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

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

At z=0 the right side is 1, and its q roots are simple. There are therefore exactly q rational points at infinity,

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, Tags 0C1B and 0C1F] consequently gives

Let \sigma send (X,Y) to (X,\zeta Y) on points. We let it act on functions by

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

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

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

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, Theorem 1.1]. Multiplication by q, which is prime to the characteristic, is a surjective isogeny [18, Theorem 8.2]. Equation (4.4) then implies the surjectivity of multiplication by \lambda.

4.2 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, Section 6, Proposition 6.2]. 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

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 (4.7) 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 (4.6).

4.3 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 4.2 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.

4.4 Why the labels must separate ramification points

Set r=v_q(N) in Corollary 4.5 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 4.5 supplies the class d_m, and Proposition 4.6 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.

5 Divisor arithmetic without factoring supports

The lifting argument uses rational divisors, although the finite points in their supports are not given individually. We now give a representation in which addition, reduction, and evaluation require only polynomial arithmetic and linear algebra. Two further operations will be needed: summing divisors computed simultaneously at the unknown roots of F, and evaluating a principal function whose divisor has very large coefficients at infinity. Linear-algebra algorithms for Riemann–Roch spaces and divisor arithmetic are established tools; see Hess [13] and Khuri-Makdisi [16]. We give the representation and size bounds explicitly because both the genus and the degree of the cover vary in this application.

Throughout this section, k is a finite field, q is an odd prime different from its characteristic, k contains a specified primitive qth root \zeta, and F\in k[X] is monic and square-free of degree N\geq q, with q\mid N. We use the curve, automorphism, and rational points at infinity introduced above. Thus

The automorphism \sigma sends points by Y\mapsto\zeta Y and acts on functions by Y\mapsto\zeta^{-1}Y. All divisors in the computation are k-rational divisors, written as sums of closed points. For a divisor D, write

for its absolute degree. Bounds polynomial in \|D\| do not mean bounds polynomial in the bit length of arbitrary divisor coefficients. Large coefficients supported at infinity are treated separately at the end of this section.

We prove the proposition by constructing the algorithms. The final two subsections extend them to simultaneous sums and to binary infinity coefficients.

5.1 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

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

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 (5.2), 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

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 (5.2); 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.

5.2 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

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

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

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

To justify the degree bound, put

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 (5.5).

In this finite ansatz, membership in I(-D) is a subspace condition, and

is a list of linear conditions on Laurent coefficients. Expansions to the bound (5.4), 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, Tag 0BS6] gives \dim_kL(D+g\infty_0)\geq1. Choose a nonzero solution a by a fixed pivot convention and define

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 5.1. 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 (5.5) 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 5.1.

5.3 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.

5.4 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.

6 Solving the promised norm equations

Division of divisor classes will require a function with a prescribed norm. This section constructs such a function when its existence is known. The construction uses linear algebra and extraction of roots in finite reduced algebras, and its complexity is polynomial in the degree of the cover. In particular, the cover degree is not treated as a constant.

The characteristic bound is a convenient sufficient condition for the scalar searches in Lemma 2.2; the main algorithm satisfies it with considerable room. The roots of F need not be supplied, and the norm solver does not require F to split over k. The function automorphism \rho is the inverse of the action \sigma used in the divisor sections. Their powers run over the same cyclic group, so they define the same norm.

We first turn the norm equation into the problem of constructing a rank-one idempotent in an algebra. We then obtain that idempotent from spaces of matrices regular at the places of the rational function field. This use of intersections of maximal orders is closely related to the explicit matrix-algebra algorithms of Ivanyos–Kutas–Rónyai [14]. Their general algorithm permits a finite-field factorization oracle. Here the cyclic presentation allows the local orders to be written explicitly, and a fiber calculation supplies the idempotent by linear algebra. We give the construction and its bounds in full.

6.1 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

Its multiplication table in the basis

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 (6.2). 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

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 (6.3) 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 (6.3). Conjugation by Y and V shows that every nonidentity basis monomial has trace zero, while \operatorname{tr}(1)=q. Consequently

Here q is invertible by (6.1).

Unramified places with q\mid v(G). Suppose v is finite, v(F)=0, and w=v(G) is divisible by q. Set \widetilde V=T^{-w/q}V, and take the R_v-span of Y^a\widetilde V^b. Both Y and \widetilde V have unit qth powers, so this span is an order and contains the inverses of all its basis monomials. It is maximal. To see this, any larger order has integral matrix traces: its regular left-action trace is integral and equals q times matrix trace. Pairing an element of the larger order with the inverse basis monomials in (6.5) therefore makes all its coordinates integral. It already belongs to the displayed span. This description applies at all finite places outside the indicated finite set, with w=0.

Places ramified in \mathcal L. Suppose v(F)=1, and again put w=v(G). Since q is odd,

The commutation factor in taking the qth power is a power of \zeta^{q(q-1)/2}=1. The residue of u is a qth power in \kappa_v^*. Indeed the extension at v is totally ramified of degree q. For any promised solution h_0 one has v_{\mathcal L}(h_0)=v(G)=w, with v_{\mathcal L}(Y)=1. Hence h_0/Y^w is a unit, its norm is u, and the residue of that norm is the qth power of its residue.

Take a residue root and lift it by Hensel’s method to R\in R_v^* with R^q=u. On column vectors e_0,\ldots,e_{q-1} define

These matrices satisfy V'Y=\zeta YV', Y^q=F, and (V')^q=u. The distinct diagonal entries of V' give all diagonal matrix units by interpolation, and the invertible shift Y gives the remaining matrix units over K_v. Thus the model is an isomorphism to M_q(K_v). Let \mathcal A_v be the inverse image of M_q(R_v).

Unramified places with q\nmid v(G). Suppose v(F)=0 and q\nmid w=v(G). The residue of F must be a qth power. Otherwise, since \kappa_v contains \mu_q and q is prime, Y^q-\overline F is irreducible and defines an unramified extension of degree q. All its norm valuations are then divisible by q, contradicting the promise on G. Lift a residue root to S\in R_v^* with S^q=F. Use the matrices

Now VY=\zeta YV, including at the wrap from e_{q-1} to e_0. The same matrix-unit argument gives an isomorphism to M_q(K_v); again take the inverse image of M_q(R_v).

Infinity. Put z=X^{-1} and \widetilde Y=z^{N/q}Y. Then

There is a unique root S\in k[[z]] of S^q=F_\infty with S(0)=1. Use (6.8) with \widetilde Y in place of Y, and with the same weighted shift for V, whatever the valuation of G may be. The inverse image of M_q(k[[z]]) is \mathcal A_\infty. This model also specifies reduction to M_q(k) at infinity.

The matrix orders just used are maximal. For example, pairing with matrix units shows that any element in a larger order has integral matrix entries, using the integrality of matrix trace exactly as above. We have therefore specified maximal orders at every place, using only residue roots whose existence follows from the norm promise.

6.2 Why one fiber contains a rank-one matrix

Define the finite-dimensional k-algebra of global sections and its evaluation image by

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 (6.3). 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

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.

6.3 From the fiber idempotent to a norm solution

Lift the matrix a_0 of Lemma 6.4 to any b\in\mathcal S with \operatorname{ev}_\infty(b)=a_0. This is a linear solve once (6.9) 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

The primary decomposition for the relatively prime factors T^{q-1} and T-1 shows that

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 6.2 now recovers a norm solution by solving Ve=he over K_0.

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

6.4 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

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 (6.1), so derivative-based square-free decomposition has no inseparable residual case. Put

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 sth 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 qth power in every residue-field component by the norm promise. Lemma 2.2 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

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 (6.13) 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 (6.13), 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 6.5; 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 (6.9).

6.5 Algorithm and polynomial bounds

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

1. 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 2.2 and their needed precision by Hensel lifting.

2. 2.

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

3. 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 6.4.

4. 4.

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

5. 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

The number of unknowns in (6.13) 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 2.2; 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

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 10.1.

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 6.1 and completing its proof.

7 Effective division by 1-\sigma

The geometric argument supplies divisor classes that are divisible by \lambda=1-\sigma over the working field. We now construct a divisor representing such a division. Its only nonlinear instruction is the promised norm equation solved in Theorem 6.1. A ramification point fixes the otherwise undetermined constant in that equation.

The procedure consists of three steps.

1. 1.

   Compute j=h^+/h^- by Lemma 5.2. Put b=v_{X=x}(j) and normalize G=cj so that G/F^b has residue 1 at X=x.

2. 2.

   Use Theorem 6.1 to find a with \operatorname{Norm}(a)=G. Set E=D-\operatorname{div}(a), and form the coefficientwise maximum V of 0,E,E+\sigma E,\ldots,E+\cdots+\sigma^{q-2}E.

3. 3.

   Return \operatorname{ReduceDivisor}(V-(\deg V)P).

We prove first that the norm equation in the second step is solvable, and then that the maximum gives the required class division.

8 Splitting an odd number of roots

We now combine the geometry of Section 4 with the divisor algorithms. The input is a square-free polynomial already known to split into linear factors, but its roots are not given. Computation over its coordinate algebra treats all roots at once. If a scalar zero test behaves differently at two roots, it immediately produces a factor by Lemma 2.1. Proposition 4.6 supplies the reason that a distinction must occur. Our task here is to construct its input classes and perform its label tests within the promised bound.

8.1 The working field and the computational operations

Put

Construct

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

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

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

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 5.1 adds divisors, applies \sigma, and reduces a degree-zero divisor to an equivalent one of absolute degree at most 2g. Lemma 5.3 sums a simultaneously represented family across the components of A, without finding those components. Lemma 5.4 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 7.1 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

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.

8.2 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. 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. 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{8.4}

   Compute the integral infinity divisors

   W_t=\lambda^{-(t-1)}Ne, \qquad 1\le t\le m. \tag{8.5}

   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. 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{8.6}

   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 2.2 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{8.7}

   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.

8.3 Correctness and cost

9 From a splitting procedure to complete factorization

We now assemble the splitting procedures into an algorithm for an arbitrary nonzero polynomial over \mathbf F_p. The driver has two jobs: handle multiplicities without restrictions on the characteristic, and turn a reducible square-free polynomial into a totally split polynomial to which the earlier procedures apply. Its degree restrictions also explain why the primary table can be constructed in increasing order without circularity.

For a degree bound b, a primary table through b consists of a generator of the full 2-primary subgroup of \mathbf F_p^*, when b\ge2, and, for each odd prime q\le b, the field K_q/\mathbf F_p, the element \zeta_q of order q, and the full q-primary generator \omega_q constructed in Proposition 3.2. This is precisely the data consumed by the splitting procedures. All calls in this section are over \mathbf F_p, even when the splitting procedure itself uses an extension field.

9.1 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

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

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.

9.2 The recursive driver

Fix the degree n of the original input, put

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 2.3. If N is odd, use Proposition 8.1. 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. 1.

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

2. 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. 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. 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. 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. 6.

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

7. 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.

9.3 Preprocessing and the original input

The table restriction in Proposition 9.2 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 3.2 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 9.2 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

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 9.2 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.

10 Uniform bit complexity

We now charge the constructions to the dense binary input. The main point is that neither the degree of the curve nor the order of a primary subgroup is treated as a constant. A second issue is the large infinity divisor in the final label tests: its coefficients are stored in binary, and the corresponding functions are evaluated from circuits rather than expanded.

Throughout this section, B=20+(n+1)(L+1) is the parameter in Equation (1.1). We use dense polynomial arithmetic and ordinary Gaussian elimination. We first count bit operations with indexed arrays, charging for binary addresses as well as arithmetic, and then allow a quadratic overhead for a sequential bit implementation. The exponents below deliberately allow substantial slack; their purpose is to give one uniform bound.

Proposition 10.1 completes the uniformity assertion in Theorem 1.2. It also identifies precisely where a number-theoretic input can enter the running time: only the numerical sizes of the auxiliary primes remain outside the polynomial bounds in B for the algebraic splitting construction.

11 Small auxiliary primes from a uniform zero-free strip

It remains to construct the auxiliary primes in (1.2) with numerical sizes polynomial in n and \log p. We use the following result from the companion paper. Its proof is not part of this paper; all dependence on that paper is isolated in this input.

The uniform width is what matters for the application: a zero-free region whose width deteriorates with the field discriminant or the height would not give the bound below by the same calculation.

11.1 A uniform smoothed prime-ideal estimate

Fix a nonzero nonnegative function \varphi\in C_c^\infty((1,2)), and put

In particular \Phi(1)>0. For a number field M of degree d_M and absolute discriminant D_M, define

where \mathfrak p runs over nonzero prime ideals of its ring of integers.

11.2 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 11.1. Theorem 1.1 uses the cited theorem to supply the same input without that assumption.