================================================================================
DETERMINISTIC POLYNOMIAL FACTORIZATION OVER PRIME FIELDS
A complete, self-contained proof for a curious high-school student
================================================================================
Based on the research paper of the same title (OpenAI, October 2026).
This document proves every statement it uses. Nothing is deferred to
"the paper" or to "standard machinery" without a proof here.
Who this is for
---------------
You know what a polynomial is. You have seen prime numbers and
arithmetic modulo a prime. You may have seen a little linear algebra
(vectors, matrices, Gaussian elimination). You do NOT need to know
abstract algebra, algebraic geometry, or analytic number theory.
Every idea from those subjects is introduced and proved here.
What you will learn
-------------------
(1) The exact problem: given a prime p in binary and a nonzero
polynomial f over the field F_p of p elements, write f as a
constant times a product of powers of distinct monic irreducible
polynomials.
(2) Why the famous randomized algorithm (Cantor-Zassenhaus) is fast,
and why replacing randomness by explicit deterministic arithmetic
with a guaranteed bound polynomial in the bit length of the input
is genuinely hard.
(3) The full deterministic construction. It has three parts:
- an even-degree splitter that orients pairs of roots;
- an odd-degree splitter built on the curve Y^q = F(X), on
divisor classes, and on the fact that the operator
lambda = 1 - sigma is surjective on the Jacobian but
injective on the lattice of divisors at infinity;
- a norm solver that turns class division into linear algebra
over a cyclic algebra and its maximal orders.
(4) An analytic input that supplies small auxiliary primes: a
uniform zero-free strip for Hecke L-functions. The statement of
that theorem is quoted from the companion paper; its consequence
(small auxiliary primes exist) is proved here from the statement.
(5) The complete bit-complexity accounting, ending in one fixed
polynomial bound.
How to read this
----------------
Parts I and II are background: read them straight through. Parts
III to VII build the algorithm, one lemma at a time. Part VIII is
the complexity count. Part IX is the analytic input. Part X is
the recap of the whole proof. Every theorem has a proof immediately
after it. If you only want the shape of the argument, read the
statements; if you want to check it, read the proofs.
A note on notation
------------------
Everything is ASCII. We write F_p for the field of p elements, Z for
the integers, Q for the rationals, and Q(zeta_m) for the m-th
cyclotomic field. The letter q always denotes an odd prime dividing
a degree N. The letter ell always denotes an auxiliary rational
prime. The symbol sigma is the automorphism (X,Y) -> (X,zeta Y) of
the curve Y^q = F(X). The symbol lambda is 1 - sigma. The symbol N
can mean a degree; when it also means a kernel we rename the kernel
to N_tr. The symbol B is the master complexity parameter; the fiber
subalgebra is called B_fib.
--------------------------------------------------------------------------------
CONTENTS
--------------------------------------------------------------------------------
PART I. THE PROBLEM AND ITS BACKGROUND
1. What "factor a polynomial" means
2. Modular arithmetic and fields
3. Finite fields
4. Polynomial time and bit operations
PART II. THE CLASSICAL PICTURE
5. The randomized algorithm of Cantor and Zassenhaus
6. Why derandomization is hard
7. Berlekamp: factors as linear algebra
8. Reduction to the totally split case
PART III. TOOLS FOR COMPUTING AT UNKNOWN ROOTS
9. Simultaneous execution over a product of fields
10. Logarithms in primary subgroups
11. Root extraction in a reduced algebra (UnitRoot)
PART IV. SPLITTING AN EVEN NUMBER OF ROOTS
12. Pairs, orientation, and the tournament
13. The row-count argument formalised
PART V. THE ODD CASE: GEOMETRY
14. The curve Y^q = F(X)
15. Divisors, principal divisors, and the Jacobian
16. The operator lambda and the infinity lattice
17. The modules T_t and their filtration
18. Ramification labels
19. Frobenius and rational divisions
20. Forced separation of ramification points
PART VI. THE ODD CASE: COMPUTATION
21. Divisor arithmetic without known supports
22. Simultaneous sums and large-divisor evaluation
23. The promised norm solver: cyclic algebras
24. Maximal orders and local matrix models
25. Global sections and the fiber idempotent
26. Effective division by lambda
PART VII. THE FULL ALGORITHM
27. The odd splitter
28. Auxiliary table
29. The recursive driver
PART VIII. THE COMPLEXITY BOUND
30. Uniform bit complexity
PART IX. THE ANALYTIC INPUT
31. Small auxiliary primes from a uniform zero-free strip
PART X. EPILOGUE
32. Conclusion: the shape of the proof
================================================================================
PART I. THE PROBLEM AND ITS BACKGROUND
================================================================================
================================================================================
1. What "factor a polynomial" means
================================================================================
Fix a prime number p. The prime field F_p is the set {0,1,...,p-1}
with addition, subtraction, and multiplication performed modulo p,
and division by any nonzero element allowed (because p is prime).
A polynomial over F_p is an expression
f(X) = a_n X^n + a_{n-1} X^{n-1} + ... + a_1 X + a_0
with each coefficient a_i in F_p. The degree n is the largest index
with a_n nonzero. The leading coefficient is a_n.
Addition and multiplication of polynomials are the usual operations,
with coefficient arithmetic in F_p. Division with remainder works:
given f and a nonzero g, there are unique polynomials Q and R with
f = Q g + R and deg R < deg g.
A polynomial is irreducible if it has positive degree and cannot be
written as a product of two polynomials of smaller positive degree.
For example, over F_2 = {0,1}:
X^2 + X = X(X + 1) is reducible,
X^2 + 1 = (X + 1)^2 is reducible,
X^2 + X + 1 is irreducible.
Over F_7: X^2 - 2 = X^2 + 5 is reducible because 3^2 = 9 = 2 mod 7,
while X^2 - 3 = X^2 + 4 is irreducible because 3 is not a square
mod 7 (the squares mod 7 are 0,1,2,4).
THEOREM 1.1 (Unique factorization). Every nonzero polynomial f over
F_p has a factorization
f = c * g_1^{e_1} * g_2^{e_2} * ... * g_r^{e_r}
where c in F_p^* is the leading coefficient, the g_i are distinct
monic irreducible polynomials, and the e_i are positive integers.
This factorization is unique up to the order of the factors.
The proof is the same as for integers: repeated division with
remainder, using that the degree is a nonnegative integer that
decreases in every nontrivial factorization step.
THE PROBLEM. Input: a prime p written in binary, and a nonzero
polynomial f over F_p written as its list of n+1 coefficients
a_0,...,a_n, each in binary. Output: the constant c, the monic
irreducible polynomials g_i, and the multiplicities e_i.
The input size is the number of bits needed to write p and the
coefficients. If L = ceil(log_2 p) and n = deg f, that is about
(n+1) L bits. We want an algorithm whose running time is at most
P((n+1)L) for some fixed polynomial P, for every input.
A first easy observation. Every coefficient a_i lies in F_p, so its
binary length is at most L. The degree n is also part of the input.
When p is small (say p <= some huge bound that is a fixed polynomial
in n and L), we can in principle afford to enumerate all p residues.
The entire difficulty is when p is enormous compared with n: then an
algorithm polynomial in p is exponential in the input length.
================================================================================
2. Modular arithmetic and fields
================================================================================
For a prime p, F_p satisfies:
- addition, subtraction, multiplication are defined and associative,
commutative, distributive;
- 0 and 1 are neutral;
- every nonzero a has an inverse a^{-1} with a a^{-1} = 1, found by
the extended Euclidean algorithm on a and p.
FERMAT'S LITTLE THEOREM. For every a in F_p, a^p = a. For a nonzero,
a^{p-1} = 1.
Proof. If a = 0 it is clear. If a != 0, the map x -> a x permutes
F_p^*, so the product of all nonzero elements equals the product of
all a x, namely a^{p-1} times the same product. Cancel.
Corollary. The multiplicative order of a nonzero a, namely the
smallest k >= 1 with a^k = 1, divides p-1.
THE GROUP F_p^*. The nonzero elements form a group under
multiplication, of order p-1. A standard theorem says this group is
cyclic: there is an element g, called a generator or primitive root,
whose powers 1, g, g^2, ..., g^{p-2} list every nonzero element
exactly once. We will prove the cyclic structure for all finite
fields in Section 3.
THE FRESHMAN'S DREAM. In F_p, (a + b)^p = a^p + b^p.
Proof. Expand by the binomial theorem. The coefficient of a^k b^{p-k}
for 1 <= k <= p-1 is binom(p,k) = p!/(k!(p-k)!), whose numerator has
a factor p but whose denominator does not (since k < p and p-k < p
and p is prime). So the coefficient is divisible by p and vanishes
in F_p.
INDICATOR FUNCTION OF ZERO. For a in F_p, a^{p-1} is 1 if a != 0 and
0 if a = 0. Therefore 1 - a^{p-1} is the indicator of a = 0.
This indicator idea is used repeatedly: for an element z in a ring
over F_p in which z^{p-1} makes sense, the element z^{p-1} equals one
on components where z is nonzero and zero where z is zero, provided
the ring is a product of copies of F_p.
EXAMPLE. In F_7, the nonzero elements are 1,2,3,4,5,6. The squares
are 1^2=1, 2^2=4, 3^2=2, 4^2=2, 5^2=4, 6^2=1, so the set of squares
is {1,2,4}. A quadratic residue is a nonzero square; a quadratic
nonresidue is a nonzero element that is not a square. For p odd,
exactly half of F_p^* consists of residues, because the map x -> x^2
on F_p^* has kernel {1,-1} of size 2.
================================================================================
3. Finite fields
================================================================================
For a prime power Q = p^d there exists a field with Q elements, and
any two such fields are isomorphic. We denote it F_Q.
CONSTRUCTION. Take an irreducible polynomial h of degree d over F_p.
Then F_p[T]/(h(T)) is a field: every nonzero residue class modulo h
has an inverse by the extended Euclidean algorithm, because h is
irreducible and does not divide that class.
EXAMPLE. p = 3, h(T) = T^2 + 1. The polynomial T^2 + 1 is irreducible
over F_3 because -1 = 2 is not a square mod 3. The field F_9 consists
of residues a + bT with a,b in F_3 and T^2 = -1 = 2. Its nine
elements are 0,1,2,T,2T,1+T,1+2T,2+T,2+2T.
STRUCTURE THEOREM 3.1. Let Q = p^d.
(a) F_Q is a vector space of dimension d over F_p, hence has Q
elements.
(b) The multiplicative group F_Q^* is cyclic of order Q - 1.
(c) F_Q contains F_p as the set of elements fixed by x -> x^p.
(d) If F_Q and F_R have the same characteristic p, then F_Q is a
subfield of F_R if and only if Q divides R.
Proof of (b). Let Q - 1 = q_1^{s_1} ... q_t^{s_t} be the prime
factorization. For each prime q_i, the polynomial X^{(Q-1)/q_i} - 1
has at most (Q-1)/q_i roots, which is fewer than Q-1, so there is an
element a_i in F_Q^* whose order does not divide (Q-1)/q_i. The order
of a_i therefore contains the full power q_i^{s_i}. The product
g = a_1 ... a_t has order Q - 1: if its order misses a factor q_i,
then g^{(Q-1)/q_i} = 1, and since the other a_j have orders coprime
to q_i, this forces a_i^{(Q-1)/q_i} = 1, contradiction. So g is a
generator.
Proof of (c). Fermat gives a^p = a for a in F_p. Conversely, if
a^p = a then a is a root of X^p - X, which has at most p roots, and
all p elements of F_p are roots; so a lies in F_p.
Proof of (d). If F_Q is a subfield of F_R, then F_R is a vector space
over F_Q, so R = Q^m and Q divides R. Conversely, if Q divides R,
then X^Q - X divides X^R - X (because Q | R), so the roots of
X^Q - X, which form F_Q, lie inside the roots of X^R - X, which form
F_R.
FROBENIUS. The map Phi: x -> x^p on F_Q is a field automorphism: it
preserves sums by the Freshman's Dream and products trivially, and
it is injective because a field has no zero divisors. Its fixed field
is F_p by (c). Its powers Phi^j: x -> x^{p^j} are also automorphisms.
REPRESENTING EXTENSION FIELDS EXPLICITLY. In the algorithm, every
extension field used is represented by a basis over F_p together with
a multiplication table, or equivalently as F_p[T]/(h) for an explicit
irreducible h. Either way, addition, multiplication, inversion, and
linear algebra over the field are deterministic procedures whose
bit cost is polynomial in the representation length. We use this
without further comment.
THE SUBFIELD OF FIXED POINTS. If an automorphism of a finite field
has order m, its fixed field has size p^r where r = d/m if m divides
d. This follows because the fixed field is F_{p^r} where r is the
degree over F_p, and the automorphism group of F_Q over F_p is cyclic
of order d generated by Frobenius. We will use only the special case
of Frobenius itself.
================================================================================
4. Polynomial time and bit operations
================================================================================
The input is a prime p in binary (L = ceil(log_2 p) bits) and a list
of n+1 coefficients, each an integer in [0,p-1]. The total bit length
is at most (n+1)L plus a few bits for n and L. We write
B = 20 + (n+1)(L+1)
so B is at least the input bit length and at most a fixed multiple
of it.
An algorithm is polynomial time if its running time on every input is
at most B^C for some absolute constant C. The exponent C must not
depend on p, n, L, or any other input parameter.
BIT OPERATIONS. We count bit operations, not field operations. A
field operation in F_p costs O(L^2) bit operations by schoolbook
arithmetic, or O(L log L log log L) with fast multiplication. For
simplicity we use schoolbook bounds and then allow generous slack in
the exponent. Multiplication of two polynomials of degree at most d
over F_p costs O(d^2) field operations, i.e. O(d^2 L^2) bit
operations. Gaussian elimination on an s by s matrix costs O(s^3)
field operations.
EXPONENTIATION. To compute a^k with k a positive integer written in
binary, use repeated squaring: O(log k) multiplications. So a^k is
computable in polynomial time in the bit lengths of a and k.
THE FORMAL DERIVATIVE. For f = sum a_i X^i, define
f' = sum i a_i X^{i-1}, where i is reduced modulo p. The usual rules
(f+g)' = f' + g' and (fg)' = f'g + fg' hold. If f = g^p, then f' = 0
because every exponent in g^p is a multiple of p, so the formal
derivative of X^{p m} is p m X^{p m - 1} = 0 in F_p.
THE GCD. For two polynomials f, g over a field, the greatest common
divisor gcd(f,g) is computable by the Euclidean algorithm in
polynomial time. It is monic by convention. If gcd(f,g) = 1, they
are coprime.
THE CHINESE REMAINDER THEOREM. If h_1,...,h_r are pairwise coprime
polynomials, then
F_p[X]/(h_1 ... h_r) is isomorphic to F_p[X]/(h_1) x ... x F_p[X]/(h_r)
as rings, by a(X) -> (a mod h_1, ..., a mod h_r). The inverse map is
computed by the extended Euclidean algorithm. In particular, if h is
square-free with factorization h = h_1 ... h_r, we may compute in
the product ring without knowing the factors: an element is just a
polynomial modulo h.
THE KEY ISSUE. We will often want to "compute at all roots of F at
once" without knowing the roots. The ring A = F_p[T]/(F) is
isomorphic to a product of copies of F_p (one per root) when F is
totally split. An operation in A is a simultaneous operation on all
roots. A zero test in A, implemented by gcd with F, either confirms
that an element is nonzero at every root, or returns a proper factor
of F. This is the engine of the whole algorithm, formalised in
Section 9.
================================================================================
PART II. THE CLASSICAL PICTURE
================================================================================
================================================================================
5. The randomized algorithm of Cantor and Zassenhaus
================================================================================
We describe the algorithm that made finite-field factorization a
practical routine. Understanding it clarifies exactly what the
deterministic construction must replace.
ALGORITHM CZ(f, p). Input: monic f in F_p[X].
Step 1. If f' = 0, write f(X) = g(X^p) and recursively factor g,
multiplying multiplicities by p.
Step 2. Compute d = gcd(f, f'). If d != 1, recursively factor d
and f/d, and merge the two factor lists.
Step 3. Now f is square-free. Pick c uniformly at random in F_p.
Compute
g = gcd(f(X), (X + c)^{(p-1)/2} - 1)
over F_p. Here p is odd.
If 1 < deg g < deg f, recursively factor g and f/g and merge.
Otherwise pick a new c and repeat.
When p = 2, use the trace map instead; we treat p odd here.
WHY STEP 3 SPLITS. Suppose f is totally split with distinct roots
x_1, ..., x_N in F_p. For a chosen c, Euler's criterion says
(x_i + c)^{(p-1)/2} equals 1 if x_i + c is a nonzero square, equals
-1 if x_i + c is a nonsquare, and equals 0 if x_i + c = 0. So g is
the product of X - x_i over those i for which x_i + c is a nonzero
square. In particular g is a proper factor whenever some roots give
square and some give nonsquare (or zero).
THE PAIR SEPARATION LEMMA. Fix two distinct roots x_i != x_j. Among
the p choices of c in F_p, all but at most two make both x_i + c and
x_j + c nonzero, and among those, exactly half have
(x_i + c)/(x_j + c) a nonzero square.
Proof. Exclude the two values c = -x_i and c = -x_j. For the other
p - 2 values, put y = x_j + c, which ranges over F_p minus two
elements. The ratio (x_i + c)/(x_j + c) = 1 + (x_i - x_j)/y. As y
ranges over F_p minus {0, x_i - x_j}, the quantity (x_i - x_j)/y
ranges over F_p minus {0, 1}, so the ratio ranges over F_p minus
{1, 0}. Exactly half of the p - 2 remaining values of the ratio are
squares (the map r -> r^2 has two preimages per nonzero square). So
at least (p-3)/2 values of c separate the pair.
CONSEQUENCE. Pick c at random. Each fixed pair of roots is separated
with probability at least 1/2 - O(1/p). By linearity of expectation,
after O(N^2) independent choices of c, every pair is separated with
probability at least 1/2. Repeating the whole procedure a constant
number of times gives a factor with probability at least 3/4. The
expected number of trials is O(N^2), and each trial costs a
polynomial-time gcd and exponentiation. So the expected running time
is polynomial in n and L.
Steps 1 and 2 reduce an arbitrary f to a product of square-free
polynomials. Step 3 then recursively splits each square-free factor.
The total expected work is polynomial in the input bit length.
THE DEFECT. The bound is on EXPECTED time. On a rare unlucky run the
algorithm may take much longer. Worse for our purpose, the argument
gives no way to choose c deterministically without trying many
candidates. If p is astronomically large, trying even a polynomial
number of candidates requires a deterministic rule that is guaranteed
to work; no such rule is known of the simple form "test c = 0,1,2,...".
The whole difficulty is to construct, without sampling, an element
that behaves like a random c for every possible f.
================================================================================
6. Why derandomization is hard
================================================================================
The C-Z algorithm depends on an inequality: for some c, the values
x_i + c and x_j + c have different quadratic characters. Over a
large prime field, such a c exists in abundance, but writing one down
explicitly requires knowing something about the unknown roots x_i.
The deterministic results before the paper under discussion fall into
two families.
(A) POLYNOMIAL IN p BUT NOT IN log p. Berlekamp's original algorithm
searches for a nonscalar element of the Berlekamp algebra by
trying scalars one at a time. That is correct and deterministic,
but it can require up to p trials. Since p has L bits, p is
exponential in the input length.
(B) POLYNOMIAL UNDER HYPOTHESES. Under the generalized Riemann
hypothesis, Ronyai and Evdokimov obtained deterministic bounds.
Shoup obtained a deterministic bound polynomial in n and
p^{1/2+o(1)}. These results show that the problem is not
inherently exponential, but they do not give a uniform polynomial
bound in (n+1)L without a hypothesis.
THE PRESENT RESULT. The paper we are explaining proves, without any
hypothesis, that there is a deterministic algorithm with running
time at most B^C for an absolute constant C (in fact the paper's
explicit exponent is about 10^12). It combines:
- Berlekamp's reduction of factorization to finding a nonscalar
element of a finite-dimensional algebra;
- a completely explicit construction of such an element when the
number of roots is even, using the 2-primary part of F_p^* and a
tournament;
- a geometric construction when the number of roots is odd, using
the curve Y^q = F(X), divisor classes, and an obstruction in the
lattice of divisors supported at infinity;
- a norm solver, which turns the geometric class-division problem
into linear algebra over a cyclic algebra;
- an analytic input, which guarantees that small auxiliary primes
exist so that the needed roots of unity and primary generators can
be constructed.
The rest of this document develops each piece and proves it.
================================================================================
7. Berlekamp: factors as linear algebra
================================================================================
Let h in F_p[X] be monic and square-free of degree d >= 1. Define
R_h = F_p[X] / (h(X)),
the ring of polynomials modulo h. Since h is square-free, the Chinese
remainder theorem gives an isomorphism
R_h -> F_p[X]/(h_1) x ... x F_p[X]/(h_r)
where h = h_1 ... h_r is the factorization of h into distinct monic
irreducibles. Each factor F_p[X]/(h_i) is a finite field F_{p^{d_i}}
with d_i = deg h_i.
THE BERLEKAMP ALGEBRA. Define
B_h = { a in R_h : a^p = a }.
This is an F_p-vector subspace of R_h, because a -> a^p is F_p-linear
(Freshman's Dream) and the equation a^p - a = 0 is linear over F_p.
THEOREM 7.1. dim_{F_p} B_h = r, the number of distinct irreducible
factors of h. In particular, h is irreducible if and only if
dim B_h = 1.
Proof. In the product description, an element a corresponds to a
tuple (a_1, ..., a_r) with a_i in F_{p^{d_i}}. The equation a^p = a
is equivalent to a_i^p = a_i in each component. By Theorem 3.1(c),
the solutions of x^p = x in a finite field of characteristic p are
exactly the elements of F_p. So B_h corresponds to F_p^r, which has
dimension r.
COMPUTING B_h. The map Frob: a -> a^p on R_h is F_p-linear. Its
matrix in the standard basis 1, X, ..., X^{d-1} is obtained by
computing X^{i p} mod h for i = 0,...,d-1 (by repeated squaring),
expressing each as a polynomial of degree < d, and reading off
coefficients. The kernel of Frob minus the identity is B_h, found by
Gaussian elimination on a d by d matrix over F_p. The cost is
polynomial in d and L.
SPLITTING WITH A NONSCALAR ELEMENT. Suppose dim B_h = r >= 2.
Choose an element b in B_h that is not in the one-dimensional
subspace F_p * 1. Then b corresponds to a tuple (b_1,...,b_r) of
elements of F_p that is not constant. So there are two indices with
b_i != b_j. For any a in F_p, the element b - a in R_h vanishes at
exactly those roots x_i with b_i = a. Consequently
gcd(h(X), b(X) - a)
is the product of X - x_i over the indices with b_i = a. Choosing a
to be one of the attained values b_i gives a nonconstant proper
divisor of h. Choosing a not attained gives 1. So testing a over the
set of attained values splits h.
THE DIFFICULTY. In the small-prime case, the number of candidate
values a is at most p, and enumerating them is polynomial in the
input length when p <= B^{200000}. In the large-prime case, p is
astronomical, and we need a different source of a nonscalar element
b that is guaranteed to take at least two distinct values on the
roots. That is where the even and odd splitters enter.
================================================================================
8. Reduction to the totally split case
================================================================================
Once h is square-free, we want to produce a totally split polynomial
F_t (all roots in F_p) of degree r = dim B_h, together with a rule
that turns any nontrivial factor of F_t into a nontrivial factor of h.
The following lemma, from the paper's driver section, does exactly
that. It replaces the classical distinct-degree decomposition by a
single linear-algebra construction.
LEMMA 8.1 (Separating element). Let h in F_p[X] be monic and
square-free of degree d, let r = dim B_h >= 2, and suppose p > r^3.
Let b_0, ..., b_{r-1} be any ordered F_p-basis of B_h. For t in F_p,
put
b(t) = b_0 + t b_1 + ... + t^{r-1} b_{r-1} in B_h,
and let F_t(Y) be the characteristic polynomial of multiplication by
b(t) on the F_p-vector space B_h (a monic polynomial of degree r in
the variable Y). Then:
(a) for some t in {0, 1, ..., r^3}, the polynomial F_t is monic,
square-free, and totally split over F_p (all r roots in F_p);
(b) for any such t and any nontrivial proper monic divisor S of
F_t, the element S(b(t)) in R_h has gcd with h equal to a
nontrivial proper divisor of h.
Proof of (a). Identify B_h with F_p^r by sending a to its tuple of
values at the roots. Under this identification, multiplication by
b(t) on B_h is diagonal, with diagonal entries b_1(t), ..., b_r(t),
where b_i(t) = b_{i,0} + t b_{i,1} + ... + t^{r-1} b_{i,r-1} is the
i-th coordinate of b(t). Its characteristic polynomial is
F_t(Y) = prod_{i=1}^r (Y - b_i(t)).
So F_t is always totally split. It fails to be square-free exactly
when b_i(t) = b_j(t) for some i != j. For fixed i != j, the
difference b_i(t) - b_j(t) is a polynomial in t of degree at most
r-1. It is not identically zero: if it were zero for all t, then the
two coordinate functionals a -> a_i and a -> a_j would agree on
every basis vector b_0,...,b_{r-1}, hence on all of B_h, which is
impossible since the tuple map is an isomorphism. A nonzero polynomial
of degree at most r-1 has at most r-1 roots. There are at most
binom(r,2)(r-1) < r^3 pairs and bad values combined. Since p > r^3,
the field has more than r^3 elements, so some t in {0,...,r^3} is
good.
Proof of (b). Let S be a nontrivial proper monic divisor of F_t. Its
roots form a nonempty proper subset J of {1,...,r}. The element
S(b(t)) in B_h has i-th coordinate S(b_i(t)), which is zero exactly
when b_i(t) is a root of S, i.e. exactly when i lies in J. So the
gcd of h with S(b(t)), which selects exactly the roots of h at which
S(b(t)) vanishes, is the product of X - x_i for i in J. This is
nonempty and proper because J is.
COST. The matrix of multiplication by each b_j is computed from
polynomial arithmetic modulo h. The characteristic polynomial F_t is
computed as a determinant of a matrix of size r with entries in F_p,
using O(r^3) field operations. The search over t tries at most
r^3 + 1 values and tests gcd(F_t, F_t') for square-freeness.
THE ROLE OF THIS LEMMA. In the large-characteristic branch, the
factorization driver (Section 29) does the following. Given a
square-free h with r = dim B_h >= 2, it computes b_0,...,b_{r-1},
finds a good t by testing t = 0,1,...,r^3, and applies a
splitter (even or odd, depending on r) to F_t. The splitter returns
a nontrivial proper factor S of F_t over F_p. By the lemma,
gcd(h, S(b(t))) is a nontrivial proper factor of h. Recursion on the
two pieces terminates because degrees strictly decrease. No
distinct-degree decomposition is needed.
IMPORTANT RESTRICTION. The splitter is only used on polynomials that
are monic, square-free, and totally split over F_p. The lemma
converts any square-free h into such an F_t of degree r, provided
p > r^3. In the large-characteristic branch p > B^{200000} > n^3 >= r^3,
so the hypothesis always holds.
================================================================================
PART III. TOOLS FOR COMPUTING AT UNKNOWN ROOTS
================================================================================
================================================================================
9. Simultaneous execution over a product of fields
================================================================================
The splitters manipulate all roots of a square-free totally split
polynomial F at once. This section states and proves the principle
that makes this legitimate.
SETUP. Let k be an explicitly represented finite extension of F_p.
Let F in F_p[T] be monic, square-free, and totally split, of degree
N. Write its roots (which exist in F_p, hence in k) as x_1,...,x_N.
The algebra
A = k[T]/(F(T))
is isomorphic to k x ... x k (N copies) by
a(T) -> (a(x_1), ..., a(x_N)).
An element a of A is stored as a polynomial of degree < N with
coefficients in k. Addition and multiplication in A are polynomial
arithmetic modulo F.
LEMMA 9.1 (Simultaneous execution). Suppose a deterministic procedure
uses only:
(i) field arithmetic in k and in A;
(ii) zero tests on elements of A;
(iii) integer control flow (comparisons, loops, choices of pivots);
and suppose that at component i its scalar inputs are obtained by
specializing given elements of A at T = x_i. Assume the procedure is
defined for every specialized input. Then one of two things happens:
(a) the procedure executes on all N components with a common
sequence of decisions; or
(b) it returns a nontrivial proper monic divisor of F in F_p[T].
The extra cost of each scalar operation or zero test is polynomial in
N, [k:F_p], and log p.
Proof. We show how to simulate the procedure without knowing the
roots. Arithmetic in A is already available. For a zero test on
a in A, compute d = gcd(F, a) over k. Since F is monic in F_p[T] and
a has coefficients in k, this gcd is computed by the Euclidean
algorithm. Because F is square-free and splits into linear factors
T - x_i, the gcd is the product of T - x_i over those i for which
a(x_i) = 0. There are three cases:
- d = 1: a(x_i) != 0 for every i;
- d = F: a(x_i) = 0 for every i;
- otherwise: d is a nontrivial proper divisor of F. Although the
computation runs over k, the polynomial d has coefficients in
F_p, because it is the product of linear factors T - x_i with
x_i in F_p. So d is a legitimate output.
Invert a nonzero element only after the zero test has shown it
nonzero in every component. The extended Euclidean algorithm on a
and F then gives its inverse modulo F. Similarly, a polynomial
degree test or a pivot choice is a sequence of zero tests on
coefficients; each such test either agrees across components or
returns a factor.
Consequently, until a factor is returned, every instruction and every
decision is valid in every component. The number of operations is the
number of simulated operations times the cost of arithmetic and gcds
in A, which is polynomial in the stated parameters.
REMARK. The same argument applies to nested procedures whose
coefficient field is itself being simulated by A. It also applies
when A has been replaced by a direct summand eA with a known
idempotent e: the identity of the summand is e, and a zero test in
the summand uses a mask as described in Section 12.
================================================================================
10. Logarithms in primary subgroups
================================================================================
Let q be a prime. Let u generate a cyclic group of order q^s. For any
element a = u^ell with ell in [0, q^s), we want to recover ell.
LEMMA 10.1 (Digit extraction). Write ell = c_0 + c_1 q + ... + c_{s-1}
q^{s-1} with 0 <= c_j < q. Set ell_0 = 0 and ell_j = c_0 + ... +
c_{j-1} q^{j-1}. Then for 0 <= j < s, the digit c_j is the unique
element of {0,...,q-1} satisfying
(a u^{-ell_j})^{q^{s-j-1}} = (u^{q^{s-1}})^{c_j}.
Proof. Write ell - ell_j = q^j (c_j + q v) for some integer v. Raise
a u^{-ell_j} = u^{ell - ell_j} to the power q^{s-j-1}:
(u^{ell - ell_j})^{q^{s-j-1}}
= u^{q^{s-j-1} q^j (c_j + qv)}
= u^{q^{s-1} (c_j + qv)}
= (u^{q^{s-1}})^{c_j} * (u^{q^s})^v
= (u^{q^{s-1}})^{c_j},
because u^{q^s} = 1. The right side depends only on c_j modulo q, and
the element u^{q^{s-1}} has order exactly q. So exactly one c_j in
{0,...,q-1} satisfies the equation.
COST. s digits, each tested against q possible values, so q s
equality tests. No enumeration of the q^s elements of the group is
needed.
PRODUCTS OF FIELDS. Suppose A = k[X]/H is a square-free algebra,
and u has order q^s in every field component. We compute the
logarithms component by component without splitting H. At each
digit level j, running the q candidates c = 0,...,q-1 in parallel
means taking gcds
gcd(H, (a u^{-ell_j})^{q^{s-j-1}} - (u^{q^{s-1}})^c).
Each nonempty gcd is the product of those linear factors of H where
the equality holds, and becomes a new piece carrying its own
accumulated ell. At most deg H pieces exist at each level. Recombine
final pieces by polynomial CRT. When some components have already
been masked off by idempotents, replace gcds with the mask operation
e_0 - (e_0 z)^{p-1} (indicator of z = 0). Both implementations are
used below (Section 11 and Section 13).
================================================================================
11. Root extraction in a reduced algebra (UnitRoot)
================================================================================
We will need: given a unit a in a square-free algebra k[X]/H that is
promised to be a q-th power, construct a q-th root explicitly, with
polynomial bit cost, without factoring H. This is UnitRoot.
LEMMA 11.1 (Root extraction from a primary generator). Let k be an
explicit finite field of cardinality Q and characteristic p. Let q
be an odd prime dividing Q - 1, let zeta in k have order q, and let
omega in k generate the full q-primary subgroup of k^*. Let
H in k[X] be monic, square-free, of degree h >= 1. Suppose p > h^2.
Given a unit a in k[X]/H promised to be a q-th power, one can
deterministically construct b with b^q = a. Bit cost is polynomial
in q, h, and the length of the field representation. The procedure
uses only arithmetic and zero tests over k, so it admits
simultaneous execution.
Proof. Three steps: separate extension degrees, get a primary
generator on each part, and split into two coprime factors.
STEP 1 (separate extension degrees). For d = 1,...,h, form
H_d = product of distinct irreducible factors of H of degree d,
using gcds with X^{Q^d} - X, after removing factors already found
for smaller degrees. Powers are computed modulo the current modulus
by binary powering. Every component of k[X]/H_d is a field of
cardinality Q^d. Write Q^d - 1 = q^s * t with q coprime to t; only
division by the specified prime q is needed to find s and t.
STEP 2 (primary generator on each part). For odd q dividing Q-1,
the lifting-the-exponent identity is
v_q(Q^d - 1) = v_q(Q - 1) + v_q(d). (11.1)
Proof of (11.1). If y = 1 + c q^m with q coprime to c and m >= 1,
then raising to any exponent n prime to q preserves v_q(y^n - 1) =
m, because the linear term n c q^m dominates. Raising to the q-th
power gives
(1 + c q^m)^q = 1 + q c q^m + binom(q,2) c^2 q^{2m} + ...,
and q c q^m has q-valuation m+1, while binom(q,2) c^2 q^{2m} has
valuation 2m+1 (since binom(q,2) = q(q-1)/2, so binom(q,2) has
v_q = 1) and higher terms have valuation >= 2m+1 (at least m+2 when
m >= 1). Since q is odd and m >= 1, m+1 < 2m+1 when m >= 1;
strict dominance holds and v_q((y^q) - 1) = m + 1. Iterating from
y = Q gives (11.1).
If q does not divide d, set u = omega in k[X]/H_d. This element,
living in the base field k, has order q^{v_q(Q-1)} = q^s in every
component (by 11.1 with v_q(d) = 0). If q divides d, solve the
k-linear system
v^{Q^{d/q}} = zeta * v (v in k[X]/H_d). (11.2)
Nonzero solutions exist in each field component: the cyclic group
of order Q^d - 1 contains a solution of v^{Q^{d/q} - 1} = zeta,
because zeta^{(Q^d - 1)/(Q^{d/q} - 1)} = 1 (zeta is already in the
subfield k ⊆ field of order Q^{d/q}, so zeta^{Q^{d/q} - 1} = 1, and
the exponent M = (Q^d - 1)/(Q^{d/q} - 1) = 1 + Q^{d/q} + ... +
Q^{q(d/q)} - ... satisfies zeta^M = 1 because Q^{d/q} ≡ 1 mod q
forces each term Q^{i d/q} ≡ 1 mod q as well). For such a nonzero
solution v, (11.1) shows v_q(order of v) = s.
To choose a solution nonzero in every component without knowing the
components, take a kernel basis v_0,...,v_{r-1} of the linear map
v -> v^{Q^{d/q}} - zeta v, with r <= h, and try
v(c) = sum_{j=0}^{r-1} c^j v_j, c = 0,...,h^2. (11.3)
Test each candidate for being a unit by gcd(H_d, v(c) as polynomial).
In any one component at most r-1 <= h-1 values of c make v(c) zero
there. With at most h components, fewer than h^2 values are excluded
altogether. The hypothesis p > h^2 ensures enough distinct scalars
exist. Raising this v to the t = (Q^d - 1)/q^s power gives a
generator u of order q^s in every component.
STEP 3 (take the root). Use the integer CRT for q^s and t to
project a into its primary and prime-to-q parts:
a_q = a^{t * (t^{-1} mod q^s)},
a_t = a^{q^s * ((q^s)^{-1} mod t)} (a_t = 1 if t = 1).
Then a = a_q a_t with order(a_q) | q^s and order(a_t) | t. A root
of a_t is obtained by raising to the q^{-1} mod t power (1 if t = 1).
Compute the logarithm of a_q to u by the digit procedure of Section
10, partitioning H_d as necessary. In each surviving piece the
logarithm ell in [0, q^s) is divisible by q, because a is a q-th
power. Therefore u^{ell/q} is a root of a_q on that piece. Multiply
the two roots (primary part and prime-to-q part), recombine pieces
by polynomial CRT, and finally recombine the relatively prime H_d.
Cost. d <= h, the bit length of Q^d is at most 1 + h log_2 Q,
and s <= h log_2 Q. Digit work touches at most h nonempty pieces,
each with at most q digit candidates. Eigenvector system dimension
at most h. Unit search at most h^2 + 1 trials. Everything else is
polynomial arithmetic, powering, or integer GCD. This proves the
claim. []
We denote this procedure by UnitRoot. To extract a root in k itself,
apply it with the linear modulus H = X.
================================================================================
PART IV. SPLITTING AN EVEN NUMBER OF ROOTS
================================================================================
================================================================================
12. Pairs, orientation, and the tournament
================================================================================
Let F in F_p[X] be monic, square-free, totally split, of even degree
N >= 2, and let p > N. The N roots x_1,...,x_N are unknown to us;
we are given u generating the full 2-primary subgroup of F_p^*.
THE TOURNAMENT IDEA. For each unordered pair {i,j} with i != j, we
want to choose an orientation i -> j or j -> i, without knowing the
roots, so that the resulting "out-degrees" c_1,...,c_N are not all
equal. If we can do that, some c_i differs from some c_j, and since
0 <= c_i <= N-1 < p, we get a factor by gcd(F, c - a) for a value a
that c takes on some but not all roots.
ORIENTING VIA A QUADRATIC CHARACTER. Write p - 1 = 2^s * t with t
odd and s >= 1. Euler's criterion says that z in F_p^* has 2-primary
logarithm ell = 0 (if z is a quadratic residue) or ell = 2^{s-1}
(if z is a nonresidue), where the logarithm is measured against the
fixed generator u of the 2-primary subgroup.
Consider the ordered pair (i,j). Its "sign" z_{ij} = x_i - x_j is a
nonzero element of F_p (in fact F_p-embedded in the algebra below).
Reversing the pair gives z_{ji} = -z_{ij}, which is a residue iff
z_{ij} is a nonresidue, since -1 = u^{2^{s-1}} is a nonresidue.
So orient i -> j iff x_i - x_j is a QR. Exactly one of the two
orders of each {i,j} is "the arrow".
IMPLEMENTATION WITHOUT ROOTS. Work in A = F_p[T]/F, so that we can
manipulate all N roots at once. In the algebra R = A (x)_{F_p} A,
the element
Delta = T (x) 1 - 1 (x) T
has coordinate x_i - x_j on the component indexed by the ordered
pair (i,j). Then
e = Delta^{p-1}
is the idempotent equal to 1 on off-diagonal components (i != j)
and to 0 on diagonal components (i = j). Work in eR, whose identity
is e. The element Delta^t has 2-power order in every off-diagonal
component:
(Delta^t)^{2^s} = Delta^{t 2^s} = Delta^{p-1} = e.
So the digit procedure of Section 10 produces a logarithm
ell_{ij} in [0, 2^s) at each off-diagonal pair, satisfying
(x_i - x_j)^t = u^{ell_{ij}}.
Now for the swapped pair (j,i): the coordinate of Delta^t is
-(x_i - x_j)^t = -u^{ell_{ij}}, and -1 = u^{2^{s-1}}, so
ell_{ji} = ell_{ij} + 2^{s-1} (mod 2^s).
Exactly one of ell_{ij}, ell_{ji} lies in the range [0, 2^{s-1})
(if ell_{ij} is in the lower half, so is one; if in the upper half,
the subtraction 2^{s-1} brings it down and reverses the roles).
Let e_* be the sum of the final masks of the digit procedure whose
logarithm lies in [0, 2^{s-1}). Then e_* is an idempotent in eR
selecting exactly one orientation of each unordered pair.
Extracting row counts. Apply the ordinary algebra trace on the
second factor:
c = (id_A (x) Tr_{A/F_p})(e_*) in A.
The i-th coordinate of c is the number c_i of surviving orientations
(i,j) in row i, viewed in F_p. Because each unordered pair
contributed exactly one survivor, all positive contributions are
integer counts with
0 <= c_i <= N - 1, sum_i c_i = N(N-1)/2.
The sum is exactly the number of unordered pairs.
If all c_i were equal to c_0, then N c_0 = N(N-1)/2, so
c_0 = (N-1)/2. For N even this is a half-integer, contradiction.
Hence some c_i differs from some c_j. Since all c_i are integers in
[0, N-1] < p, the images in F_p are not all equal.
================================================================================
13. The row-count argument formalised
================================================================================
PROPOSITION 13.1 (Even-degree splitting). Let p be odd, and let F
in F_p[T] be monic, square-free, totally split of even degree N >= 2
with p > N. Given a generator u of the full 2-primary subgroup of
F_p^*, one can deterministically find a nontrivial proper monic
divisor of F over F_p in a number of bit operations polynomial in N
and log p.
Proof. Set A = F_p[T]/F and R = A (x)_{F_p} A, so R has dimension
N^2 over F_p. Write p - 1 = 2^s t with t odd.
(a) Delta^{p-1} is off-diagonal. In R, in the coordinate description
by ordered pairs (i,j), Delta has coordinate x_i - x_j. On the
diagonal (i = j) it is zero. Off the diagonal (i != j) it is a
nonzero element of F_p, so (x_i - x_j)^{p-1} = 1. Hence
e = Delta^{p-1} is the idempotent supported on off-diagonal
components. Work in eR: identity is e; multiplication is inherited
from R and stays in eR (since ex = e(e x) for x in eR).
(b) Delta^t has 2-power order in eR. (Delta^t)^{2^s} = Delta^{p-1}
= e. So Delta^t is in the 2-primary part of (unit group of eR). The
digit procedure of Section 10 recovers, on each off-diagonal
component, the unique ell_{ij} in [0, 2^s) such that
(x_i - x_j)^t = u^{ell_{ij}}.
(c) Swapping reverses the digit. For (j,i), Delta^t has coordinate
(x_j - x_i)^t = (-(x_i - x_j))^t = -(x_i - x_j)^t because t is odd.
The negative of an element of u-generated group is u^{ell + 2^{s-1}}.
Therefore ell_{ji} = ell_{ij} + 2^{s-1} mod 2^s.
(d) Exactly one survivor per unordered pair. Ell lies in [0, 2^s).
If ell_{ij} in [0, 2^{s-1}), its survivor is (i,j). If ell_{ij} in
[2^{s-1}, 2^s), then ell_{ji} = ell_{ij} + 2^{s-1} - 2^s =
ell_{ij} - 2^{s-1} lies in [0, 2^{s-1}), so the survivor is (j,i).
Either way exactly one orientation is chosen.
(e) Row counts. Form e_* = sum over surviving off-diagonal pairs
of the corresponding mask idempotent. Set
c = (id_A (x) Tr_{A/F_p})(e_*) in A.
The trace Tr_{A/F_p}: A -> F_p is the sum-of-coordinates map. For
the i-th coordinate of A: c_i = sum_j e_*_{ij}, i.e. the number of
survivors in row i. Therefore
0 <= c_i <= N-1, sum_i c_i = #{survivors} = #{unordered pairs}
= N(N-1)/2.
(f) Some c_i differs from some c_j. If all equal to c_0, then
N c_0 = N(N-1)/2, so c_0 = (N-1)/2. Since N even, contradiction.
So some i,j with c_i != c_j.
(g) Extract a factor. Since 0 <= c_i < p, the integer c_i equals
the field element c_i mod p in F_p. Testing gcd(F, c - a) for
a = 0,...,N-1: for the value a = c_i attained by some roots but
not all, gcd(F, c - a) is the product of X - x_k for those k with
c_k = a. Nonconstant (some roots) and proper (others). Otherwise
gcd is 1 (a not attained) or F (a universal, only when all c_i
equal, but that is excluded).
(h) Cost. R = A (x) A has F_p-dimension N^2. Digit procedure:
s <= log_2 p levels, at most N^2 surviving pieces, each with
2 candidate digits (q = 2). Total bit cost polynomial in N and
log p times the field-operation cost.
[]
The core mechanism is a tournament whose arrows are determined by
the quadratic character of differences of unknown roots. Even
degree forces unequal out-degrees, and the unequal out-degrees
yield a factor.
================================================================================
PART V. THE ODD CASE: GEOMETRY
================================================================================
================================================================================
14. The curve Y^q = F(X)
================================================================================
Setup. Fix a finite field K of characteristic p, an odd prime q != p,
and a primitive q-th root of unity zeta in K. Let F in K[X] be monic,
square-free, of degree N >= q with q | N. Suppose all N roots
x_1,...,x_N of F lie in K (they will, in applications, be inside
F_p ⊆ K). Consider the smooth projective curve C/K with function
field
K(C) = K(X, Y), Y^q = F(X).
Because F has a simple root at each x_i, F is not a q-th power even
over K-bar(X), so the map X: C -> P^1 has degree q.
Smoothness. A singularity would require Y = 0 and F(X) = F'(X) = 0,
which is absent since F is square-free. So the affine model is
smooth.
Points at infinity. Put z = X^{-1}, U = Y z^{N/q}. Then
U^q = z^N F(z^{-1}) =: F_inf(z),
and F_inf(0) = 1. At z = 0 the q roots of U^q = 1 are simple, so
there are exactly q rational points at infinity,
I = {inf_0, inf_1, ..., inf_{q-1}}, U(inf_j) = zeta^j.
Ramification. The map X has simple ramification at each P_i = (x_i, 0):
locally F(X) = F'(x_i)(X - x_i) + O((X-x_i)^2) with F'(x_i) != 0, so
Y is a uniformizer and P_i is totally ramified of index q. There is
no other finite ramification, and the q points at infinity are
unramified (since q does not divide N and N/q is an integer).
Genus. Tame Riemann-Hurwitz:
g = 1 + q * (-1) + (1/2) * sum_P (e_P - 1)
= (q-1)(N-2)/2.
(Sum of e_P - 1 over the q points P_i is q * (N * (q-1)) = q N(q-1);
divide by 2 and add the P^1 base term.)
Automorphism sigma. Send (X, Y) -> (X, zeta Y) on points, and
(sigma h)(X, Y) = h(X, zeta^{-1} Y)
on functions. Then div(sigma h) = sigma div(h). In particular,
sigma fixes each P_i (only Y changes, and Y = 0 there), and permutes
inf_0 -> inf_1 -> ... -> inf_{q-1} -> inf_0, cyclically.
================================================================================
15. Divisors, principal divisors, and the Jacobian
================================================================================
Closed points. A closed point P of C over K corresponds to a
Galois orbit of geometric points, with residue field k(P) a finite
extension of K. Its degree is [k(P) : K].
Divisors. A K-rational divisor is a finite formal integer sum
D = sum_P n_P P over closed points P, with all but finitely many
n_P = 0. Its degree is deg D = sum_P n_P * [k(P) : K]. Its
absolute degree is
||D|| = sum_P |n_P| * [k(P) : K].
Principal divisors. For a nonzero rational function h in K(C)^*,
div(h) = sum_P v_P(h) P is a divisor of degree 0. Divisors of this
form are principal. Any two divisors with the same class in the
divisor class group Pic(C) differ by a principal one.
Jacobian. Pic^0(C) is the group of degree-zero divisor classes. The
Jacobian J = Pic^0(C_{\overline K}) is Pic^0 after extending
constants to \overline K. It is a finite-dimensional abelian
variety of dimension g.
The group ring R = Z[xi]. Introduce an abstract primitive q-th root
of unity xi and let sigma act as xi. Both Λ (below) and J become
R-modules.
Orbit sum kills J and Λ. The element 1 + sigma + ... + sigma^{q-1}
acts as zero on J (because the orbit sum of a divisor is the pullback
of its pushforward to P^1, and any degree-zero divisor on P^1 is
principal) and on Λ (because it just multiplies each coefficient by
the sum of the coefficients, which is zero for Λ by construction).
================================================================================
16. The operator lambda and the infinity lattice
================================================================================
The lattice. Define
Λ = { sum_{j=0}^{q-1} a_j * inf_j : a_j in Z, sum_j a_j = 0 }.
Λ is a free abelian group of rank q - 1. On it, sigma cycles the
inf_j, so sigma acts by shifting coefficients. Because the orbit
sum acts as zero on Λ, this is an R-module structure.
The key operator. Set lambda = 1 - xi, so on points it acts as
1 - sigma. Define
e = (sigma - 1) inf_0 = (inf_1 - inf_0) in Λ.
The differences sigma^j e = inf_{j+1} - inf_j generate Λ.
Therefore the map
R -> Λ, a -> a e,
is an isomorphism of free abelian groups (both rank q - 1). In
particular, multiplication by lambda is injective on Λ.
Cyclotomic identity. In R = Z[xi],
q = u * lambda^{q-1} for some unit u in R. (16.1)
Indeed q = prod_{a=1}^{q-1} (1 - xi^a), and each factor
(1 - xi^a)/(1 - xi) is an algebraic integer of norm 1, hence a unit.
The exponent q - 1 is key: q has lambda-valuation q - 1.
Quotient. R / (lambda) = F_q, because substituting xi = 1 into
the cyclotomic polynomial 1 + T + ... + T^{q-1} of xi gives q = 0.
lambda is surjective on J. Multiplication by q, prime to char p,
is a surjective isogeny on J. By (16.1), this implies multiplication
by lambda is also surjective.
Where the obstruction lives. On J, lambda is surjective. On Λ,
lambda is injective. That gap between surjectivity on classes and
injectivity on infinity-divisors is the source of forced separation
in Section 20.
================================================================================
17. The modules T_t and their filtration
================================================================================
Definition of T_t. For t >= 1 define
T_t = ( {(d, W) in J x Λ : lambda^t d = [W]} )
/ ( {([W'], lambda^t W') : W' in Λ} ). (17.1)
The numerator consists of pairs whose lambda^t-th power is an
infinity class; the denominator subtracts changes coming from adding
a divisor supported at infinity to d and cyclically moving W.
Filtration property. The map
T_t -> T_{t+1}, (d, W) -> (d, lambda W),
is injective, and its image is T_{t+1}[lambda^t], the set of classes
in T_{t+1} killed by lambda^t. Consequently, inside any T_m, the
successive modules are exactly
T_j = T_m[lambda^j], for 1 <= j <= m. (17.2)
Proof. (a) Lambda^t kills T_t. On a qualifying pair (d, W),
lambda^t d = [W], so lambda^t (d, W) becomes the trivial
([W], lambda^t W).
(b) The map is injective. Suppose (d, lambda W) = 0 in T_{t+1}.
Then there is W' in Λ with d = [W'] and lambda W = lambda^{t+1} W'.
Dividing the second equation by lambda (injective on Λ) gives
W = lambda^t W', so (d, W) = ([W'], lambda^t W') is already zero
in T_t.
(c) The image is T_{t+1}[lambda^t]. If (d, W) in T_{t+1} is killed
by lambda^t, then lambda^t d = [W'] and lambda^t W = lambda^{t+1} W'
for some W'. The second gives W = lambda W' (injectivity of lambda
on Λ), so (d, W) = (d', W') with lambda^t d' = [W'] and lambda W' = W,
hence the image of (d', W') in T_t. []
Iterated, this makes T_1 = T_m[lambda], T_2 = T_m[lambda^2], etc.:
the whole scale of T_j sits inside T_m as the kernel of lambda^j.
================================================================================
18. Ramification labels
================================================================================
The generator ε_i. For 1 <= i <= N define
ε_i = ([P_i - inf_0], e) in T_1. (18.1)
Each qualifies because lambda(P_i - inf_0) = [e]: apply lambda =
1 - sigma to P_i (fixed by sigma) minus inf_0 (sent to inf_1).
THE LEMMA. The elements ε_1,...,ε_N generate T_1 over F_q, and
sum_{i=1}^N ε_i = 0 in T_1. (18.2)
Proof of (18.2). The divisor of the function Y is
div(Y) = sum_i P_i - (N/q) sum_j inf_j. (18.3)
Set W'' = (N/q) sum_j inf_j - N inf_0. Coefficient sum:
(N/q)*q - N = 0, so W'' lies in Λ. Rearranging (18.3):
sum_i (P_i - inf_0) = div(Y) + W''.
Since div(Y) is principal, sum_i [P_i - inf_0] = [W''].
Compute lambda W'' using lambda = 1 - sigma:
lambda W'' = (1 - sigma)((N/q) sum_j inf_j)
- N (1 - sigma) inf_0.
On the first term, sigma permutes the sum: sigma((N/q) sum_j inf_j)
= (N/q) sum_j inf_{j+1} = (N/q) sum_j inf_j, since j -> j+1 is a
bijection mod q. So (1 - sigma) of that term is 0. On the second
term, (1 - sigma) inf_0 = inf_0 - inf_1 = -e. Hence
lambda W'' = 0 - N(-e) = N e.
Therefore the numerator element
sum_i ε_i = (sum_i [P_i - inf_0], N e) = ([W''], lambda W'')
lies in the denominator of the T_1 quotient, hence equals zero in
T_1. []
LABEL EXPANSION. Let D be a degree-zero divisor, W in Λ, and suppose
div(h) = (1 - sigma) D - W for some h in K(C)^*. (This is the
hypothesis that ([D], W) is in the numerator of T_1.) Then
(a) Norm_{K(C)/K(X)}(h) is a nonzero constant.
(b) Choose gamma in \overline K^* with gamma^q = Norm(h). Then h(P_i)
is defined and nonzero, and
l_i = v_{P_i}(D) - log_zeta(h(P_i)/gamma) in F_q,
and
([D], W) = sum_i l_i ε_i in T_1. (18.4)
Proof.
(a) The orbit sum of (1 - sigma)D - W is zero: on D, summing over
sigma^j gives (1 + ... + sigma^{q-1})(1 - sigma) D = (1 - sigma^{q})
D = 0; on W (an orbit-sum-zero lattice element), also zero. So the
orbit-sum of div(h) is zero, i.e. Norm(h) has zero divisor on P^1,
hence is a nonzero constant.
(b) Hilbert's Theorem 90 for the cyclic extension K-bar(C)/K-bar(X)
gives h/gamma = b/(sigma b) for some b in K-bar(C)^*.
Take a divisor W_0 supported on I with (1 - sigma) W_0 = W. Such
W_0 exists: (1 - sigma) of the full permutation lattice Z^I has
image Λ, because (1 - sigma)(sum_j c_j inf_j) = sum_j (c_j -
c_{j+1}) inf_j has coefficient sum zero.
Let D' = D - div(b). Then
(1 - sigma) D' = (1 - sigma) D - (1 - sigma) div(b)
= (1 - sigma) D - div(h) (since h/gamma = b/(sigma b))
= W.
Also (1 - sigma) W_0 = W, so (1 - sigma)(D' - W_0) = 0, i.e.
D' - W_0 is sigma-invariant.
A sigma-invariant divisor has equal coefficients on each unramified
orbit, and coefficients free modulo q at each ramification point
(pullback there multiplies by q). Reducing the residues and
absorbing each unramified orbit into X^* times a point of P^1:
D' - W_0 = sum_i a_i P_i + X^* D_0, 0 <= a_i < q. (18.5)
Degrees. Both sides have degree 0 (D' = D - div(b) and W_0 both
have degree 0). The right side has degree sum_i a_i + q deg D_0.
So q deg D_0 = -sum_i a_i.
Define W' = W_0 + (sum_i a_i) inf_0 + (deg D_0) sum_j inf_j. The
coefficient sum of W' is 0 + sum_i a_i + q deg D_0 = 0, so W' in Λ.
Classes. Since [D'] = [D] (div(b) is principal),
[D] = [W_0] + sum_i a_i [P_i] + (deg D_0) [sum_j inf_j]
= [W'] + sum_i a_i [P_i - inf_0].
Lambda. lambda W_0 = W; lambda(inf_0) = -e; lambda(sum_j inf_j) = 0.
Hence
lambda W' = W - (sum_i a_i) e.
Therefore ([W'], lambda W') lies in the T_1 denominator, i.e. is
zero in T_1. Working in the T_1 group,
([D], W) = ([D], W) - ([W'], lambda W') + ([W'], lambda W')
= (sum_i a_i [P_i - inf_0], (sum_i a_i) e)
= sum_i a_i ε_i in T_1. (18.6)
This is the F_q-coefficient expansion (coefficients a_i, not yet l_i).
c) Matching labels. At P_i both (1 - sigma)D and W have coefficient
zero, so v_{P_i}(h) = 0 and h(P_i) is defined and nonzero. The norm
at P_i is h(P_i)^q, because sigma fixes P_i and acts trivially on
the residue field K. So h(P_i)/gamma is a q-th root of unity and
log_zeta makes sense at P_i.
Let a = v_{P_i}(b). Y is a local uniformizer at P_i (Y has a simple
zero there because Y^q = F(X) has a simple zero with F'(x_i) != 0).
Write b = Y^a u near P_i with u(0) != 0. Then sigma sends
Y -> zeta^{-1} Y, so sigma b = zeta^{-a} Y^a sigma(u), and
(b/(sigma b))(P_i) = zeta^a * u(P_i)/sigma(u)(P_i) = zeta^a,
because sigma(u)(P_i) = u(P_i): sigma fixes P_i and acts trivially
on the residue field K.
From Hilbert 90, h/gamma = b/(sigma b), so h(P_i)/gamma = zeta^a
and log_zeta(h(P_i)/gamma) = a mod q.
From (18.5) at P_i: W_0 has no P_i component (supported on I),
X^* D_0 has no P_i component (P_i is a ramification point, absorbed
into the sum a_i P_i term; adjust D_0 by linear equivalence on P^1
if needed so that x_i is not in supp(D_0)). Therefore
v_{P_i}(D') = a_i, i.e. v_{P_i}(D) - v_{P_i}(div b) = a_i, i.e.
v_{P_i}(D) - a = a_i.
Combining,
l_i = v_{P_i}(D) - log_zeta(h(P_i)/gamma) = v_{P_i}(D) - a ≡ a_i.
So l_i = a_i mod q, and (18.6) becomes (18.4). []
Consequence. If all l_i are equal, then ([D], W) = sum l_i ε_i
= l_0 sum_i ε_i = 0 by (18.2). Replacing gamma by another q-th root
shifts every l_i by the same constant, which has no effect because
of (18.2).
================================================================================
19. Frobenius and rational divisions
================================================================================
Let Π denote the |K|-th power Frobenius on K-bar: it acts on
geometric points, divisors, and divisor classes. It commutes with
sigma (since sigma is K-rational) and fixes Λ pointwise.
Frobenius fixes T_1. Every P_i and every inf_j is K-rational, so
Π fixes each ε_i. Since the ε_i generate T_1, Π is the identity on
T_1.
KEY LEMMA (Frobenius filtration). Let r >= 0 and set
m = 1 + (q-1) r. Let k/K be the extension of degree q^r. Then
Π^{q^r} fixes T_m pointwise. Moreover, if 1 <= t <= m and
d in J, W in Λ satisfy lambda^t d = [W], then d is fixed by the
Frobenius of k.
Proof. Put F_j = ker(lambda^j) ⊂ T_m for 0 <= j <= m, and F_j = 0
for j < 0. By Section 17, F_1 = T_1.
(a) Π - 1 lowers the filtration by one. For v in F_j:
lambda^{j-1}(Π - 1) v = (Π - 1) lambda^{j-1} v = 0 since
lambda^{j-1} v in F_1 and Π fixes F_1. Hence (Π - 1) v in F_{j-1}.
(b) Multiplication by q lowers filtration by q-1. Because
q = u lambda^{q-1} with u a unit, mult-by-q equals mult-by-u times
mult-by-lambda^{q-1}. Mult-by-u is a bijection. So kernel of mult-by-q
on F_j is kernel of lambda^{q-1} on F_j, which lands in F_{j - (q-1)}.
(c) Induction. Suppose A = Π^{q^a} - 1 lowers filtration by >= f >= 1.
Binomial:
Π^{q^{a+1}} - 1 = (1 + A)^q - 1
= q A + binom(q,2) A^2 + ... + binom(q,q-1) A^{q-1} + A^q.
Each intermediate term binom(q,j) A^j: A^j lowers by jf, and
binom(q,j) for 1 <= j <= q-1 is divisible by q so introduces a
multiplication by q which lowers q-1 further. So binom(q,j) A^j
lowers by at least f + (q-1). The final term A^q lowers by qf
>= f + (q-1) since f >= 1 and q >= 3.
Hence A' := Π^{q^{a+1}} - 1 lowers by >= f + (q-1).
Starting with f = 1 (from part (a)) and a = 0, iterating r times
gives Π^{q^r} - 1 lowers by 1 + r(q-1) = m, hence vanishes on T_m.
(d) The "moreover". If lambda^t d = [W] with t <= m, then the class
of (d, W) in T_t ⊂ T_m is fixed by Π^{q^r}. The lattice component
is unchanged. So (Π^{q^r} d - d, 0) writes as ([W'], lambda^t W')
for some W'. The second coordinate gives lambda^t W' = 0, and
injectivity of lambda on Λ gives W' = 0. The first gives
Π^{q^r} d = d. []
FINITE-FIELD DESCENT. Let C be a smooth projective geometrically
integral curve over a finite field k. Then
(i) A k-rational divisor that is geometrically principal is the
divisor of a function in k(C)^*.
(ii) Every geometric divisor class fixed by Frobenius has a k-rational
divisor representative.
Proof. (i) Choose h with the given divisor over a finite extension
k'/k. If tau generates Gal(k'/k), then tau h/h is a constant in k'^*,
norm one to k. Hilbert 90 for k'/k gives a constant c with
c*tau(c)^{-1} = (tau h/h)^{-1} after scaling, so c h is tau-invariant,
hence lies in k(C)^*.
(ii) Choose a representative D over k'/k. Class fixed, so D - tau D
is principal; by (i) D - tau D = div(h) for h in k'(C)^*. The norm
of h from k'(C) to k(C) has zero divisor, hence is a constant in
k^*. Scaling h by a k'^* constant of norm one, Hilbert 90 for k'/k
gives h = b/(tau b), so D - div(b) is tau-invariant, and invariant
divisors descend by grouping Galois orbits. []
COROLLARY (rational lifts). In Section 14's setup, let r >= 0,
m = 1 + (q-1)r, [k : K] = q^r. For every 1 <= i <= N, there exist
classes d_{i,1},...,d_{i,m} represented by degree-zero divisors over
k, with
d_{i,1} = [P_i - inf_0], lambda d_{i,t+1} = d_{i,t},
lambda^t d_{i,t} = [e] for 1 <= t <= m. (19.1)
Proof. Surjectivity of lambda on J allows each choice over K-bar.
Induction using lambda d_{i,1} = [e] (from Section 16) and lambda
d_{i,t+1} = d_{i,t} gives lambda^t d_{i,t} = [e]. Thus (d_{i,t}, e)
qualifies for T_t. Frobenius fixes d_{i,t} over k (Section 19 key
lemma), and finite-field descent supplies a k-rational representative.
The argument applies to any chosen division, not just special
compatible ones. []
================================================================================
20. Forced separation of ramification points
================================================================================
Setup. Put r = v_q(N) and m = 1 + (q-1)r; let [k:K] = q^r.
Let d_m in J be represented by a degree-zero divisor over k with
lambda^m d_m = [Ne]. (20.1)
Define, for 1 <= t <= m,
d_t = lambda^{m-t} d_m, W_t = lambda^{-(t-1)} Ne in Λ. (20.2)
The W_t exist uniquely for all t (they are obtained by solving
(1 - sigma) W_{t+1} = W_t on cyclic infinity coordinates), and the
solution is in Λ because of the q^r | N divisibility.
PROPOSITION 20.1 (Forced separation). Choose any degree-zero divisor
D_t of C over k representing d_t. Start at t = 1. At step t, find
h_t in k(C)^* and gamma_t in k^* with
div(h_t) = (1 - sigma) D_t - W_t, gamma_t^q = Norm(h_t), (20.3)
and form the ramification labels
l_{i,t} = v_{P_i}(D_t) - log_zeta(h_t(P_i)/gamma_t) in F_q. (20.4)
If all l_{i,t} for a fixed t agree across i, advance to t+1; else
stop and return a factor (via gcd with F, as in Section 13). Then
for some t <= m, the labels are not all equal.
Proof. (a) Lattice obstruction. Write N = q^r a with q coprime to a.
By (16.1), q^r is an associate of lambda^{(q-1)r} = lambda^{m-1},
while the image of a in R/(lambda) = F_q is nonzero. Therefore
Ne in lambda^{m-1} Λ \ lambda^m Λ. (20.5)
In particular W_m exists (as W_m = lambda^{-(m-1)} Ne, using
q^r | N to guarantee divisibility by lambda^{m-1}) and
W_m NOT IN lambda Λ. And each intermediate W_t is uniquely defined.
(b) If all labels at t agree, the pair (d_t, W_t) is zero in T_1.
For t = 1 this is automatic: lambda^m d_m = [Ne] implies
lambda^1 d_1 = [Ne] where d_1 = lambda^{m-1} d_m, so (d_1, W_1)
qualifies for T_1. Section 18 shows (d_t, W_t) = sum_i l_{i,t} ε_i.
If all l_{i,t} equal l_0, then (d_t, W_t) = l_0 sum_i ε_i = 0
by (18.2).
(c) Zero in T_1 means the next invariant holds. Being zero in T_1
means (by definition of the T_1 quotient) there is W' in Λ with
d_t = [W'] and W_t = lambda W'.
For t < m: by construction W_t = lambda W_{t+1}, so lambda W' =
lambda W_{t+1}; injectivity of lambda on Λ gives W' = W_{t+1}.
Then d_t = [W_{t+1}], and substituting into lambda d_{t+1} = d_t
yields exactly lambda d_{t+1} = [W_{t+1}], the invariant required
for test t+1.
(d) At t = m the invariant fails. At t = m, zero in T_1 gives
W_m = lambda W' for some W' in Λ (using the same injectivity
argument, this time without a next step to invoke). But (20.5)
says W_m NOT IN lambda Λ. Contradiction.
(e) Therefore some t <= m has nonconstant labels. This does not
depend on the choices of D_t, h_t, or gamma_t: (18.2) cancelled
any global shift of the labels, so constancy is a well-defined
property of the pair (d_t, W_t). []
Figure 20.1 (informal). Imagine two ladders of rungs. The lower
rung is the class chain: d_1 <- lambda d_2 <- lambda d_3 <- ... <- d_m
(arrow points down). The upper rung is the lattice chain:
W_1 = Ne, W_2, W_3, ..., W_m = lambda^{-(m-1)} Ne (each obtained by
dividing Ne by one more power of lambda). Tests walk left to right.
At rung t, equal labels let the class d_t jump onto [W_{t+1}] and
move to the next rung. At rung m, W_m would need to be divisible by
lambda, which the whole N = q^r a with a coprime to q forbids.
This is where the entire odd-case split comes from: unequal labels
at some t produce a gcd with F that is a nontrivial factor.
================================================================================
PART VI. THE ODD CASE: COMPUTATION
================================================================================
================================================================================
21. Divisor arithmetic without known supports
================================================================================
The geometric argument uses divisors whose finite supports are the
unknown roots x_i. We must add them, apply sigma, compute principal
divisors, and reduce to small representatives - all without ever
knowing an individual point of the support. The representation is a
fractional ideal of the coordinate ring.
21.1 FRACTIONAL IDEALS
Setup. Let O = k[X, Y] / (Y^q - F(X)) be the coordinate ring of the
affine model. Because Y^q - F(X) is smooth (F square-free, q
coprime to char k) and its projectivization is normal, O is a
Dedekind domain with fraction field k(C). O is a free k[X]-module
with basis 1, Y, ..., Y^{q-1}.
Divisor representation. Two pieces:
(finite part) a fractional ideal I(D) of O, defined by
I(D) = {a in k(C)^* : v_P(a) + v_P(D) >= 0 at every finite P}
U {0};
(infinity part) the integer vector (v_inf_0(D), ..., v_inf_{q-1}(D)).
Storage. Pick a monic H in k[X] with
H O ⊆ I(D) ⊆ H^{-1} O. (21.1)
Store I(D) as a k-subspace of H^{-1}O / HO. Multiplication by H
identifies that quotient with O / H^2 O, of k-dimension 2 q deg H.
A subspace basis of the quotient lifts to a finite list of
O-generators of I(D). Conversely, from O-generators and a bound
(21.1), take their images and enlarge the k-span under
multiplication by X and Y; stability is reached in at most 2 q deg H
rounds and gives the subspace.
Divisor operations on the finite part reduce to algebra of ideals:
I(D + E) = I(D) * I(E) (product)
I(-D) = I(D)^{-1} (inverse ideal)
I(min(D,E)) = I(D) + I(E) (sum of subspaces)
I(max(D,E)) = I(D) ∩ I(E) (intersection)
All are linear algebra in the stored subspaces, using a common bound
H_D H_E for a product or sum, or H for an inversion.
For inversion: a in H^{-1}O lies in I^{-1} iff a*u in O for every
generator u of I. These are homogeneous linear conditions on the
quotient H^{-1}O / HO, independent of the representative of a
(because H I ⊆ O).
sigma action. sigma = (X, Y -> zeta Y) on points. On functions,
Y -> zeta^{-1} Y. On the ideal: replace Y by zeta^{-1}Y in every
generator. On the integer vector: cyclically permute indices.
Known points. At P_i = (x_i, 0), the maximal ideal of P_i is
(X - x_i, Y) with natural bound H = X - x_i. Substituting x_i for X
and 0 for Y makes local computations explicit.
Local expansions. For local data we use Hensel:
- At infinity j: z = X^{-1}, U = Y z^{N/q}. Then U^q = F_inf(z)
with F_inf(0) = 1 and U(inf_j) = zeta^j. Lift the simple root
to a truncated power series in z.
- At P_i: use Y as uniformizer and solve F(X) = Y^q with
X(0) = x_i by Hensel (F'(x_i) != 0).
Precision bound. Write a function as A(X,Y)/B(X) with
deg_Y A < q and every X-coefficient (including B) of degree <= E.
Its divisor has absolute degree at most q(E + N). So its first
nonzero Laurent coefficient at any rational point is determined by
the truncation
precision 8 q (E + N + 1). (21.2)
21.2 COMPRESSION AND PUSHFORWARD
Intermediate bounds need not be minimal. The following reduces them
to "optimal" polynomials and supplies the norm input for later.
LEMMA 21.2 (Compression). From the representation of I(D), one can
compute monic h^+, h^- in k[X] with
deg h^+ = sum_{finite P} max(v_P(D), 0) [k(P) : k],
deg h^- = sum_{finite P} max(-v_P(D), 0) [k(P) : k], (21.3)
such that H = h^+ h^- is a valid bound (21.1). If deg D = 0 and
j = h^+/h^- in k(X)^*, then
div(j) = sum_{a=0}^{q-1} sigma^a D. (21.4)
Proof. Form the integral ideals I^+ = I(D) ∩ O and
I^- = I(D)^{-1} ∩ O. These are computed by taking the intersection
of the stored subspace with O inside H_0^{-1}O for a preliminary
bound H_0. Let h^+ be the characteristic polynomial of multiplication
by X on O / I^+ and h^- the corresponding polynomial on O / I^-.
Cayley-Hamilton gives h^+ O ⊆ I^+ ⊆ I(D) and h^- O ⊆ I^- ⊆ I(D)^{-1}.
The second inclusion shows I(D) ⊆ (h^-)^{-1} O. So H = h^+ h^- is
a valid bound.
Degree formulas: at a closed point P of multiplicity d in D, the
quotient O/I^+ has a filtration by d copies of k(P), hence
k-dimension d [k(P) : k]. Summing over finite P gives (21.3).
For (21.4): the divisor of j = h^+/h^- on P^1 (via X: C -> P^1) is
div_X(h^+/h^-) = sum_P (max(v_P D, 0) - max(-v_P D, 0)) [P]
= sum_P v_P(D) [P] = X_* D.
Therefore div(j) restricted to finite points has the same minimum
valuations as X_*D. Since deg D = 0, the divisor X^*X_*D = div(j)
has degree 0 and the pullback identity for the cyclic cover gives
(21.4) exactly. []
21.3 RIEMANN-ROCH REDUCTION
For a divisor D, write L(D) = {a in k(C)^* : div(a) + D >= 0} U {0}.
Riemann-Roch inequality: for effective D of degree d >= 0,
dim_k L(D) >= d + 1 - g.
Take l = g. Then dim L(D + g inf_0) >= 1.
Local-to-global ansatz. Let H be a bound for I(-D). Every a in
L(D + l inf_0) has the form
a = H^{-1} * sum_{j=0}^{q-1} a_j(X) Y^j,
deg a_j <= deg H + ||D|| + l. (21.5)
Justification of the degree bound. Let
M = max_{a_j != 0} (deg a_j + j N/q - deg H). Then the coefficient
of z^{-M} at infinity (in each coordinate of the Laurent expansion
near inf_j) is a polynomial in the residues 1, zeta, ..., zeta^{q-1}
of degree < q; a polynomial of degree < q cannot vanish on all q
distinct q-th roots of unity, so at some inf_j the pole order (as
-v_inf_j(a)) equals M. The defining inequalities of L(D + l inf_0)
give M <= ||D|| + l, proving (21.5).
Linear system. Membership in I(-D) is a subspace condition on the
ansatz coefficients a_0, ..., a_{q-1}. The Laurent inequalities
v_inf_j(a) >= -v_inf_j(D) - l 1_{j=0} (0 <= j < q) are
linear conditions on the Laurent coefficients. Expanding through
precision (21.2) inflated by 8q(||D|| + l + 1) suffices. Solving the
resulting linear system gives the space L(D + l inf_0) explicitly.
ReduceDivisor. Given a degree-zero D, choose a nonzero
a in L(D + g inf_0). Define
D' = D + div(a). (21.6)
Since D' + g inf_0 is effective of degree g, ||D'|| <= 2g. Return
(D', a). When D is known to be principal, use l = 0: choose nonzero
a in L(D) and obtain D + div(a) = 0.
Cost. All operations are polynomial in q, N, the bound degrees, and
the divisor absolute degrees. The quotient has dimension
2q deg H; the RR ansatz has at most q (deg H + ||D|| + l + 1)
unknowns. Functions are stored with rational coefficients (ratios
of minors). All decisions are zero tests over k, so simultaneous
execution applies.
================================================================================
22. Simultaneous sums and large-divisor evaluation
================================================================================
22.1 SUMMING DIVISORS OVER A PRODUCT ALGEBRA
The odd splitter produces one divisor per root of F for each i,
computed simultaneously over the split algebra A = k[T]/F(T)
(isomorphic to k^N). We need to sum them without knowing the
components.
LEMMA 22.1 (Simultaneous divisor sum). Let A ≅ k^s be an explicitly
represented split algebra, and let I_1, ..., I_s be fractional
ideals of O supplied together over A, with monic bound polynomials
H_1, ..., H_s and a common generator count b: generators
u_{i,0}, ..., u_{i,b-1} of I_i (including H_i itself). Suppose the
prime subfield of k has more than s(b-1) elements. Then
prod_i I_i can be computed by polynomial arithmetic and linear
algebra over k, without knowing components.
Proof. Let H in A[X] be the tuple of bounds (componentwise), and
u_j in A the tuple of j-th generators (componentwise O). Define
H_* = Norm_{A/k}(H) = prod_i H_i in k[X], (22.1)
w_a = Norm_{A/k}(sum_{j=0}^{b-1} a^j u_j)
= prod_{i=1}^s (sum_{j=0}^{b-1} a^j u_{ij}) in O, (22.2)
for a in the prime subfield. The displayed products over i (and H)
are the formulas proved by the norm-determinant; they are not
instructions to recover the components.
Claim: some a gives w_a with v_P(w_a) = sum_i v_P(I_i) at every
finite P. Fix P and put d_i = min_j v_P(u_ij). Divide component i by
a local uniformizer to the d_i-th power. Its residue mod the
uniformizer is a nonzero polynomial in a over k(P) of degree at most
b-1. At most b-1 values of a make it zero. There are at most s
components, so at most s(b-1) values of a fail to hit the minimum
simultaneously in some component. The prime subfield has more than
s(b-1) elements, so some a attains all d_i at once. Dedekind
fractional ideals are determined by these minimum valuations;
therefore the w_a generate prod_i I_i.
H_* is a valid bound for prod_i I_i, so the storage representation is
recovered by finite ideal closure.
Infinity vectors. In a simultaneous execution over A, the infinity
vectors in different components must agree where zero tests agree;
otherwise a factor has already been returned. So the sum is
multiplication by s (or by the number of surviving components).
[]
In our application s = N. The compressed generator bound b is at
most 2q deg H_i + 1 (from 21.2). The characteristic cutoff in
Section 30 gives p > N(b-1).
22.2 CIRCUITS FOR LARGE INFINITY DIVISORS
The label tests of Section 20 need a function h with
div(h) = (1 - sigma) D - W, (22.3)
where W = sum_j w_j inf_j has coefficients up to N(2q)^m - too
large to represent as a divisor of bounded absolute degree. Instead
we compute h from a circuit of small function multiplications and
inversions.
LEMMA 22.2 (Circuit evaluation). Let D be a represented degree-zero
divisor with ||D|| bounded, and W = sum_j w_j inf_j a degree-zero
divisor with integer coefficients given in binary. If
Z = (1 - sigma)D - W is principal, a circuit for a defining
function h (div(h) = Z) can be computed using polynomially many
operations in q, N, ||D||, representation size, and
max_j log(2 + |w_j|).
Proof. Write W = sum_{j=1}^{q-1} w_j(inf_j - inf_0) using
sum_j w_j = 0.
Start with T_0 = (1 - sigma) D, D_0 = reduce(T_0), w_0 = correcting
function from the reduction. Invariant: D_0 = T_0 + div(w_0).
For each term w_j(inf_j - inf_0), process the binary expansion of w_j
one bit at a time:
- Doubling: D <- reduce(D + D), w <- w^2 * u (u = the reducing
function).
- Adding a single (inf_j - inf_0): D <- reduce(D + (inf_j - inf_0)),
w <- w * v (v = the reducing function), where the small divisor
inf_j - inf_0 has || || = 2.
- Signs float outside; a w_j < 0 corresponds to negating.
Invariant maintained: D_k = Z_k + div(w_k); ||D_k|| <= 4g
after each reduction (absolute degree grows by at most ||Z_step||
plus 2g per step, and reduce returns to <= 2g immediately).
Number of reductions: O(sum_j log(2 + |w_j|)), since each doubling
or addition consumes one bit of w_j.
Final step. At the end, D_final is a small representative of Z.
Compute a with Z + div(a) = 0 by the l = 0 Riemann-Roch ansatz.
Then h = (a * w_final)^{-1} has divisor Z.
Leaf sizes. Each leaf is a function from a reduction of a
small divisor. Coefficient degrees are bounded by the reduction
formulas of 21.3 (bounded by 8q(||D_k|| + N + 1) for each k).
Therefore every leaf has polynomial representation size.
Evaluating at P_i. At P_i we need v_{P_i}(Z) = 0 and h(P_i).
Propagate v_{P_i} and the leading coefficient through the
circuit:
- Multiplication: add valuations, multiply leading coefficients.
- Inversion: negate valuation, invert leading coefficient.
- Addition of (inf_j - inf_0) followed by reduction: use the
reduction function u's expansion at P_i.
Because P_i is fixed by sigma and W is supported at infinity,
v_{P_i}(Z) = 0. So the final propagated valuation is 0, and the
final propagated leading coefficient is exactly h(P_i).
Integer bit lengths: each leaf v_{P_i} is bounded by the leaf's
absolute degree; propagation doubles at most; the total is bounded
by the circuit length times leaf size, polynomial. []
================================================================================
23. The promised norm solver: cyclic algebras
================================================================================
Setup. Throughout Sections 23 through 26:
- k finite field of characteristic p, q odd prime.
- zeta in k of order q, omega in k^* generating the full q-primary
subgroup.
- F in k[X] monic square-free, N = deg F divisible by q.
- K_0 = k(X), L = K_0[Y] / (Y^q - F).
- rho: L -> L by Y -> zeta Y (automorphism of order q).
- G in K_0^*, promised to be a norm: G in Norm_{L/K_0}(L^*).
- D = max(numerator degree, denominator degree of G).
- hypothesis p > (N + 2D + 1)^2.
Goal. Deterministically construct h in L^* with
prod_{j=0}^{q-1} rho^j(h) = G. (23.1)
THEOREM 23.1 (Promised norm solver). Under these hypotheses, h can
be constructed by field arithmetic and zero tests over k only, in a
number of bit operations polynomial in q, N, D, and log |k|. No
polynomial factoring of F is used.
The proof has three stages.
Stage A (23.1). The cyclic algebra E.
Form the K_0-algebra
E = oplus_{b=0}^{q-1} L V^b,
V^q = G, V a = rho(a) V for a in L. (23.2)
E has K_0-dimension q^2, with explicit multiplication in the basis
W_{ab} = Y^a V^b (0 <= a,b < q). The norm promise (G is a norm)
makes E isomorphic to the matrix algebra M_q(K_0); this is exactly
the splitting criterion for cyclic algebras (Hasse's norm theorem,
collapsed into "G is a norm").
Stage B (23.2). A rank-one idempotent gives h.
LEMMA 23.2. Let e in E be a rank-one idempotent: e^2 = e and
tr(e) = 1 under any isomorphism E ≅ M_q(K_0). Then there is a
unique h in L^* with V e = h e, and this h satisfies (23.1). Bit
cost polynomial in q, N, D.
Proof. Ee is a q-dimensional K_0-subspace of E (rank e = 1). The map
ph: L -> Ee, a -> a e,
is K_0-linear and injective: if a ≠ 0 in L, it is invertible in E,
so a e ≠ 0. Both sides have K_0-dimension q, so ph is bijective.
Since V e is in E, it lies in Ee = ph(L); there is a unique h in L
with V e = h e. And h ≠ 0: if h = 0 then V e = 0, and multiplying by
V^{-1} (V invertible in E because V^q = G ≠ 0) gives e = 0,
contradicting tr(e) = 1.
Iteration. Apply V on the left repeatedly:
V^1 e = h e.
V^2 e = V (h e) = (V h) e = (rho(h) V) e = rho(h) (V e)
= rho(h) (h e) = (rho(h) h) e.
V^k e = (prod_{j=0}^{k-1} rho^j(h)) e by induction on k.
At k = q:
V^q e = G e = (prod_{j=0}^{q-1} rho^j(h)) e.
So (G - prod rho^j(h)) e = 0 in E.
The element s = G - prod rho^j(h) lies in K_0 (each rho^j(h) is in
L, but their product is invariant under rho, hence in the fixed
field K_0 of rho). If s ≠ 0, then s is invertible in K_0 ⊆ E, so
s e ≠ 0, contradiction. Hence s = 0 and (23.1) holds.
Computation of h from e. Both sides of "V e = h e" are elements of
E. Express them in the basis W_{ab}. The unknowns are the q
coefficients c_0, ..., c_{q-1} of h(Y) = sum_a c_a Y^a in K_0. The
coefficientwise identity V e - h e = 0 in E gives q^2 linear
conditions in (c_a); bijectivity of ph makes the system unique
solvable. Solve by Gaussian elimination over K_0. []
Stage C (23.3). Constructing a rank-one idempotent.
Sections 24 and 25 build e. Local maximal orders A_v at every place
(Section 24), global sections S = E ∩ prod A_v, reduction at
infinity B = ev_inf(S) ⊆ M_q(k) (Section 25). Bundle theory on P^1
shows B is block upper triangular, hence contains a rank-one
idempotent a_0. Lift a_0 to b in S. Then e = b^q is a rank-one
idempotent. Apply Lemma 23.2 to get h.
================================================================================
24. Maximal orders and local matrix models
================================================================================
For each place v of P^1_k, construct a maximal order A_v in
E ⊗ K_v. Notation: K_v = completion of K_0 at v, R_v its valuation
ring, z a uniformizer.
Global structure. L / K_0 is a cyclic q-cover of P^1 ramified
exactly at P_1, ..., P_N (index q at each) and unramified elsewhere.
At infinity, F has a pole of degree N (a multiple of q), so
infinity is unramified.
Norm promise translation. For an unramified cyclic local extension
of degree q, the norm subgroup of K_v^* equals {x : q | v(x)}
(units times q-th powers of uniformizers). Norm promise therefore
forces q | v(G) at every unramified v. In particular at every
generic v and at infinity.
24.1 GENERIC UNRAMIFIED CASE
Let v be unramified; v(F) = 0 unless v = infinity where v(F) = -N.
Because q | v(G) by the norm promise, and q | v(F) (either 0 or -N),
define
Y_v = Y / z^{v(F)/q}, V_v = V / z^{v(G)/q}. (24.1)
The exponents are integers. Then
Y_v^q = F / z^{v(F)} = unit at v,
V_v^q = G / z^{v(G)} = unit at v,
V_v Y_v = rho(Y_v) V_v (rescaling factors cancel).
Set A_v = R_v-span of {Y_v^a V_v^b : 0 <= a,b < q}. This is a free
R_v-module of rank q^2 closed under multiplication; being so with
all "unit" generators, it is a maximal order.
24.2 INFINITY
Take v = infinity, z = X^{-1}. Then v(F) = -N and
U := z^{N/q} Y = Y / z^{-N/q} = Y / z^{v(F)/q} = Y_v (24.2)
matches the generic formula. Norm promise: v_inf(G) = -deg G is a
multiple of q, so V_inf := V / z^{v_inf(G)/q} is a unit. Thus
A_inf = k[[z]]-span of {U^a V_inf^b : 0 <= a,b < q}.
Reduction at infinity: mod z, U becomes a matrix u in M_q(k) with
u^q = F_inf(0) * 1 = 1, and V_inf mod z is invertible in M_q(k).
Absorbing the mod-z scalar u into the identification, A_inf mod z =
M_q(k); the residue map is
ev_inf: S -> M_q(k), b -> b mod z. (24.3)
24.3 RAMIFIED PLACE P_i
At v = P_i: L_v/K_v is totally ramified of index q, and Y is a
uniformizer of L_v (Y^q = F has v(F) = 1, so v_L(Y) = 1 under the
L_v-normalised valuation v_L(L_v^*) = Z).
E ⊗ K_v is a division algebra; its maximal order A_{P_i} is unique
(central simple algebra over a discretely valued field). Explicitly:
take V_v = Y^{-v(G)} V. Since q v_L(V) = v_L(V^q) = v_L(G) =
q v(G) under the normalised v_L, we have v_L(V) = v(G); then
v_L(V_v) = -v(G) * 1 + v(G) = 0 (a unit). And
V_v Y = Y^{-v(G)} V Y = Y^{-v(G)} rho(Y) V
= rho(Y) Y^{-v(G)} V = rho(Y) V_v.
Set A_{P_i} = R_v-span of {Y^a V_v^b : 0 <= a,b < q}, a free
R_v-module of rank q^2 closed under multiplication. Maximality
follows from the corresponding subalgebra being integrally closed
and having the maximal possible residue algebra over kappa_v.
24.4 COMPATIBILITY
The A_v's agree outside the finite set
Bad = {P_1, ..., P_N} U {zeros and poles of G} U {infinity}.
Outside Bad, A_v = M_q(O_{P^1}). By gluing, the A_v are the stalks
of a sheaf of maximal orders in E over P^1, which is End(V) for some
vector bundle V of rank q on P^1.
The global sections are
S = E ∩ prod_v A_v = H^0(P^1, End V). (24.4)
================================================================================
25. Global sections and the fiber idempotent
================================================================================
From Section 24, we have the global sections S = E ∩ prod A_v.
Computing S. By the ansatz of Section 21.3 adapted to E: S equals
the set of elements of the form
b = sum_{a,b=0}^{q-1} c_{ab}(X) Y^a V^b (25.1)
with c_{ab}(X) in k(X) such that b is integral at every place. This
is a finite-dimensional k-subspace of E. A k-basis of S is computed
by imposing the integrality conditions at each exceptional place
(P_i: integrality in A_{P_i}; infinity: k[[z]]-integrality via the
model of 24.2; generic v: vanishing of X-poles) and solving the
resulting k-linear system.
Reduction at infinity. Let ev_inf: S -> M_q(k) be the residue map
of (24.3), applied basis element by basis element. Set
B = ev_inf(S) ⊆ M_q(k). (25.2)
B is a k-subalgebra of M_q(k) (since S is closed under product and
ev_inf is a k-algebra homomorphism).
Bundle splitting. Let V be the rank-q vector bundle on P^1 with
End(V) extending the local A_v's. Grothendieck's theorem on P^1
(the elementary proof covers split P^1; see Hazewinkel--Martin):
every bundle on P^1 decomposes as a direct sum of line bundles,
V ≅ oplus_{i=1}^{r} O(d_i)^{m_i}, d_1 > d_2 > ... > d_r.
Consequently End(V) at the fiber z = 0 is block upper triangular
with diagonal blocks M_{m_i}(k). Indeed, an endomorphism of
oplus_i O(d_i)^{m_i} sends O(d_j)^{m_j} to O(d_i)^{m_i} via a
section of O(d_j - d_i) tensor M_{m_i x m_j}(k). At z = 0:
- (i,i): any m_i x m_i matrix;
- (i,j) for i < j: vanishing at z = 0 (since d_j < d_i);
- (i,j) for i > j: likewise vanishing (since d_j > d_i).
So B is block upper triangular, with diagonal blocks B_ii =
M_{m_i}(k).
Trace-pairing kernel. Define
N = {a in B : tr(ab) = 0 for all b in B}. (25.3)
For block-upper-triangular B with diagonal blocks M_{m_i}(k): the
trace pairing tr(ab) is a sum over i of tr(a_ii b_ii). The pairing
on M_{m_i}(k) is nondegenerate, so a_ii = 0 for all i iff a is in N.
Therefore N = strict block upper triangular matrices (all diagonal
blocks zero).
Common column kernel. Let
U = intersection_{a in N} ker(a) ⊆ k^q. (25.4)
In block coordinates v = (v_1, ..., v_r) with v_i in k^{m_i},
(a v)_i = sum_{j > i} a_{ij} v_j. To vanish for every strict-upper-
triangular a: for i = r, this is always zero; for i = r - 1, need
a_{r-1, r} v_r = 0 for all a_{r-1,r} in M_{m_{r-1} x m_r}(k), hence
v_r = 0; downward induction gives v_2 = ... = v_r = 0. So
U = {(v_1, 0, ..., 0) : v_1 in k^{m_1}} ⊆ k^q. (25.5)
Rank-one idempotent in B. Let v be any nonzero element of U. Because
dim U = m_1 >= 1, such v exists. Choose w in U with w^T v = 1 (the
functional w -> w^T v is nonzero on U, so scale to 1). Set
a_0 = v w^T (v as column, w^T as row). (25.6)
Properties:
- a_0^2 = v (w^T v) w^T = v w^T = a_0 (idempotent).
- tr(a_0) = w^T v = 1.
- rank(a_0) <= 1 (image inside span(v) ⊆ k^{m_1} x {0} x ... x
{0}), and rank >= 1 because w^T v = 1 forces a_0 ≠ 0. So rank 1.
- a_0 in B: its matrix is supported on the (1,1) block, which
lies in block upper triangular B (only the diagonal block (1,1)
nonzero).
So a_0 is a rank-one idempotent of B.
Lift to S. Since a_0 in B = ev_inf(S), there is b in S with
ev_inf(b) = a_0. Find it by k-linear solve: a basis (s_1, ..., s_d)
of S maps under ev_inf to a basis of B; solve for the coordinates
of a_0 in that basis.
Char poly of b. View b as an element of E ≈ M_q(K_0), acting
K_0-linearly on K_0^q. Its trace invariants tr(b^k) are K_0-valued
rational functions on P^1.
LEMMA 25.1 (tr(b^k) is constant). For every k >= 1, tr(b^k) is a
constant function in k.
Proof. Let v be any place of P^1.
(a) v generic unramified (including infinity): b in A_v =
M_q(R_v), so b^k in M_q(R_v), hence tr(b^k) in R_v. No pole at v.
(b) v = P_i ramified: b in A_{P_i} (maximal order of local division
algebra). Then b^k in A_{P_i}, and the reduced trace rtr(b^k) is
in R_v. Under the local splitting A_{P_i} ⊗ K_v^spl = M_q(K_v^spl),
the trace matrix of A_{P_i} matches the matrix trace, and rtr
is R_v-valued by construction.
Hence tr(b^k) has no poles anywhere on P^1. A rational function
with no poles on a smooth complete curve is constant. []
Residue at infinity. At z = 0, b mod z = a_0 (rank-one idempotent
in M_q(k)). Hence b^k mod z = a_0^k = a_0, and
tr(b^k) mod z = tr(a_0) = 1.
Since tr(b^k) is constant, tr(b^k) = 1 for every k >= 1.
Characteristic polynomial. Newton's identities relate p_k := tr(b^k)
to the elementary symmetric functions e_1, ..., e_q of eigenvalues.
Newton:
k e_k = sum_{j=1}^{k} (-1)^{j-1} e_{k-j} p_j, e_0 = 1. (25.7)
With p_j = 1 for all j >= 1:
e_1 = p_1 = 1;
e_2 = (e_1 p_1 - p_2)/2 = 0;
e_3 = (e_2 p_1 - e_1 p_2 + p_3)/3 = 0;
... e_k = 0 for 2 <= k <= q - 1;
e_q = 0 (in the q-th sum, the surviving terms are
-e_1 p_{q-1} + e_0 p_q = -1 + 1 = 0).
Hence
det(T - b) = T^q - e_1 T^{q-1} + (-1)^2 e_2 T^{q-2}
+ ... + (-1)^q e_q
= T^q - T^{q-1} = T^{q-1} (T - 1). (25.8)
Rank-one idempotent. Since char p > q, the factors T^{q-1} and
T - 1 are coprime (T = 1 is not a root of T^{q-1} unless q = 1).
The primary decomposition applies:
K_0^q = ker(b^{q-1}) ⊕ ker(b - 1) (25.9)
(routine: b-stable, disjoint since gcd = 1, sums to all of K_0^q by
dimension count - the two generalized eigenspaces account for both
eigenvalue 0 and eigenvalue 1).
Define e = b^q in E. Then
- On ker(b^{q-1}): b^{q-1} = 0, so b^q = b * b^{q-1} = 0.
- On ker(b-1): b = 1, so b^q = 1.
Therefore e is the projection onto ker(b - 1). That summand has
K_0-dim 1 (char poly has (T - 1) with multiplicity 1). So e is a
rank-one idempotent; tr(e) = dim(ker(b-1)) = 1.
Conclusion. Apply Lemma 23.2 to e. Obtain h in L^* with
prod_{j=0}^{q-1} rho^j(h) = G. This completes Theorem 23.1.
Every step is deterministic and uses only k-arithmetic and zero
tests: the local orders are constructed from explicit formulas, S
and B by k-linear algebra, ev_inf by reducing a basis, a_0 by the
trace-pairing kernel and its common kernel, b by a linear solve,
e = b^q by q-fold multiplication in E, and h by solving V e = h e.
All costs are polynomial in q, N, D, and log |k|.
================================================================================
26. Effective division by lambda
================================================================================
Setup. k finite, q odd prime, zeta in k of order q. F in k[X] monic
square-free, N = deg F divisible by q, all roots in k. Curve C/k:
Y^q = F(X), sigma = (X, Y -> zeta Y), lambda = 1 - sigma. We keep
the notation Lambda = sum_j a_j inf_j with sum a_j = 0 (the
infinity lattice of Section 16), e = inf_1 - inf_0 = -lambda(inf_0).
PROPOSITION 26.1 (Class division). Let P = (x, 0) be a k-rational
ramification point of C. Let D be a represented degree-zero divisor
over k. Suppose
char k > (N + 2||D|| + 1)^2
and the promise [D] in (1 - sigma) Pic^0(C)(k) holds. Then there is
a deterministic procedure LambdaDivide(D, P) returning a degree-zero
divisor D' over k satisfying
(1 - sigma) [D'] = [D], ||D'|| <= 2 g, (26.1)
with polynomial bit cost in representation size, q, N, ||D||, and
log |k|. The procedure is compatible with simultaneous execution
over A = k[T]/F(T).
Proof.
(1) Compression. Apply Lemma 21.2 to the fractional ideal I(D): get
monic h+, h- in k[X] with div(h+/h-) on P^1 equal to X_*D. Put
j = h+/h- in k(X)^*. Then
div_C(j) = sum_{a=0}^{q-1} sigma^a D. (26.2)
(2) Normalization. Let b = v_{X=x}(j) = v_{P}(D) (equal because
X_*D has coefficient v_P(D) at the point x above P; both P and x
are k-rational). Since F is monic with simple zeros at all x_i,
v_{X=x}(F) = 1, so v_{X=x}(j / F^b) = 0 and the quotient is a
nonzero unit at X = x. Compute
c = ((j / F^b)|_{X=x})^{-1} in k^*. (26.3)
Then G = c j in k(X)^* satisfies G / F^b |_{X=x} = 1.
(3) Norm promise for G. By the input promise, [D] = (1 - sigma)
[D_0] for some degree-zero D_0; by the finite-field descent principle
(Section 19) we may assume D_0 is k-rational. Then D - (1 - sigma)D_0
is principal. Take a_0 in L^* with
div(a_0) = D - (1 - sigma) D_0. (26.4)
Apply the orbit-sum map 1 + sigma + ... + sigma^{q-1} (which kills
both J and Lambda):
div(Norm_{L/K_0}(a_0)) = sum_{a=0}^{q-1} sigma^a div(a_0)
= div(j),
Norm_{L/K_0}(a_0) = c_0 j for some c_0 in k^*. (26.5)
At P: sigma fixes P and acts trivially on the residue field k, so
(1 - sigma) D_0 has coefficient 0 at P (it is a sigma-invariant
divisor; at a sigma-fixed point its coefficient is a multiple of
the ramification index, which is 1). Therefore v_P(a_0) =
v_P(D) = b.
Consider u = a_0 / Y^b in L^*. Its norm is
Norm(u) = Norm(a_0) / Norm(Y)^b = c_0 j / F^b,
because Norm_{L/K_0}(Y) = (-1)^{q-1} Y^q = F (q odd, so (-1)^{q-1}
= 1). At P, Y is a local uniformizer of C (Section 16.3), so
v_P(u) = v_P(a_0) - b v_P(Y) = b - b = 0; the value u(P) is defined
and nonzero.
Evaluate Norm(u) at X = x. Every deck transformation sigma^a fixes
P and acts trivially on k. So
u(P)^q = Norm(u)(P) = (c_0 j / F^b)|_{X=x}. (26.6)
By (26.3), the right side is c_0 * (j/F^b)|_{X=x} = c_0 / c. Hence
c / c_0 = u(P)^{-q} is a q-th power in k^*. Consequently
G = c j = (c / c_0) * c_0 j
= (q-th power) * Norm(a_0) in Norm_{L/K_0}(L^*). (26.7)
(4) Apply Theorem 23.1 (NormSolve) to G. Get a in L^* with
Norm_{L/K_0}(a) = G.
(5) Set E = D - div(a). This is a divisor on C, over k. By
(26.2) and (26.5),
sum_{a=0}^{q-1} sigma^a div(a) = div(Norm(a)) = div(c j) = div(j).
So sum_a sigma^a [E] = sum_a sigma^a [D] - div(j) = 0. In other
words E has degree-zero orbit sum.
(6) Partial sums. For 0 <= j <= q put
S_j = sum_{a=0}^{j-1} sigma^a E, S_0 = S_q = 0. (26.8)
Coefficientwise maximum V = max_{0 <= j < q} S_j (well-defined
because 0 is in the list; the max is over integer vectors on
divisor coefficients). Then by cyclic indexing sigma S_j = S_{j+1}
- E, so sigma V = V - E, i.e.
(1 - sigma) V = E. (26.9)
Since E's orbit sum is zero, the partial sums are bounded in degree
by ||E||; V is a divisor of degree bounded by ||E||.
(7) Reduction. The divisor V - (deg V) P is degree-zero (P is
sigma-fixed, so deg does not change under sigma). Return
D' = ReduceDivisor( V - (deg V) P ). (26.10)
Then [(1 - sigma) D'] = [(1 - sigma)V] = [E] = [D], and by
ReduceDivisor (21.6) we have ||D'|| <= 2g.
Cost. Compression: polynomial (Lemma 21.2). Normalization at X = x:
one local expansion. The norm solver uses parameters bounded by
||D|| and runs polynomially (Theorem 23.1); the hypothesis
char k > (N + 2||D|| + 1)^2 covers its characteristic need
(Section 23 p > (N+2D+1)^2 with D <= ||D||). Partial sums: q-1
applications of sigma to a divisor and q-1 coefficientwise maxima,
each polynomial. ReduceDivisor: polynomial (21.6). All steps use
arithmetic and zero tests over k, so simultaneous execution
applies. []
================================================================================
27. The odd splitter
================================================================================
PROPOSITION 27.1 (Odd-degree splitting, restated). Let p prime,
L = ceil(log2 p), B = 20 + (n+1)(L+1). Suppose p > B^{200000} and
F in F_p[X] is monic, square-free, totally split of odd degree
3 <= N <= n. Choose an odd prime q | N. Suppose supplied: a field
K/F_p of degree at most q - 1; a primitive q-th root of unity zeta
in K; an element omega_K in K^* of order q^{v_q(|K|-1)}. Then
OddSplit(F, q, K, zeta, omega_K) returns a nontrivial proper monic
divisor of F over F_p in bit operations bounded by a fixed polynomial
in B.
PROOF.
Setup. Put r = v_q(N) >= 1 and m = 1 + (q-1) r. Enlarge K to a
field k with [k:K] = q^r; then [k:F_p] <= N(q-1). By construction,
k contains F_p and the roots of F, and zeta in k of order q. The
characteristic cutoff p > B^{200000} gives the hypotheses required
by Section 19 (Frobenius filtration) and Proposition 26.1 (class
division). Specifically, for every t <= m and every class d in J(k)
with lambda^t d = [W] (W in Lambda), d has a rational representative
divisor over k (Section 19). All computations are simultaneous
over A = k[T]/F(T); any scalar test that separates components
immediately returns a factor of F over F_p (Lemma 9.1), and the
algorithm returns; otherwise all components proceed in lockstep
and the final factor, if obtained, splits into subsets of roots.
STEP 1 (lift each ramification class). In simultaneous execution
over A: in component i (associated with root x_i), start with
D = P_i - inf_0, (27.1)
a degree-zero divisor. Apply LambdaDivide(D, P_i) successively
m - 1 times, at each stage replacing D by its output. Write
d_{i, t} for the class after t - 1 divisions, so
d_{i, 1} = [P_i - inf_0] and d_{i, t+1} = output class of the t-th
division of d_{i, t}.
Invariant. For 1 <= t <= m:
lambda^t d_{i, t} = [e]. (27.2)
Proof by induction. At t = 1:
lambda d_{i, 1} = (1 - sigma)[P_i - inf_0]
= [P_i - sigma P_i] - [inf_0 - sigma inf_0]
= 0 - (inf_0 - inf_1) = [e].
Suppose lambda^{t-1} d_{i, t-1} = [e]. Since d_{i, t} is a
lambda-division of d_{i, t-1}, (1 - sigma) d_{i, t} = d_{i, t-1}.
Then lambda^t d_{i, t} = lambda^{t-1}(lambda d_{i, t}) =
lambda^{t-1} d_{i, t-1} = [e]. ✓
Each LambdaDivide call (Proposition 26.1) has its promise:
the input d_{i, t} is a lambda-division of d_{i, t+1}... more
directly, d_{i, t} is (1 - sigma)-divisible (it is (1 - sigma) of
d_{i, t+1} for t < m). And for the last call at t = m - 1, d_{i, m}
is (1 - sigma)-divisible by the Frobenius filtration lemma
(Section 19).
Each call's characteristic hypothesis holds: by the compression
bound (Lemma 21.2), ||D|| <= N throughout the chain (all D's have
absolute degree bounded by N), and (N + 2N + 1)^2 = (3N + 1)^2 < p.
STEP 2 (sum the lifts; downward chain). Simultaneous divisor sum
(Lemma 22.1) applied to the N divisors D_{i, m} representing the
d_{i, m}:
d_m = sum_{i=1}^N d_{i, m}. (27.3)
Reduce it to D_m (degree-zero, ||D_m|| <= 2g). For t = m - 1,
m - 2, ..., 1, reduce (1 - sigma) D_{t+1} to get D_t and set
d_t = [D_t]. Then
d_t = lambda^{m - t} d_m for 1 <= t <= m. (27.4)
Compute W_t = lambda^{-(t-1)} Ne. The solutions live in Lambda (not
just in J): Lambda is cyclic as an F_q[lambda]-module, lambda is
injective on Lambda (Section 16), and Ne = N inf_1 - N inf_0 has
leading coefficient N divisible by q^r, so Ne lies in the q^r-th
power of lambda Lambda, giving W_t for 1 <= t <= m via finite
linear systems on the cyclic infinity coordinates.
STEP 3 (test the labels). For t = 1, 2, ..., m:
(a) Compute h_t in k(C)^* with
div(h_t) = (1 - sigma) D_t - W_t. (27.5)
Existence. We verify [(1 - sigma) D_t] = [W_t] in J. Using
(27.4) with d_t = lambda^{m-t} d_m:
[(1 - sigma) D_t] = lambda d_t = lambda^{m-t+1} d_m. (27.5a)
And from (27.2) summed over i in (27.3):
lambda^m d_m = sum_i lambda^m d_{i, m} = sum_i [e] = [Ne],
because lambda^m d_{i, m} = [e] for each i (27.2) and
Ne = sum_i e = N e. Therefore
[W_t] = lambda^{-(t-1)} [Ne] = lambda^{-(t-1)} lambda^m d_m
= lambda^{m-t+1} d_m. (27.5b)
Comparing (27.5a) and (27.5b):
[(1 - sigma) D_t] = [W_t],
so (1 - sigma) D_t - W_t is principal, and h_t in k(C)^* with
(27.5) exists.
Compute h_t via circuit evaluation (Lemma 22.2): the circuit
represents h_t by small divisor reductions and produces
v_{P_i}(Z) = 0 and h_t(P_i) with bounded cost despite the
potentially enormous binary W_t coefficients.
(b) Evaluate h_t(P_i) and v_{P_i}(D_t) simultaneously (Lemma 22.2
evaluates h_t from the circuit; v_{P_i}(D_t) from the ideal
representation).
(c) Take the constant c_t := Norm(h_t) in k^*. This is a k^*-value
independent of i (Section 18(a) shows that Norm of a function
with divisor (1 - sigma)D - W is a nonzero constant). Extract
c_t as a scalar from A (Section 22.2).
(d) Room for roots: use UnitRoot (Lemma 11.1) with q, zeta, omega_K
to obtain gamma_t in k^* with gamma_t^q = c_t. (The q-primary
subgroup hypothesis needed by UnitRoot is supplied by
K = F_p(zeta) and omega_K.)
(e) Compute the ramification labels
l_{i, t} = v_{P_i}(D_t) - log_zeta(h_t(P_i)/gamma_t)
in F_q (mod q). (27.7)
Compare the N labels l_{1, t}, ..., l_{N, t} in F_q, simultaneously.
Because the whole computation is over A = k[T]/F, this comparison
is a simultaneous scalar test: if the labels differ for some
components, the zero tests produce a gcd g = gcd(F, some_element)
corresponding to the differing subset of roots. Return g (a
nontrivial proper monic divisor of F over F_p).
If all l_{i, t} agree for all i, proceed to next t.
(f) Correctness: Section 20 (Proposition 20.1) proves that the N
labels cannot all agree for all t = 1, ..., m. If they all did,
Equation (20.3) and the label test would force a fixed infinity
divisor W_m in lambda Lambda, contradicting (16.x) W_m notin
lambda Lambda. So a factor is returned at some t.
(g) Output descent. Every factor obtained by simultaneous execution
is in F_p[X]. Indeed, the gcd is over k, but it is the product
of (T - x_i) over a subset of the roots x_i in F_p; hence its
monic form is in F_p[X]. No additional descent of the output
is needed.
Cost. Every step is polynomial in B and log |k| = O(N log p) = O(B):
- Step 1: m - 1 <= (q - 1) r applications of LambdaDivide, each
polynomial (Prop. 26.1).
- Step 2: simultaneous divisor sum (Lemma 22.1) and O(m) reductions
of (1 - sigma) D_t, each polynomial.
- Step 3: q distinct calls to UnitRoot (one per root, but
simultaneously), each polynomial in q, N, log |k| (Lemma 11.1).
Circuit evaluation (Lemma 22.2) is polynomial. Label tests
are scalar q-th-root-of-unity comparisons in F_q, polynomial.
So OddSplit returns in time polynomial in B. []
The output factor is in F_p[X], nontrivial, proper. OddSplit runs
polynomially in B from start to finish.
================================================================================
28. Auxiliary table
================================================================================
CITED INPUT (from Section 31). For every prime q <= n there is an
auxiliary rational prime ell_q satisfying
ell_q not in {2, 3, p, q}, ell_q = 1 mod 12 q,
p^{(ell_q - 1)/q} not = 1 mod ell_q. (28.1)
Set E = max(2, max_{q <= n} ell_q). Supplied ell_q's are verified
by trial division and modular exponentiation in polynomial time in
E, n, and log p.
THE TABLE. For each prime q <= n:
- (q = 2) an element omega_2 in F_p^* of order 2^{v_2(p-1)};
- (q odd) an explicitly represented field K_q/F_p of degree at most
q - 1, an element zeta_q in K_q of order q with K_q = F_p(zeta_q),
and an element omega_q in K_q^* of order q^{v_q(|K_q| - 1)}.
"Explicit" means: a basis of K_q over F_p and its multiplication
constants, so that K_q-arithmetic and K_q-linear algebra are
polynomial in the representation size.
28.1 THE CYCLOTOMIC ALGEBRA R_ell AND A q-DEGREE FIELD
Fix an auxiliary prime ell = ell_q (so ell = 1 mod q). Define the
F_p-algebra
R_ell = F_p[T] / (1 + T + ... + T^{ell - 1}), (28.2)
dimension ell - 1. Over the algebraic closure,
R_ell ⊗ overline-F_p = overline-F_p^{ell - 1}, the algebra of
functions on the ell - 1 primitive ell-th roots of unity.
The group Gamma_ell = (Z/ell Z)^* acts by substitution
tau_a: T -> T^a. The subgroup
H_q = {a^q : a in Gamma_ell} (28.3)
has index q in Gamma_ell (a cyclic group of order ell - 1 = q *
multiple, so the q-th powers form the unique subgroup of index q).
Define
U_q = R_ell^{H_q} = intersection_{a in H_q} ker(tau_a - id), (28.4)
computed by F_p-linear algebra.
LEMMA 28.1. U_q is a field of degree q over F_p.
Proof. Over overline-F_p, R_ell is functions on mu_ell - 1, and H_q
acts freely with orbits of size (ell - 1)/q. The H_q-fixed part
consists of functions on H_q-orbits, isomorphic to overline-F_p^q.
So U_q is q-dimensional over F_p.
Non-splitting. Frobenius x -> x^p acts on mu_ell - 1 by
zeta -> zeta^p, i.e., on Gamma_ell by a -> ap. Mod H_q this is a
permutation of the q cosets Gamma_ell / H_q. By (28.1), the integer
p^{(ell - 1)/q} is not 1 mod ell, so p is not a q-th power mod ell,
so p notin H_q. Hence p generates the quotient Gamma_ell / H_q of
order q, and Frobenius acts TRANSITIVELY on the q cosets.
Therefore any F_p-rational idempotent of U_q (indicator of an
H_q-stable subset) is constant: equal to 0 or 1. So U_q has no
nontrivial idempotent, and being q-dimensional, is a field
F_{p^q}. []
Set K_q := U_q.
Multiplication constants: products of basis elements of U_q, reduced
in R_ell and re-expressed in the same basis.
A primitive q-th root zeta_q in K_q. Since |K_q^*| = p^q - 1 and
q | p^q - 1 (Fermat), K_q contains primitive q-th roots of unity.
Compute zeta_q: pick an element z in K_q not lying in a proper
subfield, and set zeta_q = z^{(p^q - 1)/q}. Or, in the specific
R_ell-coordinate model, read zeta_q directly from a suitable basis
combination. Either way, K_q = F_p(zeta_q) unless q divides p - 1,
in which case zeta_q lies in F_p and K_q = F_p with degree 1 <= q-1.
28.2 THE FULL q-PRIMARY GENERATOR omega_q
Let Q = |K_q| = p^q (or a lower power if K_q is smaller), and
s = s_q = v_q(Q - 1). The lifting-the-exponent identity (11.1) for
an odd prime q and integer a = 1 mod q:
v_q(a^m - 1) = v_q(a - 1) + v_q(m) for m >= 1. (28.5)
Apply with a = Q (which is 1 mod q by Fermat):
v_q(Q^m - 1) = s + v_q(m) for m >= 1. (28.6)
Build a degree-q-1 extension V_q of K_q where the q^{th}-root
difference lives: V_q = K_q[X] / (X^{q-1} + X^{q-2} + ... + 1),
of F_p-dimension q (q-1). Solve the K_q-linear equation
u^{Q - 1} = zeta_q in V_q^*. (28.7)
The LTE identity (28.6) combined with ord(u^{Q-1}) = q forces the
q-part of ord(u) to be q^{s+1}: if ord(u) has q-part q^{s+a} with
a >= 0, then gcd(ord(u), Q-1) has q-part q^{min(s+a, s)} = q^s,
so ord(u^{Q-1}) has q-part q^a = q, giving a = 1. The
prime-to-q part of ord(u) is killed by (Q^q - 1)/q^{s+1} (the
q-free part of Q^q - 1), which is a multiple of the q-free part
of ord(u).
Solving for u by Section 11's linear algebra (kernel basis, unit
search with c = 0, ..., h^2 where h = number of K_q factors in V_q).
Set
w = u^{(Q^q - 1) / q^{s+1}}, omega_q = w^q. (28.8)
Orders. From (28.6) with m = q: v_q(Q^q - 1) = s + v_q(q) = s + 1.
So the integer (Q^q - 1) / q^{s+1} is coprime to q.
We established above that ord(u) = q^{s+1}. Then
ord(w) = ord(u) / gcd(ord(u), (Q^q - 1)/q^{s+1})
= q^{s+1} / gcd(q^{s+1}, (Q^q-1)/q^{s+1})
= q^{s+1} / 1 = q^{s+1}.
Then omega_q = w^q has order q^{s+1} / gcd(q^{s+1}, q) = q^s.
Since q^s | Q - 1, the unique subgroup of V_q^* of order q^s lies
in K_q^*. So omega_q is in K_q^*. Extract its coordinates in the
K_q basis by solving the linear inclusion K_q -> V_q -> K_q^{q-1}.
No integer factorization of p - 1 or Q^q - 1 is used: only repeated
division by q (for valuations) and binary exponentiation.
28.3 THE INCREASING-DEGREE CONSTRUCTION
Build the table in increasing q order. At prime q:
- q = 2: no Factor call needed. Construct omega_2 of order
2^{v_2(p-1)} via the q=2 case of the cyclotomic construction (or,
equivalently, via the quadratic field U_2 with v^p = -v, c = v^2,
omega_2 = c^{(p-1)/2^{v_2(p-1)}}).
- q odd: construct K_q = U_q, zeta_q, omega_q via 28.1-28.2. The
construction calls Factor (Section 29 main routine) only on the
cyclotomic Phi_q of degree q - 1, whose prime factors are all
< q. By the induction hypothesis, table entries for primes
<= q - 1 already exist. So the Factor call at step q uses only
already-constructed entries.
Induction over q: at q = 2, direct. At odd q, build the entry using
already-existing entries. So the full table through n can be built
before the main call on the input polynomial.
Cost. Per entry, polynomial in ell_q and B (excluding the Factor
call, which is polynomial by the inductive hypothesis). Trial
division to verify ell_q, or upward search for a suitable ell_q, is
polynomial. So the entire table construction is polynomial in B
and E.
================================================================================
29. The recursive driver
================================================================================
Parameters. Fix n as the degree of the input f. Put
L = ceil(log2 p), B = 20 + (n + 1)(L + 1). (29.1)
Define the characteristic as "small" if p <= B^{200000}, "large"
otherwise.
LEMMA 29.1 (Separating element). Let h in F_p[X] be monic square-free
of degree d with r = dim B_h >= 2, and suppose p > r^3. Let
b_0, ..., b_{r-1} be an ordered F_p-basis of the Berlekamp algebra
B_h. Then there is t in {0, 1, ..., r^3} such that the characteristic
polynomial F_t of multiplication by
b(t) = sum_{j=0}^{r-1} t^j b_j (29.2)
on B_h is monic, square-free, and totally split over F_p. For any
such t and any nontrivial proper monic divisor S of F_t,
gcd(h, S(b(t))) in F_p[X] (29.3)
is a nontrivial proper monic divisor of h.
Proof. In coordinates B_h ≅ F_p^r, multiplication by b(t) is
diagonal with entries b_i(t) = sum_j t^j b_{i,j}. Char poly:
F_t(Y) = prod_{i=1}^r (Y - b_i(t)). (29.4)
Monic: clear. Totally split: all roots b_i(t) are in F_p.
Square-free: need b_i(t) ne b_j(t) for all i, j.
Fix i ne j. The difference b_i(t) - b_j(t) is a polynomial in t of
degree at most r-1. It is not identically zero: if it were, the
coordinate functionals "take the i-th coordinate" and "take the
j-th" would agree on all b_j basis vectors, hence on B_h, contradiction.
So b_i(t) - b_j(t) has at most r-1 roots. With binom(r, 2) pairs,
at most binom(r, 2)(r-1) < r^3 values of t are bad. Since p > r^3,
some t in {0, 1, ..., r^3} is good.
For the second claim, let S be a nontrivial proper monic divisor of
F_t. Its roots form a nonempty proper subset J of {1, ..., r}.
The element S(b(t)) in A_h = F_p[T]/(h(T)) has i-th coordinate S(b_i(t)),
zero iff b_i(t) is a root of S, i.e., iff i in J. So
gcd(h, S(b(t))) = product_{i in J} (T - x_i), a nontrivial proper
divisor. []
PROCEDURE Factor(h). Input: monic h in F_p[X] of degree b <= n.
Output: list of (monic irreducible g_i, multiplicity e_i) such that
h = prod_i g_i^{e_i}, with distinct monic irreducible g_i.
1. Base cases. deg h = 0: return []. deg h = 1: return [(h, 1)].
2. p-th-power case. Compute h'. If h' = 0, then h = g(X)^p for a
unique g (obtained by extracting p-th roots of the coefficients;
for a in F_p, a^{1/p} = a, so the coefficients are unchanged).
Recursively factor g, multiply every returned multiplicity by p,
return.
3. Square-free split. If h' ne 0, compute d_0 = gcd(h, h'). If
d_0 ne 1, recursively factor d_0 and h/d_0, merge by adding
multiplicities of equal factors, return.
4. Irreducibility test. Now h square-free. Compute Berlekamp algebra
B_h = {a in A_h : a^p = a}, (29.5)
the kernel of the F_p-linear map a -> a^p - a (Frobenius minus
identity) on A_h; the matrix of Frobenius is obtained by powering
the standard basis. Let r = dim B_h. If r = 1, return [(h, 1)].
5. Small-characteristic split. If p <= B^{200000} and r >= 2:
find a nonscalar b in B_h (test basis elements against the
one-dimensional F_p * 1 subspace). Test gcd(h, b - a) for
a = 0, 1, ..., p - 1 until a nontrivial proper gcd is found.
Denote it h_1.
6. Large-characteristic split. If p > B^{200000} and r >= 2:
apply Lemma 29.1 to b_0, ..., b_{r-1} (basis of B_h) to obtain
t, b(t), F_t. Compute S = Split(F_t) via EvenSplit (Section 13)
if r even or OddSplit (Section 27) if r odd. Set
h_1 = gcd(h, S(b(t))).
7. Recursion. Specialize h_1 (nonconstant proper divisor) and
h/h_1, recursively factor both, merge.
CORRECTNESS AND TABLE CONTRACT.
PROPOSITION 29.2. Fix n, p, B as in (29.1). For every monic
h in F_p[X] of degree b <= n, Factor(h) terminates and returns the
complete irreducible factorization of h. In the large-characteristic
case this assumes the primary table through b; no entry for a prime
> b is used. The number of recursive calls for one input h is
O((b+1)^2).
Proof (induction on b).
Base cases (b = 0, 1): direct.
Step 2: h' = 0 iff every nonconstant exponent in h is divisible by
p, iff h = g(X)^p. Every a in F_p is its own p-th root
(Frobenius fixes F_p), so g's coefficients a^{1/p} equal the
original a. Recursion on g has smaller degree; multiplicities
multiplied by p. ✓
Step 3: d_0 = gcd(h, h') is proper (deg h' < deg h). Both recursive
arguments have smaller positive degree and multiply to h/d_1 or h...
more directly: h = d_0 * (h/d_0), and d_0, h/d_0 both have degree
< b. Recursions give factorization; merge handles repeated factors
(they need not be coprime). ✓
Step 4: dim B_h = number of distinct irreducible factors of h
(Berlekamp). r = 1 iff h irreducible. ✓
Step 5: nonscalar b in B_h has at least two distinct coordinate
values (b(x_i)). Pick a = one attained value; gcd(h, b - a) contains
exactly the X - x_i with b(x_i) = a. Nonconstant proper. ✓
Step 6: Separating element. ✓
Step 7: Two smaller-degree recursions. ✓
Termination: degrees decrease strictly. Total calls: at each level,
the degrees sum to at most b, so at most b + 1 nodes per level; depth
at most b + 1; O((b+1)^2) calls. ✓
Table contract: each Split(F_t) has deg F_t = r <= deg h = b. By
Sections 13 (EvenSplit) and 27 (OddSplit), the splitter uses only
table entries for primes <= its input degree <= b. All Factor
recursions have degree <= b. So entries only <= b. ✓
[]
THE ORIGINAL INPUT f.
For the original nonzero f in F_p[X], deg f = n, leading coefficient
c:
- deg f = 0: return (c, []).
- Otherwise h = f / c is monic of degree n.
- deg h <= 1: no table needed, direct.
- Small characteristic (p <= B^{200000}): use Factor(h) directly
(Step 5's scalar search handles all splitting).
- Large characteristic: build the table (Section 28) through
primes <= n by induction; then apply Factor(h).
MAIN THEOREM (restated from Section 1). For every prime p and every
nonzero f in F_p[X] given as a dense coefficient list, the complete
factorization f = c * prod_i g_i^{e_i} can be computed
deterministically in bit operations polynomial in (deg f + 1) *
ceil(log2 p).
Proof. Preprocessing (Section 28) is polynomial in E = max ell_q and
B. Factor(h) via Proposition 29.2 is polynomial in B given the
table. Each table entry (Section 28) calls Factor only at degrees
< q (Phi_q of degree q-1), so no circularity. The analytic input
(Section 31) gives auxiliary primes ell_q polynomial in B, so
E = poly(B). Total: polynomial in B = 20 + (n+1)(L+1), i.e.,
polynomial in the input size. []
The explicit bit count is the subject of Section 30.
================================================================================
30. Uniform bit complexity
================================================================================
Convention. B = 20 + (n+1)(L+1). Dense polynomial arithmetic, ordinary
Gaussian elimination. We charge for memory addresses as well as
arithmetic; a quadratic overhead converts an address-charged count
to a sequential-memory count. The exponents below are deliberately
generous: the goal is polynomial, not tight.
PROPOSITION 30.1. Let E = max auxiliary prime (or 2 if none needed).
The complete algorithm Factor + preprocessing uses
O(B^{500000} + B^{100} E^{20}) (30.1)
bit operations. Same bound if the auxiliary primes are found by
upward search (E = largest found). In particular if
E = O(B^{20000000}), the total is O(((n+1)L)^{10^{12}}).
Proof. Bound one call of each component.
(a) NormSolve (Section 23). Per call O(B^{2000}) bit. The input G
has numerator and denominator degrees <= ||D|| <= B^3 (compression,
Section 21.2). Largest intermediate dimension <= B^{65}. Largest
linear system < B^{30} scalar parameters. Intermediate function
coefficient degrees <= B^{20}, divisor norm ||div h|| <= B^{40}.
(b) Divisor arithmetic (Section 21, 22). Per operation
O((U')^{30}) scalar field ops with U' = B^{200} (input divisor
degree <= B^{46}, coefficient degrees <= B^{60}, bivariate
multiplication at most quadratic degree each), giving O(B^{6000})
bit.
(c) LambdaDivide (Section 26). One NormSolve (O(B^{2000})) plus
orbit sums (q <= B partial sums, each O(B^{6000})) plus one
ReduceDivisor (O(B^{6000})). Total O(B^{6000}) bit per call.
(d) OddSplit (Section 27). At most m - 1 <= (q-1)r <= B
LambdaDivide calls per root; N <= B roots; all simultaneous.
Sum the lifts (one Lemma 22.1 call). Then <= m <= B label tests,
each doing circuit evaluation (Lemma 22.2, poly in B^{50} bit
length of W_t), one UnitRoot (Lemma 11.1, poly in B at d <= B),
and one label comparison (poly in q <= B, log |k| <= B). Total
O(B^{7000}) bit per OddSplit.
(e) EvenSplit (Section 13). Algebra dimension N^2 <= B^2, s <= B
levels, at most B^2 pieces of size q = 2, two candidate digits.
Total O(B^{5}) pieces, poly cost: O(B^{100}) bit per call.
(f) Factor / driver (Section 29). Each call does Berlekamp (poly
in deg h <= B) plus a splitting call.
Small-character branch: at most B^{200000} scalar trials, each poly
cost, so O(B^{200004}) bit per call.
Large-character branch: one EvenSplit or OddSplit (B^{7000}), so
O(B^{7000}) per call.
At most O(B^2) recursive Factor calls, so:
small char total: O(B^{200006})
large char total: O(B^{7002})
(g) Table (Section 28). Per entry: R_ell dimension <= E,
substitution operators via modular poly powering, fixed-space
system <= E unknowns, at most E elements of H_q, q <= B digits.
Poly in E and B per entry. Excluding the recursive Factor call
(which is polynomial by the inductive hypothesis), total
O(B^{40} E^{10}) per entry. At most B entries: O(B^{41} E^{10}).
(h) Sum. Small-char driver + large-char driver + table:
O(B^{200006} + B^{7002} + B^{41} E^{10}).
Enlarge B^{200006} to B^{500000}; enlarge B^{7002} + B^{41} E^{10}
to B^{100} E^{20} (which dominates for E >= 2 and B >= 20). Result:
O(B^{500000} + B^{100} E^{20}).
If E = O(B^{20000000}), then B^{100} E^{20} = O(B^{400000100}).
With B = O((n+1)L), total = O(((n+1)L)^{400000100}) which is at
most ((n+1)L)^{10^{12}}. ✓
[]
COROLLARY 30.2. The complete algorithm Factor + preprocessing runs
in O(((n+1)L)^{10^{12}}) bit operations, hence in polynomial bit
cost in the input size.
Proof. By Proposition 30.1 with E = O(B^{20000000}) from
Corollary 31.3 below. []
================================================================================
31. Small auxiliary primes from a uniform zero-free strip
================================================================================
We have reduced the main algorithm to: given explicit auxiliary
primes ell_q satisfying (28.1) for each prime q <= n, Factor runs
in polynomial bit cost in B and E. It remains to prove that
suitable ell_q exist with E polynomial in B.
Analytic input. The companion paper [OpenAIPrimitive26] proves a
uniform zero-free region for finite-order Hecke L-functions:
THEOREM 31.1 (Uniform Hecke zero-free strip; companion paper
Theorem 1.2). There is an absolute constant delta > 0 such that
the following holds. For any number field K with discriminant D_K
and degree [K:Q] = m, any finite-order Hecke character chi of K,
and any T >= 2, the function L(s, chi) has no zero in the region
Re(s) > 1 - delta, |Im(s)| <= T,
except for at most one exceptional main-character zero beta in
(1 - delta, 1), with 1 - beta bounded below by a fixed multiple of
1 / (log(D_K T) + m).
Consequence (smoothed explicit formula). Let Phi: [0, inf) -> [0, 1]
be a fixed smooth compactly supported bump with Phi(1) > 0. Then
for any number field K with discriminant D_K and degree m, and any
T >= 2, the smoothed prime count
Psi_K(x) := sum_{N(a) <= 2x} Phi(N(a)/x) Lambda_K(a) (31.1)
with Lambda_K the von Mangoldt function on ideals satisfies
Psi_K(x) = x Phi(1) + O_Phi(x^{1 - delta} (log D_K + m log x)). (31.2)
Applying to the tower M/K, with zeta_M a product of q Hecke
L-functions over K (Abelian zeta factorization, Neukirch):
LEMMA 31.2. With K, M as in the setup below, and arbitrary T >= 2,
Psi_K(x) - q^{-1} Psi_M(x)
= (1 - q^{-1}) x Phi(1) + O_Phi(x^{1 - delta} B^3). (31.3)
Setup for the auxiliary prime. For an odd prime q <= n, put
K = Q(mu_{12q}), M = K(p^{1/q}). (31.4)
[K:Q] <= 12 q and [M:Q] <= 12 q^2. Since p is large (p > 2 for our
algorithm), q | N and p is unramified in K = Q(mu_{12q}), the
polynomial X^q - p is Eisenstein at any prime of K over p, so
[M:K] = q. Since mu_q ⊆ K, this makes M/K cyclic, so zeta_M
factors as a product of q Hecke L-functions over K.
Log discriminants:
log D_K <= [K:Q] log(12q) <= 12q log(12q);
log D_M <= q log D_K + [K:Q](q log q + (q-1) log p).
With q, n, L <= B, both fields satisfy
log D + [K:Q] << B^3. (31.5)
So in (31.3) the error term is O_Phi(x^{1 - delta} B^3).
Scale. Take x = T B^{20000000}, with T >= 2 an absolute constant
to be chosen. Error / main term = O_Phi(T^{-delta} B^{-17}), so
much less than 1; the main term (1 - q^{-1}) x Phi(1) dominates.
Subtract low-order contributions:
(i) Prime powers with exponent j >= 2: at most
O_Phi([K:Q] * x^{1/2} log^2(2x)) (via Hardy-Ramanujan-type
counting for prime ideals of residue degree >= 2 and higher
powers).
(ii) The prime ideals over {2, 3, p, q}: O_Phi([K:Q] log(2x)).
Both are o(x); enlarging the constant T (which enters through the
T^{-delta} error) makes their sum less than c_1 x for a fixed
c_1 > 0.
Remaining first-power-degree-one primes of K. These lie over
rational primes ell = 1 mod 12q with ell not in {2, 3, p, q} (so
ell splits completely in K = Q(mu_{12q})). For such ell:
- If p^{(ell-1)/q} = 1 mod ell: X^q - p has a root mod ell, so ell
splits completely in M and contributes q primes above it in M.
Then the contribution of ell to Psi_K is exactly cancelled by
its contribution to q^{-1} Psi_M.
- If p^{(ell-1)/q} ne 1 mod ell: X^q - p is irreducible mod ell,
and ell DOES NOT split in M/K. This ell is a valid auxiliary
prime satisfying (28.1).
So if no auxiliary prime lies in (x, 2x), the difference
Psi_K - Psi_M/q is bounded by the error terms (all remaining
"first-power degree-one" contributions cancel, prime-squares and
prime-cubes are small, exceptional prime ideals above small
rationals are small). But (31.3) with the error at scale
x = T B^{20000000} shows the difference is at least c_1 x for
large T. Contradiction.
Therefore, for every q <= n, an auxiliary prime ell_q exists with
ell_q in (x, 2x), i.e.,
ell_q <= 2 T B^{20000000}. (31.6)
COROLLARY 31.3. Take E = max_{q <= n} ell_q <= 2 T B^{20000000}. Then
the bit cost bound (30.1) of Proposition 30.1 becomes
O(((n+1)L)^{10^{12}}). (31.7)
Therefore the complete algorithm Factor + preprocessing runs in
polynomial bit cost in the input size.
================================================================================
32. Conclusion: the shape of the proof
================================================================================
We have completed a deterministic polynomial-time factorization
over any prime field. Let us review the main steps so the whole
outline stays visible.
The problem. Given f in F_p[X], find its complete factorization
f = c * prod_i g_i^{e_i}, g_i distinct monic irreducible,
e_i positive integers.
Trial division over roots works only if p is small (O(p) work);
polynomial in p is exponential in log p. The challenge is p huge.
The randomized algorithm (Cantor-Zassenhaus). For f monic square-
free, pick a random c in F_p and compute gcd(f, (X + c)^{(p-1)/2} - 1).
Each c splits with probability >= 1/2 (pair separation). Expected
polynomial time, no deterministic guarantee.
Berlekamp (the reduction). For square-free f, compute the Berlekamp
algebra B_f = {a in A_f : a^p = a}. Its dimension equals the number
r of distinct irreducible factors. If r = 1, f is irreducible. If
r >= 2, need to split further.
The main driver (Section 29). Two splitting procedures:
- Small p (p <= B^{200000} ~ poly(n, L)): scalar search
gcd(h, b - a) for a = 0, ..., p - 1 over nonscalar b in B_h.
- Large p: use a separating element (Lemma 29.1) to reduce F_t
(degree r, totally split), split it with EvenSplit or OddSplit.
At most O((b+1)^2) recursive calls, each polynomial.
The two splitters.
EvenSplit (Sections 12, 13). A 2-primary generator u of F_p^*
suffices. Compute e = Delta^{p-1} in the algebra A (x)_F_p A, where
Delta = T (x) 1 - 1 (x) T
has coordinate x_i - x_j on the ordered pair (i, j). e = Delta^{p-1}
is 1 on off-diagonal components, 0 on the diagonal. Delta^t has
2-power order on eR. Extract ell_{ij} in [0, 2^s) from
(x_i - x_j)^t = u^{ell_{ij}}. Exactly one of ell_{ij}, ell_{ji} =
ell_{ij} + 2^{s-1} lies in [0, 2^{s-1}). The out-degree counts c_i
sum to N(N-1)/2; if all equal, each equals (N-1)/2, impossible for
even N. So c_i separates the roots, giving a factor.
OddSplit (Sections 14-27). Uses an odd prime q | N of the input
degree. Consider C: Y^q = F(X), a smooth projective curve with
genus g = (q-1)(N-2)/2. Work in the Jacobian J. The operator
lambda = 1 - sigma acts on J and on the infinity lattice
Lambda = {sum a_j inf_j : sum a_j = 0}.
Lambda is a cyclic F_q[lambda]-module; lambda is INJECTIVE on
Lambda. But lambda is SURJECTIVE on J. This mismatch is the
mechanism.
Lift each ramification class [P_i - inf_0] repeatedly via class
division (Proposition 26.1) ignoring the mystery of what the lift
"looks like"; the lifts exist and stay rational over an explicit
extension k of degree q^{v_q(N)}. Sum the lifts.
Compare labels. The lift lives in a chain of modules T_1, T_2, ...,
T_m with T_1 = sum F_q * epsilon_i and sum epsilon_i = 0 in T_1.
Each class (D, W) in T_1 has a ramification-label expansion
(D, W) = sum l_i epsilon_i, l_i in F_q.
The l_i are computed from the function h with
div(h) = (1 - sigma) D - W and a q-th root of unity gamma with
gamma^q = Norm(h):
l_i = v_{P_i}(D) - log_zeta(h(P_i)/gamma) mod q.
If the labels are unequal, they immediately separate roots and give
a factor. If all labels agree at every stage t = 1, ..., m, the
agreement would force a lattice-level impossibility (W_m notin
lambda Lambda), contradiction. So a factor IS obtained.
The two critical tools.
NormSolve (Theorem 23.1). Given a norm G = prod rho^j(h), construct
h. Uses a cyclic algebra E = oplus_{j<q} L V^j with V^q = G. Find a
rank-one idempotent e in E via maximal orders, global sections, and
the fiber idempotent a_0 = v w^T in B = ev_inf(S). Extract h via
V e = h e.
Auxiliary table (Section 28). For each q <= n, get K_q = F_{p^q},
zeta_q of order q, and omega_q of order q^{v_q(p^q - 1)}. Built
from R_ell = F_p[T]/(1 + T + ... + T^{ell-1}) with H_q-fixed part
U_q (Lemma 28.1: field of degree q, using the auxiliary condition
p^{(ell-1)/q} ne 1 mod ell for Frobenius transitivity).
The analytic input (Section 31). The auxiliary primes ell_q exist
with ell_q <= 2T B^{20000000}, from the uniform Hecke zero-free
strip of the companion paper [OpenAIPrimitive26].
The result (Theorem 1.1, Proposition 30.1, Corollary 31.3). The
complete factorization is computable deterministically in
O(((n+1)L)^{10^{12}}) bit operations, which is polynomial in the
input size.
Two case distinctions matter. Small-vs-large characteristic (p vs
B^{200000}) decides whether scalar search or separating-element
reduction is used. Even-vs-odd degree of F_t decides whether the
2-primary tournament or the lambda-division machinery applies.
Randomness is replaced by the algebraic structure of the split
algebra (small p) or by the number theory of the q-cover (large p).
Determinism comes from the uniformity of the analytic input, not
from the algebraic constructions themselves.