arXiv:1504.07697v2 [cs.CC] 11 Jul 2016

POLYNOMIAL FACTORIZATION OVER FINITE FIELDS BY COMPUTING
EULER-POINCARE CHARACTERISTICS OF DRINFELD MODULES
ANAND KUMAR NARAYANAN
anandkn@caltech.edu

Abstract. We propose and rigorously analyze two randomized algorithms to factor univariate polynomials over finite fields using rank 2 Drinfeld modules. The first algorithm estimates the degree of
an irreducible factor of a polynomial from Euler-Poincare characteristics of random Drinfeld modules.
Knowledge of a factor degree allows one to rapidly extract all factors of that degree. As a consequence,
the problem of factoring polynomials over finite fields in time nearly linear in the degree is reduced to
finding Euler-Poincare characteristics of random Drinfeld modules with high probability. The second
algorithm is a random Drinfeld module analogue of Berlekamp’s algorithm. During the course of its
analysis, we prove a new bound on degree distributions in factorization patterns of polynomials over
finite fields in certain short intervals.

1. Introduction
1.1. Current State of the Art. Let Fq denote the finite field with q elements and Fq [t] the polynomial
ring in one indeterminate. The fastest known randomized algorithm for factorization in Fq [t] is the
Kaltofen-Shoup algorithm [KS98, § 2] implemented by Kedlaya-Umans fast modular composition [KU08].
It belongs in the Cantor-Zassenhaus [CZ81] framework and to factor a polynomial of degree n takes
e 3/2 log q + n log2 q) expected time by employing the following sequence of steps1. The first is square
O(n
free factorization where the polynomial in question is written as a product of square free polynomials. A
square free polynomial is one that does not contain a square of an irreducible polynomial as a factor. The
second step known as distinct degree factorization takes a monic square free polynomial and decomposes
it into factors each of which is a product of irreducible polynomials of the same degree. The final step
is equal degree factorization which splits a polynomial all of whose irreducible factors are of the same
degree into irreducible factors. The bottleneck is distinct degree factorization and currently the difficulty
appears to be in finding the factor degrees. Given the degree of a factor, one can extract all factors of
e log2 q) expected time [KU08].
that degree in O(n

1.2. Polynomial Factorization and Euler-Poincare Characteristic of Drinfeld Modules. We
propose a novel procedure to read off the smallest factor degree of a monic square free polynomial
h ∈ Fq [t] from the Euler-Poincare characteristic χφ,h of a random rank 2 Drinfeld module φ reduced
at h. The reduction of φ at h is a finite Fq [t]-module and its Euler-Poincare characteristic χφ,h ∈ Fq [t]
(see Q
Definition 2.1) is an
Q Fq [t] valued cardinality measure. If h factors into monic irreducible factors as
h = i pi , then χφ,h = i χφ,pi . A Drinfeld module analogue of Hasse’s theorem for elliptic curves, due to
Gekeler [Gek91], asserts for each pi that χφ,pi = pi + cφ,i for some cφ,i ∈ Fq [t] with deg(cφ,i ) ≤ deg(pi )/2.
Hence, the leading coefficients of h and χφ,h agree and the number of agreements reveals information
about the degree of the smallest degree factor of h. In § 3, we prove,
The author was partially supported by NSF grant CCF 1423544.
1The soft O
e notation suppresses no(1) and logo(1) q terms for ease of exposition.
1

2

ANAND KUMAR NARAYANAN

√
Theorem 1.1. For n ≤ q/2, the smallest factor degree of a degree n square free h ∈ Fq [t] can be
inferred in O(n log q) time from χφ,h with probability at least 1/4 for a randomly chosen φ.
Consider an algorithm B that takes a square free h ∈ Fq [t] and a random Drinfeld module φ as inputs
such that with constant probability the output B(h, φ) is χφ,h . That is, B is a montecarlo algorithm to
compute Euler-Poincare characteristics. By choosing φ at random and invoking Theorem 1.1, we establish
that a non trivial factor can be found in nearly linear time with oracle access to B.
e log2 q) expected time algorithm (with oracle access to B) to find an
Corollary 1.2. There exists an O(n
√
irreducible factor of a square free polynomial h ∈ Fq [t] of degree n ≤ q/2 with only O(1) queries to B,
each of the form B(h).
√
The requirement q ≥ 2n in Theorem 1.1 and Corollary 1.2 is without loss of generality since if q were
√
smaller, we could choose a small power q ′ of q that satisfies q ′ ≥ 2n and obtain the factorization over
Fq′ [t] with the running time unchanged up to polylogarithmic factors in n (see Remark 3.2).
Given oracle access to B, obtaining the complete factorization by naively extracting one factor at a
time using Corollary 1.2 leads to a 3/2 running time exponent on n. For instance, a polynomial of degree
n with one irreducible factor each of degree 1, 2, 3, . . . , m − 1, m where m = Θ(n1/2 ) requires Θ(n1/2 )
extractions. In [GNU15], an algorithm to quickly obtain the complete factorization given a procedure
to extract a non trivial factor as a subroutine is described. As a consequence, an algorithm for implementing B with exponent less than 3/2 would lead to a polynomial factorization algorithm with exponent
less than 3/2. As an illustration, in § 3.2, we obtain the following corollary of Theorem 1.1 describing
an implication of a nearly linear time algorithm for computing Euler-Poincare characteristic of random
Drinfeld modules.
e logO(1) q) expected time for
Corollary 1.3. An implementation of the oracle function B that takes O(n
O(1)
4/3
e
inputs of degree n yields an O(n
log
q) expected time polynomial factorization algorithm.

We describe our first complete polynomial factorization algorithm by presenting an implementation of B.
Assuming the matrix multiplication exponent ω is 2, our implementation of B and hence the polynomial
factorization algorithm both have running time exponent 3/2 in the input degree. A faster implementation of B would break the 3/2 exponent barrier in polynomial factorization. Thus, the problem of
computing Euler-Poincare characteristics of random Drinfeld modules warrants a thorough investigation.
The problem is analogous to point counting on elliptic curves over finite fields and the question as to if
there is a Drinfeld module analogue of Schoof’s algorithm [Sch95] is immediate.
We next briefly sketch our implementation of B. The obvious procedure to compute χφ,h for a given
a square free h ∈ A and a rank 2 Drinfeld module φ, is to compute the characteristic polynomial of the
(Fq linear) φ action on Fq [t]/(h). However, the complexity of such generic linear algebraic techniques is
equivalent to inverting square matrices of dimension deg(h). We devise a faster implementation of B by
exploiting the fact that the input φ to B is chosen at random. For q ≥ 2 deg(h)4 , which we may assume
without loss of generality, we prove it is likely that the reduction of a random φ at h is a cyclic Fq [t]module and further that χφ,h coincides with the order (that is, the monic generator of the annihilator)
of a random element in φ reduced at h. Implementing B is thus reduced to the finding the order of a
random element in a random Drinfeld module φ reduced at h with constant probability. In § 3.1, we
solve the order finding problem by posing it as an instance of the automorphism projection problem of
e (1+ω)/2 log q + n log2 q) expected time algorithm to find
Kaltofen-Shoup [KS98] and thereby obtain an O(n
a factor. In § 3.2, we describe how to obtain the complete factorization.

POLYNOMIAL FACTORIZATION AND EULER-POINCARE CHARACTERISTICS OF DRINFELD MODULES

3

1.3. Drinfeld Module Analog of Berlekemp’s Algorithm. Our second algorithm is a randomized
Drinfeld analogue of Berlekamp’s algorithm [Ber67] wherein Fq [t]-modules twisted by the Frobenius action is replaced with reductions of random rank-2 Drinfeld modules. It has the distinction of being the
only polynomial factorization algorithm over finite fields that does not involve a quadratic residuosity
like map. To factor h ∈ Fq [t], Berlekamp’s algorithm proceeds by finding a basis for the Berlekamp
subalgebra, which is the fixed space of the q th power Frobenius τ acting on Fq [t]/(h). Then (as in the
Cantor-Zassenhaus [CZ81] variant) a random element β in the Berlekamp subalgebra is generated by
taking a random Fq linear combination of the basis elements. When q is odd, with probability at least
half, the greatest common divisor of h and a lift of β (q−1)/2 − 1 is a non trivial factor of h. In place of
the Fq [t]-module Fq [t]/(h) and its Berlekamp subalgebra (which is the τ − 1 torsion in Fq [t]/(h)), our
second algorithm works over a random Drinfeld module reduced at h and its torsion corresponding to
low degree polynomials in the Drinfeld action. These low degree polynomials are precisely the low degree
factors of χφ,h . In terms of implementation, the algorithm closely resembles the fast black-box algorithm
e (1+ω)/2+o(1) log q + n log2 q) expected running time.
of Kaltofen-Shoup [KS98, § 3] and shares its O(n
Our analysis of the Drinfeld analogue of Berlekamp’s algorithm relies on bounds on the degree distribution of factorization patterns of polynomials in short intervals in Fq [t]. We prove the required
bounds, but only when q is very large compared to n. When q is not large enough, the claimed running
times hold under a widely believed conjecture (see Conjecture 4.2) and a slower running time bound is
proven unconditionally (see Remark 5.3). We next state the bounds for large q since they might be of
independent interest.

1.4. Factorization Patterns of Polynomials in Short Intervals. For a partition λ of a positive
integer d, let P (λ) denote the fraction of permutations on d letters whose cycle decompositions correspond
to λ. When q is large enough compared to d, a random polynomial in Fq [t] of degree d has a factorization
pattern corresponding to a partition λ of d with probability about P (λ) [Coh]. In § 4, we prove that the
degree distribution of a random polynomial in the interval If,m := {f + a|a ∈ Fq [t], deg(a) ≤ m} around
f ∈ Fq [t] is not far from the degree distribution of a random polynomial of degree d.
Theorem 1.4. For every f ∈ Fq [t] of degree d bounded by log q ≥ 3d log d, for every m ≥ 2 and for every
partition λ of d,




|{g ∈ If,m |λg = λ}|
1
1
P (λ) ≤
≤ 1+ √
1− √
P (λ)
q
|If,m |
q

where λg denotes the partition of deg(g) induced by the degrees of the irreducible factors of g.

1.5. Related Work. Our algorithms draw inspiration from Lenstra’s elliptic curve integer factorization
[Len87] where the role of multiplicative groups modulo primes in Pollard’s p − 1 algorithm [Pol74] was
recast with the group of rational points on random Elliptic curves modulo primes. Our first algorithm
for degree estimation using Euler-Poincare characteristic is a random Drinfeld module analogue of an
algorithm described in the author’s Ph.D thesis [Nar14, Chap 7] using Carlitz modules. To our knowledge,
the use of Drinfeld modules to factor polynomials over finite fields originated with Panchishkin and
Potemine [PP89] whose algorithm was rediscovered by van der Heiden [vdH04] (see also [vdH04-1]). Our
Drinfeld module analogue of Berlekamp’s algorithm shares some similarities with the algorithm in [vdH04]
but they differ in the following aspects. In contrast to our algorithm, the algorithm in [vdH04] only works
for equal degree factorization and targets torsion corresponding to large degree polynomials to aid in the
splitting; resulting in a slower running time. Further, its analysis was merely supported by heuristics.
Using Theorem 1.4 and Lemma 2.3, the proof of Lemma 5.2 can be extended to rigorously analyze the
algorithm in [vdH04] for large q when restricted to rank 2 Drinfeld modules.

4

ANAND KUMAR NARAYANAN

1.6. Organization. The analysis of our algorithms rely critically on the distribution of the characteristic polynomial (of the Frobenius endomorphism in the representation of the endomorphism ring) of a
random rank 2 Drinfeld module (on its ℓ-adic Tate modules). In § 2, we prove Lemma 2.3, the required
equidistribution lemma on the aforementioned characteristic polynomial. We begin § 2 by recounting the
theory of rank 2 Drinfeld modules followed by § 2.1, where the structure of rank 2 Drinfeld modules in
terms of its characteristic polynomial is described. In § 2.2, we state a weighted class number formula for
isomorphism classes of Drinfeld modules with a given characteristic polynomial (due to Gekeler [Gek08])
and from it derive Lemma 2.3. Gekeler’s weighted class number formula is obtained through complex
multiplication theory, that is, a correspondence between isomorphism classes of Drinfeld modules and
Gauss class numbers in certain imaginary quadratic orders. While they hold in even characteristic, for
ease of exposition, we assume in § 2.2 and consequently in the analysis of our algorithms that q is odd.
In § 3, we state and analyze our first algorithm, namely to estimate factor degrees by computing EulerPoincare characteristic and prove Theorem 1.1 and Corollaries 1.2 and 1.3. Theorem 1.4 concerning
factorization patterns of polynomials in short intervals is proven in § 4, which can be read independent
of the rest of the paper. The Drinfeld analogue of Berlekamp’s algorithm is described and analyzed in § 5.
A remarkable
feature of our algorithms andQreductions is that we address the factorization of a square
Q
free h = i pi ∈ Fq [t] by looking at χφ,h = i χφ,pi for random φ. We may view χφ,h as a perturbation
of h, since χφ,pi is the irreducible factor pi of h perturbed within a half degree (of pi ) interval. These
intervals widen with Drinfeld modules of increasing rank. Theorem 1.4 and Lemma 2.3 together imply
that even for rank 2, the intervals are large enough for χφ,pi to exhibit random factorization patterns.
This allowed us to pose the worst case complexity of polynomial factorization in terms of an average
complexity statement (Corollary 1.3) concerning Drinfeld modules. It would be interesting to see if this
perturbation leads to worst case to average case reductions for other multiplicative problems.
2. Finite Rank-2 Drinfeld Modules
Let A = Fq [t] denote the polynomial ring in the indeterminate t and let K be a field with a non zero ring
homomorphism γ : A → K. Necessarily, K contains Fq as a subfield. Fix an algebraic closure K̄ of K
and let τ : K̄ −→ K̄ denote the q th power Frobenius endomorphism. The ring of endomorphisms of the
additive group scheme Ga over K can be identified with the skew polynomial ring Khτ i where τ satisfies
the commutation rule ∀u ∈ K, τ u = uq τ . A rank-2 Drinfeld module over K is (the A-module structure
on Ga given by) a ring homomorphism
φ : A −→ Khτ i
t 7−→ γ(t) + gφ τ + ∆φ τ 2

for some gφ ∈ K and ∆φ ∈ K × . For a ∈ A, let φa denote the image of a under φ. We will concern
ourselves primarily with rank 2 Drinfeld modules and unless otherwise noted, a Drinfeld module will
mean a rank 2 Drinfeld module.
To every A-algebra L over K̄, the Drinfeld module φ endows a new A-module structure (which, we
denote by φ(L)) through the A-action
∀f ∈ L, ∀a ∈ A, a ∗ f = φa (f ).

For every A-algebra homomorphism ρ : L −→ L, ∀a ∈ A and ∀f ∈ L, ρ(φ(f )) = φ(ρ(f )). Thus ρ, when
thought of as a map from φ(L) −→ φ(L), is an A-module homomorphism. For every direct product
L × L′ of A-algebras over K̄, we hence have the corresponding direct sum of A-modules
∼ φ(L) ⊕ φ(L′ ).
φ(L × L′ ) =

POLYNOMIAL FACTORIZATION AND EULER-POINCARE CHARACTERISTICS OF DRINFELD MODULES

5

Henceforth, we restrict our attention to Drinfeld modules φ : A −→ Fq (t) over Fq (t) (with γ : A → Fq (t)
being the inclusion (identity map), gφ ∈ A and ∆φ ∈ A× ) and their reductions.
For a proper ideal f ⊂ A, let Ff denote A/f. For a prime ideal p ⊂ A, if ∆φ is non zero modulo p,
then the reduction φ/p := φ ⊗ Fp of φ at p is defined through the ring homomorphism
φ/p : A −→ Fp hτ i

t 7−→ t + (gφ mod p)τ + (∆φ mod p)τ 2
and the image of a ∈ A under φ/p is denoted by (φ/p)a . Even if ∆φ is zero modulo p, one can still obtain
the reduction (φ/p) of φ at p through minimal models of φ (c.f. [Gek91]). We refrain from addressing
this case since our algorithms do not require it.
As before, the Drinfeld module φ/p endows a new A-module structure (denoted by (φ/p)(L)) to every A-algebra L over the algebraic closure of Fp through the A-action
∀f ∈ L, ∀a ∈ A, a ∗ f = (φ/p)a (f )

′

and for every direct product L × L of A-algebras over the algebraic closure of Fp ,
(φ/p)(L × L′ ) ∼
= (φ/p)(L) ⊕ (φ/p)(L′ ).

Further, for every A-algebra L over the algebraic closure of Fp , φ(L) ∼
= (φ/p)(L).

Define the annihilator Ann(L) of a finite A-module L to be the monic generator of the annihilator
ideal {a ∈ A|aL = 0} of L. Define the A-order Ord(α) of an element α in a finite A-module L to be
the monic generator of the annihilator ideal {a ∈ A|aα = 0} of α. For f ∈ A, denote by (f ) the ideal
generated by f and by deg(f ) the degree of f . For a non zero ideal f ⊂ A, let deg(f) denote the degree
of its monic generator. For f, g ∈ A, by gcd(f, g) we mean the monic generator of the ideal generated by
f and g.
Definition 2.1. Following [Gek91], the Euler-Poincare characteristic of a finite A-module L is defined
as the unique monic polynomial χ(L) ∈ A such that
(1) If L ∼
= A/p for a prime ideal p ⊆ A, then (χ(L)) = p,
(2) If 0 → L1 → L → L2 → 0 is exact, then χ(L) = χ(L1 )χ(L2 ).
The above definition is a minor departure from [Gek91], where χ(L) was defined as an ideal, not a monic
generator. For a non zero ideal f ⊂ A and a Drinfeld module φ, let χφ,f denote χ(φ(Ff )). By definition,
Ann(φ(Ff )) divides χφ,f.
2.1. Frobenius Distributions and the Structure of Rank 2 Drinfeld Modules. In this subsection,
we recount the characterization of the A-module structure of reductions of Drinfeld modules at primes
due to Gekeler. Unless stated otherwise, proofs of claims made here are in [Gek91]. For Drinfeld modules
φ, ψ with reduction at a prime p ⊂ A, a µ ∈ Fp hτ i such that
∀a ∈ A, µ(φ/p)a = (ψ/p)a µ

is called as a morphism from φ/p to ψ/p. Let EndFp (φ) denote the endomorphism ring of φ/p. The
Frobenius at p, τ deg(p) is in EndFp (φ) and there exists a polynomial
Pφ,p (X) = X 2 − aφ,p X + bφ,p ∈ A[X]

(called the characteristic polynomial of the Frobenius at p) such that Pφ,p (τ deg(p) ) = 0 in EndFp (φ). The
polynomial Pφ,p is called as the characteristic polynomial because it is the characteristic polynomial of

6

ANAND KUMAR NARAYANAN

τ deg(p) in the representations of EndFp (φ) on the ℓ-adic Tate modules for prime ideals ℓ ⊂ A.
Furthermore, a rank-2 Drinfeld module analogue of Hasse’s theorem for elliptic curves states that
(bφ,p ) = p , deg(aφ,p ) ≤ deg(p)/2.

To be precise, the coefficient bφ,p = ǫφ,p p where p is the monic generator of p and
ǫφ,p = 1/((−1)deg p NFp /Fq (∆φ )) ∈ F×
q

where NFp /Fq is the norm from Fp to Fq . As in the elliptic curve case, aφ,p is referred to as the Frobenius
trace; a consequence of the aforementioned connection to Tate modules. Since τ deg(p) acts as the identity
on φ(Fp ), Pφ,p (1) kills φ(Fp ) (that is, (φ/p)Pφ,p (1) is the zero element in EndFp (φ)). In fact,
(χφ,p ) = (Pφ,p (1)) ⇒ χφ,p = p − (aφ,p − 1)/ǫφ,p.

As a consequence of φ being of rank 2, φ(Fp ) is either a cyclic A-module or a direct sum of two cyclic
A-modules. That is, there exists monic polynomials mφ,p , nφ,p ∈ A (not necessarily relatively prime)
such that as A-modules
φ(Fp ) ∼
= A/(mφ,p ) ⊕ A/(mφ,p nφ,p ).
In particular,
χφ,p = p − (aφ,p − 1)/ǫφ,p = m2φ,p nφ,p , Ann(φ(Fp )) = lcm(mφ,p , mφ,p nφ,p ) = mφ,p nφ,p .

Further still, when q is odd, mφ,p and nφ,p are completely determined by Pφ,p and a precise characterization of mφ,p and nφ,p in terms of aφ,p and ǫφ,p is described by Cojocaru and Papikian [CP14, Cor3].
Seeing that the characteristic polynomial completely determines the A-module structure of a Drinfeld
module reduced at a prime p, the question as to which polynomials can arise as such characteristic polynomials is immediate and is addressed in [Dri77], [Gek91] and [Yu95]. Yu [Yu95] relates the number of
isomorphism classes of Drinfeld modules (φ/p) with a given characteristic polynomial X 2 − aX + ǫp to
class numbers of orders in imaginary quadratic extensions over K. This relation arises from a theory that
bears likeness to the complex multiplication theory of elliptic curves. Gekeler [Gek08] using the complex
multiplication theory proved a precise characterization of the number of isomorphism classes of Drinfeld
modules (φ/p) with a given characteristic polynomial X 2 − aX + ǫp. Gekeler’s characterization implies
a certain equidistribution of the probability of X 2 − aX + ǫp being Pφ,p for a randomly chosen φ and is
discussed in the subsequent subsection.
2.2. Frobenius Distributions of Rank 2 Drinfeld Modules. Let p ⊂ A be a prime of degree d and
let p be its monic generator. Analysis of our algorithms will involve counting Drinfeld modules (φ/p) with
characteristic polynomial Pφ,p (X) = X 2 − aX + ǫp for a given ǫ ∈ F×
q and a ∈ A of degree at most d/2.
Such precise counts were proven by Gekeler [Gek08] by building on the connection between isomorphism
classes of Drinfeld modules over Fp and class numbers of imaginary quadratic orders established by Yu
[Yu95]. We begin the section by stating the result of Gekeler in equation 2.1 and later prove lemmas that
will find use in the analysis of our algorithms.
We identify a Drinfeld module (φ/p) with the tuple (gφ mod p, ∆φ mod p). The number of Drinfeld
×
modules (φ/p) is |Fp ||F×
p | since we get to pick gφ mod p from Fp and ∆φ mod p from Fp . Two Drinfeld
×
modules (φ/p) and (ψ/p) are isomorphic over Fp if and only if there is a c ∈ Fp such that gψ = cq−1 gφ
2
mod p and ∆ψ = cq −1 ∆φ mod p.
As a consequence, the automorphism group AutFp (φ) depends on if gφ mod p = 0. If gφ mod p = 0 and

POLYNOMIAL FACTORIZATION AND EULER-POINCARE CHARACTERISTICS OF DRINFELD MODULES

7

∼ F×2 . Else, AutF (φ) ∼
if further Fp contains a quadratic extension (call Fq2 ) of Fq , then AutFp (φ) =
= F×
p
q .
q
×
∼
The former case AutFp (φ) = Fq2 corresponds to φ having complex multiplication by Fq2 [t] and is rare.
For ǫ ∈ F×
q and a ∈ A not necessarily monic and of degree at most deg(p)/2, denote by H(a, ǫ, p) a
set of representatives of isomorphism classes of Drinfeld modules (φ/p) with Pφ,p (X) = X 2 − aX + ǫp.
Define
X
q−1
h∗ (a, ǫ, p) :=
#AutFp (φ)
(φ/p)∈H(a,ǫ,p)

which might be thought of as a weighted count of the isomorphism classes of Drinfeld modules with
Pφ,p (X) = X 2 − aX + ǫp where the weight (q − 1)/AutFp (φ) is 1 except in rare cases. We next describe
the connection between class numbers of certain imaginary quadratic orders and h∗ (a, ǫ, p).
Fix an ǫ ∈ F×
q and an a ∈ A of degree at most deg(p)/2. Let C be the A-algebra generated by a
root of X 2 − aX + ǫp and let E be the quotient field of C. It turns out that E is an imaginary quadratic
extension of k.
Yu [Yu95] proved that two Drinfeld modules are isogenous if and only if they have the same characteristic polynomial and further established that the number of isomorphism classes of Drinfeld modules
with characteristic polynomial X 2 − aX + ǫp equals the Gauss class number of C. This connection is
analogous to a similar statement concerning elliptic curves due to Deuring [Deu41]. Further, the weighted
count h∗ (a, ǫ, p) equals a certain appropriately weighted Gauss class number of C which was explicitly
computed by Gekeler [Gek08] using an analytic class number formula. We next summarize this result of
Gekeler assuming for ease of exposition that Fq is of odd characteristic throughout this section.
Let B be the integral closure of A in E. Let D denote the discriminant a2 − 4ǫp and f the largest
monic square factor of D. Let D0 = D/f . Then C = A + f B.
Let ξ denote the Dirichlet character associated with E and for ℜ(s) > 1 define the L-function
Y
−1
L(s, χ) :=
.
1 − ξ(ℓ)|ℓ|−s
ℓ prime of k

The unique prime at infinity ∞ is ramified in E/k if deg(D0 ) is odd and is inert if deg(D0 ) is even. Let
η denote the ramification index of ∞ in E/k (that is, η = 2 if deg(D0 ) is odd and η = 1 otherwise). Let
g denote the genus of the algebraic curve associated with E. Then
h∗ (a, ǫ, p) = ηq g S(f )L(1, ξ)
where
S(f ) :=

X
f′ |f

|Ff′ |

Y
(1 − ξ(ℓ)|Fℓ |−1 ).
ℓ|f′

Here f ⊆ A is the ideal generated by f , the summation is over proper ideals f′ dividing f and the product
is over prime ideals ℓ dividing f′ . When f is not A, we have
The conductor cond(ξ) of ξ is

S(f ) ≥ |Ff |.
(
(D0 )
if deg(D0 ) is even
cond(ξ) =
(D0 ).∞ if deg(D0 ) is odd

8

ANAND KUMAR NARAYANAN

But for a couple of exceptional cases, the genus g is determined by cond(ξ) as
g = deg(cond(ξ))/2 − 1.
The inequality 2.1 we arrive at for h∗ (a, ǫ, p) will be accurate in those exceptional cases as well. Thus we
refrain from mentioning the exceptional cases referring instead the interested reader to [Gek08]. Thus
(
q deg(D0 )/2−1
if deg(D0 ) is even
qg =
q deg(D0 )/2−1/2 if deg(D0 ) is odd
and

(

|Ff |q g =

q deg(D)/2−1
q deg(D)/2−1/2

if deg(D) is even
if deg(D) is odd.

In summary,
(2.1)

∗

h (a, ǫ, p) ≥

(

1 deg(D)/2
L(1, ξ)
qq
√2 q deg(D)/2 L(1, ξ)
q

if deg(D) is even
if deg(D) is odd

Lemma 2.2. Let p ⊂ A be a prime ideal and p its monic generator. For every S ⊆ {(a, ǫ) ∈ A ×
2
F×
q | deg(a − 4ǫp) = deg(p)},
( p
X
√
if deg(p) is even
|S| |Fp |(1 − deg(p)
q )/q
∗
p
h (a, ǫ, p) ≥
deg(p) √
2|S| |Fp |(1 − √q )/ q if deg(p) is odd.
(a,ǫ)∈S

Proof. We first lower bound L(1, ξ) for a ξ corresponding to an arbitrary (a, ǫ).
Y
−1
1
L(1, ξ) =
1 − ξ(ℓ)|ℓ|−1
−
(1 − ξ(∞)|∞| 1)
ℓ prime of A

≥

Y

ℓ prime of A

1 − ξ(ℓ)|ℓ|−1

−1

since ξ(∞) ∈ {0, 1} and |∞| = q. From Weil’s proof of the Riemann hypothesis for curves over finite
√
fields, there exists wi ∈ C with |wi | = q such that
Y

ℓ prime of A

1 − ξ(ℓ)|ℓ|

Since deg(cond(ξ)) − 1 ≤ deg(p),

deg(cond(ξ))−1 

Y

i=1

1−

wi
q


−1 −1



≥

=

deg(cond(ξ))−1 

Y

i=1

wi
1−
q



.


deg(p)
1
deg p
1− √
≥1− √ .
q
q

For all (a, ǫ) ∈ S, since deg(a2 − 4ǫp) = deg(p), inequality 2.1 implies
( p
X
√
|S| |Fp |(1 − deg(p)
if deg(p) is even
q )/q
∗
p
h (a, ǫ, p) ≥
deg(p) √
√
2|S| |Fp |(1 −
q )/ q if deg(p) is odd.
(a,ǫ)∈S



POLYNOMIAL FACTORIZATION AND EULER-POINCARE CHARACTERISTICS OF DRINFELD MODULES

9

Lemma 2.3. Let p ⊂ A be a prime ideal and p its monic generator. For every S ⊆ {(a, ǫ) ∈ A ×
2
F×
q | deg(a − 4ǫp) = deg(p)}, the number of Drinfeld modules (φ/p) over Fp with (aφ,p , ǫφ,p ) ∈ S is lower
bounded by
( ×
p
√
if deg(p) is even
|Fp ||S| |Fp |(1 − deg(p)
q )/(q(q − 1))
p
|{(φ/p)|(aφ,p , ǫφ,p ) ∈ S}| ≥
√
deg(p)
×
√
2|Fp ||S| |Fp |(1 −
q )/( q(q − 1)) if deg(p) is odd.

2
Proof. Fix an S ⊆ {(a, ǫ) ∈ A × F×
q | deg(a − 4ǫp) = deg(p)}.

|{(φ/p)|(aφ,p , ǫφ,p ) ∈ S}| =
=

X

X

(a,ǫ)∈S (φ/p)∈H(a,ǫ,p)

|F×
p|
AutFp (φ)

X
|F×
p|
h∗ (a, ǫ, p).
q−1
(a,ǫ)∈S

Applying Lemma 2.2, we get
|{(φ/p)|(aφ,p , ǫφ,p ) ∈ S}| ≥

(

p
deg(p)
|F×
if deg(p) is even
p ||S| |Fp |(1 − √q )/(q(q − 1))
p
√
deg(p)
×
2|Fp ||S| |Fp |(1 − √q )/( q(q − 1)) if deg(p) is odd.



3. Degree Estimation and Euler-Poincare Characteristic of Drinfeld Modules
Q
Henceforth, let h ∈ A denote the monic square free reducible polynomial whose factorization h =Q i pi
into monic irreducible polynomials pi ∈ A we seek. By the chinese reminder theorem, Fh = i Fpi
where h and pi s are the principal ideals generated by h and the pi s respectively. We next present a novel
algorithm to compute the degree (call sh ) of the smallest degree factor of h using Drinfeld modules.
For a Drinfeld module φ that has reduction at each prime dividing h,
Y
Y
M
M
(pi − (aφ,pi − 1)/ǫφ,pi ) .
χφ,pi =
(φ/pi )(Fpi ) ⇒ χφ,h =
φ(Fpi ) ∼
φ(Fh ) ∼
=
=
i

i

i

i

Since ∀i, deg((aφ,pi − 1)/ǫφ,pi ) ≤ deg(pi )/2,

χφ,h = h + terms of smaller degree.
In fact,
h − χφ,h =

X

i:deg(pi )=sh




Y
−
1
a
 φ,pi
pj  + (terms of degree < (deg(h) − ⌈sh /2⌉))
ǫφ,pi
j6=i

⇒ deg(h − χφ,h ) ≤ deg(h) − ⌈sh /2⌉.
When φ is chosen at random, the equidistribution theorem of Gekeler suggests, with high probability,



Y
X
−
1
a
φ,p
i

pj  = deg(h) − ⌈sh /2⌉ ⇒ deg(h − χφ,h ) = deg(h) − ⌈sh /2⌉
deg 
ǫφ,pi
i:deg(pi )=sh

j6=i

leading to the following algorithm to compute sh .

Algorithm 3.1.
Input : Monic square free reducible polynomial h ∈ A of degree n.

10

ANAND KUMAR NARAYANAN

(1) Choose a Drinfeld module φ by picking gφ ∈ A and ∆φ ∈ A× each of degree less than deg(h)
independently and uniformly at random.
(2) If gcd(∆φ , h) 6= 1, output it as a factor. Else φ has reduction at primes dividing h and we proceed.
(3) Compute χφ,h .
(4) Output: n − deg(h − χφ,h ).
The running time of the algorithm is dominated by step (3). One way to compute χφ,h is as the characteristic polynomial of φt viewed as a linear transformation on Fh . Computing characteristic polynomials
of linear transformations over finite fields can be performed in polynomial time [Sto01].
The output is at least ⌈sh /2⌉. We prove in the ensuing lemma that when q is large enough compared
to n, the output is ⌈sh /2⌉ with probability at least 1/4. We are thus ensured of finding ⌈sh /2⌉ with
probability 1 − δ with only O(log(1/δ)) repetitions of the algorithm. From ⌈sh /2⌉, we infer that sh is
s
either 2⌈sh /2⌉ − 1 or 2⌈sh /2⌉. We can test which one is correct by checking if gcd(tq h − t, h) is non
trivial and further extract the product of factors of degree sh .
Remark 3.2. In the analysis of our algorithms, we may assume without loss of generality that q ≥ c1 nc2
for some absolute positive constants c1 and c2 . If q were smaller, we could choose the smallest prime c
that satisfies q c ≥ c1 nc2 and obtain the factorization in Fqc [t] with the running time unchanged up to
polylogarithmic factors in n. Factors of h irreducible over Fq and of degree prime to c remain irreducible
over Fqc . Factors of h that are irreducible over Fq of degree (say d) divisible by c will split into c
c
c
distinct
Q irreducible factors over Fq . From the factorization over Fq thus obtained, express h as h =
Q
h
where
h
∈
F
[t]
are
irreducible
factors
that
remained
irreducible
over Fqc and hd ∈ Fqc [t]
h
d
i
q
i
d
i
is the product of all irreducible factors of h in Fqc [t] (but not in Fq [t]) of degree d/c. In fact, hd is the
product of all Fq [t] irreducible factors of h of degree d and hence hd ∈ Fq [t]. We may perform equal
degree factorization on hd to obtain all Fq [t] irreducible degree d factors of h. Since c is bounded by
an absolute constant, the post processing steps after obtaining the factorization over Fqc take at most
O(n1+o(1) (log q)1+o(1) + n(log q)2+o(1) ) expected time.
√
Lemma 3.3. If q is odd and q ≥ 2n, algorithm 3.1 outputs ⌈sh /2⌉ with probability at least 1/4.
Proof. For the output deg(h) − deg(h − χφ,h ) of algorithm 3.1 to be ⌈sh /2⌉, it suffices for



Y
X
−
1
a
 φ,pi
pj  = deg(h) − ⌈sh /2⌉
deg 
ǫφ,pi
i:deg(pi )=sh

j6=i

to hold. Since pi are all monic, this is equivalent to
X
aφ,pi ,⌊sh /2⌋
(3.1)
6= 0
ǫφ,pi
i:deg(pi )=sh

where aφ,pi ,⌊sh /2⌋ ∈ Fq denotes the coefficient of the t⌊sh /2⌋ term in aφ,pi .
Fix a factor pj of h of degree sh .
Since gφ ∈ A and ∆φ ∈ A× are each chosen of degree less than deg(h) independently and uniformly at
random (with gcd(∆φ , h) =Q
1), by the chinese remainder theorem, the tuple {(gφ mod pi , ∆φ mod pi )}i
is distributed uniformly in i (Fpi × F×
pi ).

POLYNOMIAL FACTORIZATION AND EULER-POINCARE CHARACTERISTICS OF DRINFELD MODULES

11

In particular, ∀i 6= j, (aφ,pi , ǫφ,pi ) and (aφ,pj , ǫφ,pj ) are independent and



 



X
X
X
aφ,pj ,⌊sh /2⌋
aφ,pi ,⌊sh /2⌋
aφ,pi ,⌊sh /2⌋
P r 
6= 0 =
= −θ P r
6= θ 
Pr 
ǫφ,pi
ǫφ,pi
ǫφ,pj
θ∈Fq

i:deg(pi )=sh



⇒ Pr 

(3.2)

Fix a θ ∈ Fq and let

X

i:deg(pi )=sh

i:deg(pi )=sh ,i6=j



aφ,pi ,⌊sh /2⌋
6= 0 ≥ min P r
θ∈Fq
ǫφ,pi




aφ,pj ,⌊sh /2⌋
6= θ .
ǫφ,pj

2
Sθ := {(a, ǫ) ∈ A × F×
q | deg(a − 4ǫpj ) = deg(pj ), a⌊sh /2⌋ /ǫ 6= θ}

where a⌊sh /2⌋ ∈ Fq denotes the coefficient of the t⌊sh /2⌋ term in a.
We next count elements in Sθ to lower bound its size. The condition deg(a2 −4ǫpj ) = deg(pj ) implies that
we are only allowed to pick a ∈ A of degree at most deg(pj )/2. If deg(pj ) is odd, deg(a2 − 4ǫpj ) = deg(pj )
is always satisfied for every a ∈ A of degree at most deg(pj )/2. To pick an element in Sθ , but for the
coefficient a⌊sh /2⌋ , we may choose the coefficients of a ∈ A arbitrarily of degree at most deg(pj )/2 and
2
arbitrarily choose ǫ ∈ F×
q . For each such choice, to satisfy deg(a − 4ǫpj ) = deg(pj ) and a⌊sh /2⌋ /ǫ 6= θ,
we need to exclude at most two choices for a⌊sh /2⌋ if deg(pj ) is even and at most one choice if deg(pj ) is
odd. Thus
(
p
(q − 2) |Fpj |q
if deg(pj ) is even
p
|Sθ | ≥
√
(q − 1) |Fpj | q if deg(pj ) is odd.
Applying Lemma 2.3 for Sθ , we get

Thus, for

√




1
deg(pj )
1−
|Fpj ||F×
{(φ/pj )|(aφ,pj , ǫφ,pj ) ∈ Sθ } ≥ 1 − √
pj |.
q
q−1

q ≥ 2 deg(h) ≥ 2 deg(pj ),


 

aφ,pj ,⌊sh /2⌋
1
1
deg(pj )
1−
≥
6= θ ≥ 1 − √
Pr
ǫφ,pj
q
q−1
4

and by equation 3.2 the lemma follows.



Proof of Theorem 1.1 and Corollary 1.2: Theorem 1.1 follows from the proof of correctness (Lemma
3.3) of Algorithm 3.1. Corollary 1.2 follows by considering lines one and three in algorithm 3.1 to be
performed by the black box B in Corollary 1.2. The case gcd(∆φ , h) 6= 1 for a random φ is unlikely to
happen and hence step 2 of algorithm 3.1 may be ignored in the reduction.
When q is large enough (say q ≥ 2 deg(h)4 ), it is likely for a randomly chosen φ that φ(Fh ) is a cyclic
A-module. Further, for a random α ∈ φ(Fh ), it is likely that Ord(α) = Ann(φ(Fh )). Since φ(Fh ) being
cyclic implies χφ,h = Ann(φ(Fh )), it is likely that Ord(α) = χφ,h . Thus, instead of computing χφ,h
in Algorithm 3.1, we could compute Ord(α) for a random α ∈ φ(Fh ) and be assured that the output
deg(h) − deg(h − Ord(α)) likely is ⌈sh /2⌉.
Algorithm 3.4.
Input : Monic square free reducible polynomial h ∈ A of degree n.
(1) Choose a Drinfeld module φ by picking gφ ∈ A and ∆φ ∈ A× each of degree less than deg(h)
independently and uniformly at random.

12

ANAND KUMAR NARAYANAN

(2) If gcd(∆φ , h) 6= 1, output it as a factor. Else φ has reduction at primes dividing h and we proceed.
(3) Choose α ∈ φ(Fh ) at random and compute Ord(α) with constant probability.
(4) If deg(Ord(α)) = deg(h), Output: n − deg(h − Ord(α)).
Every step except for (3) can be performed in O(n log q) time. In § 3.1, we show that the order of
an element in φ(Fh ) (and hence step (3)) can be computed with probability arbitrarily close to 1 in
O(n(1+ω)/2 + o(1)(log q)1+o(1) + n1+o(1) (log q)2+o(1) ) expected time. In the subsequent lemma, we prove a
lower bound on the probability that reductions of Drinfeld modules are cyclic and use it in Theorem 3.6
to prove that Algorithm 3.4 outputs sh with constant probability. Consequently, we have an O(n(1+ω)/2 +
o(1)(log q)1+o(1) + n1+o(1) (log q)2+o(1) ) expected time algorithm to extract a non trivial factor.
Lemma 3.5. For odd q, for everyprime ideal p ⊂ A, the probability that φ(Fp ) is a cyclic A-module for
a randomly chosen φ/p is at least 1 − deg(p)+1/2
.
2(q−1)

Proof. Let p ⊂ A be a prime ideal and p its monic generator. Cojocaru and Papikian [CP14, Cor 3]
determined the following precise characterization of the A-module structure of finite Drinfeld modules
when Fq is of odd characteristic. For a Drinfeld module φ with reduction at p, let fφ,p ∈ A denote the
largest monic square factor of the discriminant a2φ,p − 4ǫφ,p p of Pφ,p . As A-modules
φ(Fp ) ∼
= A/(mφ,p ) ⊕ A/(mφ,p nφ,p )
where

mφ,p = gcd(fφ,p , aφ,p − 2).
In particular, φ(Fp ) is A-cyclic if and only if gcd(fφ,p , aφ,p − 2) = 1. Let

2
2
Sp := {(a, ǫ) ∈ A × F×
q | deg(a − 4ǫp) = deg(p), gcd(a − 4ǫp, a − 2) = 1}.

We next estimate the size of Sp . An element in Sp can be chosen as follows. Pick a ∈ A arbitrarily of
degree at most deg(p)/2. For such a chosen a, to satisfy gcd(a2 − 4ǫp, a − 2) = 1, pick ǫ such that for
all monic irreducible polynomials ℓ dividing a − 2, a2 − 4ǫp 6= 0 mod ℓ. For a fixed monic irreducible
2
ℓ dividing a − 2, there is at most one ǫ ∈ F×
q such that a − 4ǫp = 0 mod ℓ for if there were two, then
that would imply ℓ divides p which contradicts the fact that p is irreducible and of degree higher than
ℓ. Thus, for a chosen a, to ensure a2 − 4ǫp and a − 2 are relatively prime, we need to exclude at most
deg(p)/2 values for ǫ. When deg(p) is even, for a chosen a, to ensure deg(a2 − 4ǫp) = deg(p), we need to
exclude at most one choice for ǫ.
(
p
if deg(p) is even
(q − 2 − deg(p)/2) |Fpj |q
p
⇒ |Sp | ≥
√
(q − 1 − deg(p)/2) |Fpj | q if deg(p) is odd.

Applying Lemma 2.3 for Sp , we get



deg(p) + 1/2
|Fp ||F×
1−
p |.
2(q − 1)


Thus φ(Fp ) is A-cyclic with probability at least 1 − deg(p)+1/2
.
2(q−1)
|{(φ/p)|(aφ,p , ǫφ,p ) ∈ Sp }| ≥



Theorem 3.6. There exists a positive constant c such that for q odd and at least 2n4 , algorithm 3.4
outputs ⌈sh /2⌉ with probability at least c.

Proof. Assume q is odd and q ≥ 2n4 . For a choice of α and φ made in algorithm 3.4, if the following
three conditions hold, then clearly the output is ⌈sh /2⌉.
• Ord(α) = Ann(φ(Fh )),
• Ann(φ(Fh )) = χφ,h ,

POLYNOMIAL FACTORIZATION AND EULER-POINCARE CHARACTERISTICS OF DRINFELD MODULES

13

• deg(h) − deg(h − χφ,h ) = ⌈sh /2⌉.
For a fixed φ and a random α ∈ φ(Fh ), from the A-module decomposition of φ(Fh ) into invariant factors,
we infer that Ord(α) = Ann(φ(Fh )) with probability at least
1
|{a ∈ A| deg(a) < deg(Ann(φ(Fh ))), gcd(a, Ann(φ(Fh ))) = 1}|
≥ (1 − 1/q)deg(h) ≥ 1 − deg(h)/q ≥ .
2
q deg(Ann(φ(Fh )))
The last inequality is a consequence of q ≥ 2 deg(h)4 . If φ(Fh ) is a cyclic A-module, then by definition
χφ,h = Ann(φ(Fh )). Hence, to claim the theorem, it suffices to prove that for a Drinfeld module φ chosen
at random as in algorithm 3.4, the following two conditions hold with constant probability
• φ(Fh ) is a cyclic A-module,
• deg(h) − deg(h − χφ,h ) = ⌈sh /2⌉.
The proof proceeds by induction on the factors of h. Let m denote the number of irreducible
facQ
tors of h. Without loss of generality relabel the irreducible factors of h such that h = m
p
where
i
i=1
Qi
deg(p1 ) ≥ deg(p2 ) ≥ . . . ≥ deg(pm ). In particular, deg(pm ) = sh . Let hi := j=1 pj and hi := (hi ).

Induction Hypothesis: For i < m, assume φ(Fhi ) is a cyclic A-module with probability at least 1 −
The initial case i = 1 of the induction hypothesis (that is, h1 is prime), follows from Lemma 3.5.

deg(hi )
√
q

i−1

We next lower bound the probability that φ(Fh ) (= φ(Fhm )) is A-cyclic and deg(h) − deg(h − χφ,h )) =
⌈sh /2⌉ conditioned on φ(Fhm−1 ) being A-cyclic. Since gφ ∈ A and ∆φ ∈ A× are each chosen of degree less
than deg(h) independently and uniformly at random (with gcd(∆φ , h) = 1),Qby the chinese remainder
theorem, the tuple {(gφ mod pi , ∆φ mod pi )}i is distributed uniformly in i (Fpi × F×
pi ). In particular, (aφ,pm , ǫφ,pm ) is independent of the structure of φ(Fhm−1 ). Consequently, instead of conditioning on
φ(Fhm−1 ) being A-cyclic, we fix a tuple
Y
(gφ mod pi , ∆φ mod pi )
i<m

such that φ(Fhm−1 ) is A-cyclic. In particular, χφ,hm−1 is fixed. In the remainder of the proof, the only
randomness in φ comes from choosing (gφ mod pm , ∆φ mod pm ) uniformly at random from Fpm × F×
pm .
As reasoned in the proof of Lemma 3.3, for deg(h) − deg(h − χφ,h ) to be ⌈sh /2⌉, it suffices for
X
(3.3)
(aφ,pi ,⌊sh /2⌋ /ǫφ,pi ) 6= 0
i:deg(pi )=sh

to hold where aφ,pi ,⌊sh /2⌋ ∈ Fq denotes the coefficient of the t⌊sh /2⌋ term in aφ,pi .
Since ∀i 6= j, (gφ mod pi , ∆φ mod pi ) is fixed,
X
θ :=

(aφ,pi ,⌊sh /2⌋ /ǫφ,pi )

i:deg(pi )=sh ,i6=m

is fixed. Clearly equation 3.3 holds if and only if (aφ,pm ,⌊sh /2⌋ /ǫφ,pm ) 6= θ.
Since φ(Fhm−1 ) is A-cyclic, if φ(Fpm ) is A-cyclic and χφ,pm is relative prime to χφ,hm−1 , then φ(Fh )
is A-cyclic. Thus, to ensure φ(Fh ) is A-cyclic, it suffices if gcd(pm − (aφ,pm − 1)ǫφ,pm , χφ,hm−1 ) = 1 and

.

14

ANAND KUMAR NARAYANAN

gcd(a2φ,pm − 4ǫφ,pm pm , aφ,pm − 2) = 1. The argument as to why is identical to the discussion in the proof
of Lemma 3.5.
For a ∈ A, denote by a⌊sh /2⌋ ∈ Fq the coefficient of t⌊sh /2⌋ in a. To summarize, the set Spm of tuples (a, ǫ) ∈ A × F×
q that satisfy the four conditions
(i)
(ii)
(iii)
(iv)

deg(a2 − 4ǫpm ) = deg(pm ),
a⌊sh /2⌋ 6= θǫ,
gcd(ǫpm − (a − 1), χφ,bh ) = 1,
gcd(a2 − 4ǫpm , a − 2) = 1,

has the property that if (aφ,pm , ǫφ,pm ) ∈ Spm then φ(Fh ) is A-cyclic and deg(h) − deg(h − χφ,h ) = ⌈sh /2⌉.
We estimate a lower bound on the size of Spm by choosing a ∈ A arbitrarily of degree at most deg(pm )/2
and for each choice of a, picking only those ǫ such that the four conditions are satisfied. To ensure the
first condition, we need to exclude at most one choice each for ǫ. To satisfy the fourth condition, for a
fixed choice of a, we need to exclude at most deg(a − 2) ≤ deg(pm )/2 choices for ǫ. This is because for
2
each monic irreducible polynomial ℓ dividing a − 2, there is at most one ǫ ∈ F×
q such that a − 4ǫpm = 0
mod ℓ. For if there were two, then ℓ would divide pm , which is an irreducible polynomial of degree higher
than deg(ℓ). To satisfy the third condition, for a fixed choice of a 6= 1, we need to exclude at most
deg(hm−1 ) choices for ǫ. This is because for each monic irreducible polynomial ℓ dividing χφ,hm−1 , there
is at most one ǫ ∈ F×
q such that ǫpm − (a − 1) = 0 mod ℓ. For if there were two, then ℓ would divide pm
in which case restricting to a 6= 1 assures that ǫpm − (a − 1) 6= 0 mod ℓ. If θ 6= 0, to satisfy the second
condition we need to exclude at most one choice for ǫ which implies
(p
if deg(pm ) is even
|Fp | − 1(q − deg(hm−1 ) − deg(pm )/2 − 3)q
θ 6= 0 ⇒ |Spm | ≥ p m
√
|Fpm | − 1(q − deg(hm−1 ) − deg(pm )/2 − 3) q if deg(pm ) is odd.
For θ = 0, the second condition can be satisfied by restricting the count to non zero a⌊sh /2⌋ and we get
(p
if deg(pm ) is even
|Fp | − 1(q − deg(hm−1 ) − deg(pm )/2 − 2)(q − 1)/q
θ = 0 ⇒ |Spm | ≥ p m
√
|Fpm | − 1(q − deg(hm−1 ) − deg(pm )/2 − 2)(q − 1)/ q if deg(pm ) is odd.
Applying Lemma 2.3 for Spm and assuming q ≥ 2 deg(h)4 , we get


deg(h)
|{(φ/pm )|(aφ,pm , ǫφ,pm ) ∈ Spm }| ≥ 1 − √
|Fpm ||F×
pm |.
q

The probability that φ(Fh ) is A-cyclic and deg(h) − deg(h − Ann(φ(Fh ))) = ⌈sh /2⌉ conditioned on
φ(Fhm−1 ) being A-cyclic is hence at least
1−

deg(h)
√ .
q

By induction φ(Fh ) is A-cyclic and deg(h) − deg(h(t) − Ann(φ(Fh ))) = ⌈sh /2⌉ with probability at least

m
deg(h)
m deg(h)
deg(h)2
1− √
≥1−
≥1− √
√
q
q
q
which is lower bounded by a constant since q ≥ 2 deg(h)4 and the theorem follows.



POLYNOMIAL FACTORIZATION AND EULER-POINCARE CHARACTERISTICS OF DRINFELD MODULES

15

3.1. Order Finding in Finite Drinfeld Modules. We sketch a Montecarlo randomized algorithm to
compute Ord(α) with probability arbitrarily close to 1 in O(n(1+ω)/2+o(1) (log q)1+o(1) + n1+o(1) (log q)2 )
time2. The algorithm works for every φ with reduction at h and every α ∈ φ(Fh ). Fix a φ with reduction
at h and an α ∈ φ(Fh ). Compute the minimal polynomial of the linear sequence {U(φjt (α)), j ∈ Z≥0 }
where U : Fh −→ Fq is a random Fq linear map. The minimal polynomial of the linear sequence divides
Ord(α) and with probability at least half equals Ord(α). Hence the least common multiple of the minimal
polynomials of the resulting linear sequences of O(log(δ)) independent trials is Ord(α) with probability
at least 1 − δ. For a trial, the minimal polynomial of a sequence can be computed in O(n1+o(1) log q) time
using the fast Berlekamp Massey algorithm given the first 2 deg(h) − 1 elements in the sequence. Hence
the critical step is the computation of
2 deg(h)−2

{U(α), U(φt (α)), U(φ2t (α)), . . . , U(φt

(3.4)

(α))}

for a randomly chosen U. This is virtually identical to the automorphism projection problem of KaltofenShoup. The difference being that the Frobenius endomorphism modulo h is replaced by the Drinfeld
endomophism φt modulo h. In Kaltofen-Shoup apart from being an Fq linear endomorphism of Fh , the
e 1+o(1) (log q)2 ) time
only property of the Frobenius exploited is that τ (t mod h) can be computed in O(n
using the vonzur Gathen-Shoup algorithm. To adapt the automorphism projection algorithm of Kaltofen
and Shoup [KS98][§ 3.2] to apply in our setting, we merely have to demonstrate how to efficiently compute
φt (t mod h) given h, gφ mod h and ∆φ mod h. Since
φt (t

mod h) = t2

mod h + τ (t

mod h) + τ 2 (t

mod h),

we can compute φt (t mod h) in O(n1+o(1) (log q)2 ) time with three Frobenius powers and two additions
modulo h thereby making the Katofen-Shoup algorithm applicable to our setting.
3.2. Obtaining the Complete Factorization from a Factor Finding Procedure. In this subsection, we prove that given access to a blackbox D that takes as input a square free f ∈ A and outputs an
irreducible factor, there is an O(n4/3+o(1) (log q)1+o(1) ) expected time algorithm F to factor a polynomial
of degree n over Fq into its irreducible factors. Further, this algorithm makes at most n1/3 calls to D.
Thereby, Corollary 1.3 would follow from Theorem 1.1.
Without loss of generality, assume that the input h ∈ A to F is square free and of degree n. Obtaining the factorization
of h by extracting one irreducible factor at a time using D could in the worst
√
case take Θ( n) calls to D. A faster alternative is to use the Kaltofen-Shoup algorithm with fast modular
composition to extract small degree factors of h and then invoke D to extract the large degree factors
one at a time. In particular, using [KU08, Lem 8.4, Thm 8.5], extract all the irreducible factors of h of
degree at most n2/3 in O(n4/3+o(1) (log q)1+o(1) ) expected time. The remaining irreducible factors of h
each have degree at least ⌈n2/3 ⌉. Hence there are at most n1/3 irreducible factors of h remaining and the
complete factorization of h can be obtained by extracting a factor at a time with at most n1/3 calls to D.
Remark 3.7. Kaltofen and Shoup [KS98, § 3.1] through the blackbox Berlekamp algorithm [KL94] reduced
polynomial factorization in time nearly linear in degree to two problems that are transposes of each
other, namely automorphism projection and automorphism evaluation. Being transposes, a straight
line program that computes Fq linear forms in the input for one would in linear time yield a straight
line program for the other of the same complexity. In particular, there is nearly linear polynomial
factorization algorithm if there is a nearly linear time Fq linear solution to the automorphism projection
problem. Our order finding problem is no harder than automorphism projection. We hence arrive at the
stronger assertion that polynomial factorization is reducible to automorphism projection. In particular,
2We may replace (1 + ω)/2 with ω /2, where ω is the exponent of n × n by n × n2 matrix multiplication (see [KU08]).
2
2

16

ANAND KUMAR NARAYANAN

no assumptions on the Fq linearity of automorphism projection algorithm is made. We must however
remark that the automorphism projection we consider (see equation 3.4) is broader than that stated in
[KS98, § 3.2] where only the Frobenius automorphism is considered.
3.3. Degree Estimation Using Carlitz Modules. The degree estimation algorithm framework also
gives rise to variants where there is no randomization with respect to the choice of Drinfeld modules. In
fact, the following deterministic example from the author’s Ph.D thesis [Nar14] using Carlitz modules
(rank 1 Drinfeld modules) partly motivated the randomized version. The Carlitz module based algorithm
is suited to the case when the characteristic of Fq does not divide the number of factors of the smallest
degree.
Example 3.8. Factor Degree Estimation using Carlitz Modules.
Input : Monic square free reducible polynomial h ∈ A.
(1) Choose the Carlitz module φ (the rank 1 Drinfeld module φ with gφ = 1 and ∆φ = 0).
(2) Compute χφ,h .
(3) Output: deg(h) − deg(h − χφ,h ).
In [Nar14] it is shown that the output is exactly sh provided the number of factors of degree sh is not
divisible by the characteristic of Fq . This is true since for the Carlitz module φ, for all prime ideals p ⊂ A,
χφ,p = p − 1 where p is the monic generator of p.
Curiously for the Carlitz module φ, finding χφ,h is easily seen to be no harder than factoring h. Computing χφ,h is linear time reducible to factoring h since given the factorization of h, it is trivial to write
down χφ,h in O(deg(h) log q) time.
4. Factorization Patterns of Polynomials in Small Intervals
Our analysis of the Drinfeld module analogue of the black-box Berlekamp algorithm relies on the degree
distribution in factorization patterns of polynomials in short intervals which we study in this section.
For a partition λ of a positive integer e, let Cλ := {σ ∈ Se |λσ = λ} denote its conjugacy class where Se
is the symmetric group on e elements and λσ is the partition of e induced by the factorization of σ into
disjoint cycles. Let P (λ) := |Cλ |/|Se |. For a polynomial f ∈ A, let λ(f ) denote the partition of deg(f )
induced by the degrees of the irreducible factors in the factorization of f in A.
For f ∈ A and a positive integer m < deg(f ), define the interval around f corresponding to the degree bound m as
Im (f ) := {f + a|a ∈ A, deg(a) ≤ m}.
For I ⊂ A where each polynomial in I is of degree exactly d > 1 and a partition λ of d, define
Bq (I, λ) := {a ∈ I|λ(a) = λ}

and πq (I, λ) := |Bq (I, λ)|.

Bank, Bary-Soroker and Rosenzweig [BBR14] recently proved the following theorem when the field size
q tends to infinity while d is fixed.
Theorem 4.1. ([BBR14, Thm 1]) For all monic f ∈ A of fixed degree d, for all positive integers
2 < m < d and for all partitions λ of d,
πq (Im (f ), λ) ∼ P (λ)|Im (f )|
It is widely conjectured (see [BBR14]) that

as

q → ∞.

POLYNOMIAL FACTORIZATION AND EULER-POINCARE CHARACTERISTICS OF DRINFELD MODULES

Conjecture 4.2. For all monic f ∈ A of degree d such that 3 < d <
πq (Im (f ), λ) ∼ P (λ)|Im (f )|

as

17

√
q/2 and for all partitions λ of d,

q d → ∞.

In the next subsection § 4.1, by applying an effective Lang-Weil bound to the argument in [BBR14], we
prove an effective version of Theorem 4.1 that holds for log q > 5d log(d).
4.1. A High Dimensional Variant of the Function Field Chebotarev Density Theorem. Let E
denote the rational function field Fq (t1 , . . . , tm ) in the m indeterminates t1 , . . . , tm . Let F/E be a finite
Galois extension of E. Fix an algebraic closure Fq of Fq and let
α : Gal(F/E) −→ Gal((Fq ∩ F )/Fq )

denote the restriction map. Let V = Spec(Fq [t1 , . . . , tm ]) and let Vur (Fq ) ⊂ V (Fq ) denote the subset
of Fq rational places in V that are etale in the extension F/E. Let OF denote the integral closure of
Fq [t1 , . . . , tm ] in F and let W = Spec(OF ). For a place B ∈ W lying above a place p ∈ V that is etale in
F/E, let σB ∈ Gal(F/E) denote its Artin symbol. For a place p ∈ V that is etale in F/E, let
Θp := {σB |B ∈ W, B|p} ⊆ ker(α)

denote the conjugacy class of Artin symbols above p.

Lemma 4.3. If q ≥ 2(m + 1)[F : E]2 , for every conjugacy class Θ ⊆ ker(α),


|Θ|
|Θ|
qm
m
13/3 m−1
|{p ∈ Pur (Fq )|Θp = Θ}| −
q ≤
q
([F : E] − 1)([F : E] − 2) √ + 5[F : E]
.
|ker(α)|
|ker(α)|
q
Proof. Fix a conjugacy class Θ ⊆ ker(α) and let U := {p ∈ Pur (Fq )|Θp = Θ}.
Let ρ : W −→ V denote the norm map from W down to V . Applying [Bar12][Prop. 2.2] to (V,W,ρ, Θ)
c and a finite separable morphism
implies the existence of a smooth irreducible affine Fq -variety W
c
π : W −→ V such that
c) = U ,
(i) π(W
(ii) deg(π) = |ker(α)|,
c (Fq )| = |ker(α)|/|Θ|.
(iii) ∀p ∈ U, |π −1 (p) ∩ W
c −→ V is finite, W
c and V have the same dimension, namely m. Further, W and W
c are twists
Since π : W
c
of each other [Bar12]. As a consequence, W and W have the same degree, namely [F : E].
c (Fq ) using an effective Lang-Weil bound [CM06],
Bounding the size of W
qm
c (Fq )| − q m ≤ ([F : E] − 1)([F : E] − 2) √
+ 5[F : E]13/3 q m−1 .
|W
q

c ) = U and ∀p ∈ U, |π −1 (p) ∩ W
c (Fq )| = |ker(α)|/|Θ|, |W
c (Fq )| = |ker(α)||U|
Since π(W
|Θ|


m
|Θ|
q
|Θ|
⇒ |U | −
([F : E] − 1)([F : E] − 2) √ + 5[F : E]13/3 q m−1 .
qm ≤
|ker(α)|
|ker(α)|
q



Theorem 4.4. For every positive integer m ≥ 2, for every monic f ∈ A of degree greater than m and
for every partition λ of deg(f ), if log q ≥ 5 deg(f ) log(deg(f )) then
1
|πq (Im (f ), λ) − P (λ)|Im (f )|| ≤ P (λ)|Im (f )|.
2

18

ANAND KUMAR NARAYANAN

Proof. Fix a monic non constant polynomial f ∈ A of degree at least m and let
m
X
xi ti−1 .
Ff := f (t) +
i=1

Since the indeterminate x1 only appears in Ff as the linear term x1 , Ff is absolutely irreducible and
separable in t. Thus the splitting field Ff of Ff over E = Fq (x1 , . . . , xm ) is Galois. We will shortly apply
Lemma 4.3 to the extension Ff /E. Before doing so, we argue that Ff /E is a geometric extension.
The splitting field of Ff over Fq (x1 , . . . , xm ) is the composite Ff .Fq and we have

Gal(Ff .Fq /Fq (x1 , . . . , xm )) = Gal(Ff .Fq /Fq (x1 , . . . , xm )) ≤ Gal(Ff /E) ≤ Sdeg(f ) .

By [BBR14][Prop 3.6], Gal(Ff .Fq /Fq (x1 , . . . , xm )) ∼
= Sdeg(f )

⇒ Gal(Ff .Fq /Fq (x1 , . . . , xm )) ∼
= Gal(Ff /E) ∼
= Sdeg(f ) ⇒ Ff ∩ Fq = Fq .
Hence Ff /E is a geometric extension. Since Gal(Ff ∩ Fq /Fq ) is trivial, the restriction map
αf : Gal(Ff /E) −→ Gal(Ff ∩ Fq /Fq )

has kernel

ker(αf ) = Gal(Ff /E) ∼
= Sdeg(f ) .

Since Gal(Fq /Fq ) = hτ i ∼
= Z where τ is the q th power Frobenius, homomorphisms from Gal(Fq /Fq ) to
Sdeg(f ) are parametrized by the permutations in Sdeg(f ) they map τ to. That is, σ ∈ Sdeg(f ) corresponds
to θσ ∈ Hom(Gal(Fq /Fq ), Sdeg(f ) ) that takes τ to σ.
Fix a partition λ of deg(f ). For the conjugacy class Θλ := {θσ |σ ∈ Cλ } ⊆ ker(αf ),

|Cλ |
|Θλ |
=
= P (λ)
| ker(α)|
|Sdeg(f ) |
∼ Sdeg(f ) and |Θλ | = |Cλ | and the second
where the first equality follows from the fact that ker(α) =
equality follows from the definition of P (λ).
(4.1)

Equation 4.1 together with Lemma 4.3 applied to the extension Ff /E yields
||{p ∈ Vur,f (Fq )|Θp = Θλ }| − P (λ)q m | ≤ 2P (λ)[Ff : E]m+1 q m/2

where Vur,f (Fq ) ⊆ V (Fq ) is the set of Fq -rational places in E that are etale in Ff . Identifying V (Fq )
with Am (Fq ), a prime p = (a1 , . . . , am ) ∈ Vur,f (Fq ) has Θp = Θλ if and only if λ(Ff (a1 , . . . , am , t)) ∈ Cλ
([Bar12, Lem 2.1]). Thus

For q > 20 deg(f )5 ,

||{(a1 , . . . , am ) ∈ Vur,f (Fq )|λ(Ff (a1 , . . . , am , x)) = λ}| − P (λ)q m |


qm
13/3 m−1
≤ P (λ) (deg(f ) − 1)(deg(f ) − 2) √ + 5 deg(f )
.
q
q
1
(deg(f ) − 1)(deg(f ) − 2) 5 deg(f )13/3
+
≤ ,
√
q
q
2
3P (λ)
P (λ)
|Im (f )| ≤ πq (Im (f ), λ) ≤
|Im (f )| + πqra (Im (f ), λ)
⇒
2
2

where
πqra (Im (f ), λ) := {(a1 , . . . , am ) ∈ V (Fq ) \ Vur,f (Fq )|λ(Ff (a1 , . . . , am , x)) = λ}|

POLYNOMIAL FACTORIZATION AND EULER-POINCARE CHARACTERISTICS OF DRINFELD MODULES

19

accounts for ramified primes with the factorization pattern corresponding to λ. The ramified part
πqra (Im (f ), λ) is bounded by the number of Fq points in the variety defined by the discriminant ∆t (Ff ) ∈
Fq [x1 , . . . , xm ] of Ff with respect to t. By expressing ∆t (Ff ) as the resultant of Ff and its derivative
with respect to t, we see, deg(∆t (Ff )) ≤ 2[Ff : E] − 1. Applying an effective version of the Lang-Weil
bound [CM06], πqra (Im (f ), λ) turns out to be negligible in our computation.
Since [Ff : E] = deg(f )!, for log q > 5 deg(f ) log(deg(f )),
1
3
P (λ)|Im (f )| ≤ πq (Im (f ), λ) ≤ P (λ)|Im (f )|
2
2
and the theorem follows.



Remark 4.5. Recent break through algorithms for discrete logarithm computation [Jou][BGJT] over a
small characteristic finite field (say Frd ) have the following initial polynomial search step. Given r and
d, search for h0 , h1 ∈ Fr2 [t], each of degree 2 such that the factorization of h1 tr − h0 over Fr2 [t] has
an irreducible factor of degree d. The search is known to succeed only under heuristic assumptions. If
Theorem 4.4 were true for q ≥ (n − 1)2 , then as a corollary (by setting q = r2 , f = tr+1 and m = 2), the
search provably succeeds (even when h1 is fixed as h1 = t) without making any heuristic assumptions.
More generally, if Theorem 4.4 holds for q ≥ c1 nc2 for some positive absolute constants c1 , c2 , then the
heuristic assumptions in the polynomial selection step (with appropriate modifications) may be removed.
5. Drinfeld Module Analog of Berlekamp’s Algorithm
We motivate the Drinfeld module analog of Berlekamp’s algorithm with a brief description of Lenstra’s
algorithm for integer factorization. Pollard’s p-1 algorithm [Pol74] is designed to factor an integer that
has a prime factor modulo which the multiplicative group has smooth order. Say for instance that a
positive integer n has a prime factor p such that every prime power factor of p − 1 is bounded by b.
The algorithm proceeds by choosing a positive integer B as the smoothness bound and computes m, the
product of all prime powers bounded by B. A positive integer a < n is then chosen at random. Assume
a is prime to n for otherwise gcd(a, n) is a non trivial factor of n. If B ≥ b, since p − 1 divides m,
am − 1 = (ap−1 )m/(p−1) − 1 ∼
= 0 mod p ⇒ p | am − 1

and gcd(am − 1, n) is likely a non trivial factor of n.

The running time is at least exponential in the size of B. For typical n, B needs to be as big as the
smallest factor of n and thus the running time is typically exponential in the size of the smallest factor of n.
Lenstra’s elliptic curve factorization algorithm [Len87] factors every n in (heuristic) expected time subexponential in the size of the smallest factor p of n. A key insight of Lenstra was to substitute the
multiplicative group (Z/pZ)× in Pollard’s p-1 algorithm with the group E(Fp ) of Fp rational points of a
random elliptic curve E over Fp . The running time depends on the smoothness of the group order |E(Fp )|
√
for a randomly chosen E. The Hasse-Weil bound guarantees that ||E(Fp )| − (p + 1)| ≤ 2 p and Lenstra
proved that his algorithm runs in expected time subexponential in the size of p assuming a heuristic on
√
√
the probability that a random integer in the interval [p + 1 − 2 p, p + 1 + 2 p] is smooth.
Our algorithm can be thought of as an analogue of Berlekamp’s algorithm wherein the Frobenius action is replaced with a random rank-2 Drinfeld action; much like Lenstra’s algorithm is an analogue
of Pollard’s p − 1 obtained through replacing the multiplicative group modulo a prime with a random
elliptic curve group. Before outlining the algorithm, a few remarks regarding notation are in order. For a

20

ANAND KUMAR NARAYANAN

positive integer b, we call a polynomial b-smooth if all its irreducible factors are of degree at most b. For
a Drinfeld module φ (with reduction at primes dividing h) and β ∈ φ(Fh ), by gcd(β, h) we really mean
the gcd of h and a lift of β to A.
Drinfeld Module Analogue of the Black-box Berlekamp Algorithm.
Input : Monic square free reducible polynomial h ∈ A.

(1) Pick a smoothness bound b ≥ 1.
(2) Choose a Drinfeld module φ at random by picking gφ ∈ A and ∆φ ∈ A× each of degree less than
deg(h) independently and uniformly at random.
(3) Choose a random non zero α ∈ φ(Fh ) and compute Ord(α).
(4) Find a monic b-smooth factor f of Ord(α) (if one exists).
(5) Output: gcd(φOrd(α)/f (α), h) is likely a non trivial factor of h.

There is flexibility on how the smooth factor f is determined once b is chosen. One extreme is to set f
to be the largest b-smooth factor of Ord(α). The other, is to further factor the largest b-smooth factor
of Ord(α) (recursively or by other means) and to set f to one of the b-smooth irreducible factors of
Ord(α). A rigorous analysis of the former choice with b = 1 is in § 5.1. An informal discussion of why
the algorithm is likely to succeed with the latter choice follows keeping in mind that
M
φ(Fpi ) , χφ,pi = pi − (aφ,pi − 1)/ǫφ,pi , ∀i.
φ(Fh ) ∼
=
i

For d > 0, a random polynomial of degree d has a linear factor with at least constant probability. Assume
the plausible hypothesis (which is for large q true by Theorem 1.4) that for every i, the probability
of a polynomial in the interval Ipi := {pi + a | a ∈ A, deg(a) ≤ deg(pi )/2} around pi possessing a
b-smooth factor roughly equals the probability of a random polynomial of degree deg(pi ) possessing a bsmooth factor. This smoothness hypothesis along with the equidistribution of characteristic polynomials
(equation 2.1) suggests it is likely for every b > 0 that there exists a j such that χφ,pj = pj −(aφ,pj −1)/ǫφ,pj
has a b-smooth factor. Since Ann(φ(Fpj )) divides χ(φ(Fpj )), it is thus likely that Ann(φ(Fh )) (which is
the least common multiple of {Ann(φ(Fpi ))}i ) has a b-smooth factor. Assuming that is the case, since
α is chosen at random, with probability at least 1 − 1/q there is a monic b-smooth polynomial dividing
Ord(α). The algorithm picks one such monic irreducible factor f of Ord(α). The fact that the reduction
of φ at h is random and equidistribution of characteristic polynomials (equation 2.1) imply the likely
existence of k such that f (t) does not divide χφ,pk . Consequently
Y
φOrd(α)/f (α) ∼
pi
= 0 mod pk , φOrd(α)/f (α) ≇ 0 mod
i6=k

and thus gcd(φOrd(α)/f (α), h) is likely a non trivial factor of h.
The computation of Ord(α) can be performed efficiently through linear algebra as discussed in § 3.1.
This is in stark contrast to the integer analog, where finding the order of an element in the multiplicative
group modulo a composite appears hard. A consequence is that unlike Lenstra’s algorithm, our success
probability is reliant not on χφ,p being smooth but merely on it possessing a smooth factor. The running
times are thus bounded by a polynomial in the problem size.
5.1. Drinfeld Module Analogue of Berlekamp’s Algorithm With Linear Smoothness. In this
section we formally state and analyze the version of the Drinfeld analog of blackbox Berlekamp algorithm
where the smooth factor chosen is the product of all linear factors of the order of a randomly chosen
element in φ(Fh ).

POLYNOMIAL FACTORIZATION AND EULER-POINCARE CHARACTERISTICS OF DRINFELD MODULES

21

Algorithm 5.1.
Input : Monic square free reducible polynomial h ∈ A of degree n.
(1) Choose a Drinfeld module φ by picking gφ ∈ A and ∆φ ∈ A× each of degree less than deg(h)
independently and uniformly at random.
(2) If gcd(∆φ , h) 6= 1, output it as a factor. Else φ has reduction at primes dividing h and we proceed.
(3) Choose α ∈ φ(Fh ) at random and compute Ord(α).
(4) Compute f = gcd(tq − t, Ord(α)).
(5) Compute φOrd(α)/f (α).
(6) Output: gcd(h, φOrd(α)/f (α)).
The running time of the algorithm is dominated by steps (3) and (5). As in § 3.1 , step (3) can be performed with O(n(1+w)/2+o(1) (log q)o(1) + n1+o(1) (log q)2 ) expected time by adapting the automorphism
projection algorithm of Kaltofen-Shoup. Step (5) poses the transpose problem of step (3) and can be
performed in identical expected time as step 3 by the transposition principle (see [KS98, § 3.2]).
The rest of the section is devoted to showing that algorithm 5.1 outputs a non trivial factor of h with
constant probability. In fact, we prove something stronger in Lemma 5.2 by showing that there exists positive constants c1 and c2 such that for every factor pi of h, pi divides gcd(h, φOrd(α)/f (α)) with probability
at least c1 and pi does not divide gcd(h, φOrd(α)/f (α)) with probability at least c2 . As a consequence,
not merely a factor but the complete factorization of h can be obtained by recursing the algorithm with
recursion depth bounded by O((log n)2 ) (see [KS98, § 3]).
Lemma 5.2. There exists positive a constant c such that, for q odd and log q ≥ 5n log n, at the termination of algorithm 5.1, for every prime factor p of h with monic generator p, p divides gcd(h, φOrd(α)/f (α))
with probability at least c and p does not divide gcd(h, φOrd(α)/f (α)) with probability at least c.
Proof. Fix a prime factor p of h with monic generator p. Assume q is odd, log q ≥ 3n log n and let
2
q
Sin := {(a, ǫ) ∈ A × F×
q | deg(a − 4ǫp) = deg(p), gcd(t − t, p − (a − 1)/ǫ) = 1},

2
q
Sout := {(a, ǫ) ∈ A × F×
q | deg(a − 4ǫp) = deg(p), gcd(t − t, p − (a − 1)/ǫ) 6= 1}.
b denote the set of partitions of deg(p)
Let Λ denote the set of partitions of deg(p) that contain 1 and let Λ
that do not contain 1.

Since deg(a2 − 4ǫp) = deg(p) is always true when deg(p) is odd and deg(a) ≤ 2 deg(p), by Theorem
4.4 it follows for deg(p) odd that
!√
X
q(q − 1) q
|Fp |,
|Sin | ≥
P (λ)
2
λ∈Λ


√
X
q(q − 1) q


|Sout | ≥
P (λ)
|Fp |.
2
b
λ∈Λ

When deg(p) is even, since the characteristic of Fq is assumed odd, we can enforce deg(a2 − 4ǫp) = deg(p)
by restricting the choice of ǫ to ensure 4ǫ is not a square in F×
q and picking a ∈ A arbitrarily of degree at
most deg(p)/2. There are at least (q − 1)/2 such choices for ǫ and applying Theorem 4.4 once for each
such choice we get for deg(p) even and Fq of odd characteristic,
!
q
X
q(q − 1)
|Fp |,
2|Sin | ≥
P (λ)
2
λ∈Λ

22

ANAND KUMAR NARAYANAN



2|Sout | ≥ 

X

b
λ∈Λ



q(q − 1)
P (λ)
2

q
|Fp |.

The number of permutations in Sdeg(p) with no fixed points is ⌈deg(p)!/e⌉ if deg(p) is even and
⌊deg(p)!/e⌋ otherwise. Thus
X
X
⌊deg(p)!/e⌋
⌈deg(p)!/e⌉
P (λ) ≥
and
P (λ) ≥ 1 −
deg(p)!
deg(p)!
λ∈Λ

b
λ∈Λ

and there exists positive constants b1 , b2 such that
X
X
P (λ) ≥ b1 and
P (λ) ≥ b2 .
λ∈Λ

b
λ∈Λ

Applying Lemma 2.3 once each to Sin and Sout , there exists positive constants d1 and d2 such that,
{(φ/p)|(aφ,p , ǫφ,p ) ∈ Sin } ≥ d1 |Fp ||F×
p |,

{(φ/p)|(aφ,p , ǫφ,p ) ∈ Sout } ≥ d2 |Fp ||F×
p |.

Since gφ ∈ A and ∆φ ∈ A× are each chosen of degree less than deg(h) independently and uniformly at
random and gcd(∆φ , h) = 1, by the chinese remainder theorem (gφ mod p, ∆φ mod p) is distributed
uniformly in Fpi × F×
pi . Thus the probability that Ann(φ(Fp )) has a linear factor is at least d1 and
the probability that Ann(φ(Fp )) does not have a linear factor is at least d2 . Since the projection of a
random α ∈ φ(Fh ) into φ(Fp ) has order Ann(φ(Fp )) with probability at least (1 − 1/q) ≥ 1/2, the lemma
follows.

Remark 5.3. If q < 5n log n, we may work over a finite extension F′q /Fq such that q ′ ≥ 3n log n and by
Lemma 5.2 be assured that the algorithm 5.1 succeeds, however, we incur an extra factor of n in the
expected running time. If Conjecture 4.2 is true, then Lemma 5.2 holds with only the requirements that
√
√
q is odd and q ≥ 2n. The assumption q ≥ 2n may be made without loss in generality (Remark 3.2).
Acknowledgement
I thank Lior Bary-Soroker, Zeyo Guo, Ming-Deh Huang and Chris Umans for valuable discussions.
References
[BBR14] E. Bank, L. Bary-Soroker and L Rosenzweig, Prime polynomials in short intervals and in arithmetic progressions,
http://arxiv.org/abs/1302.0625
[BGJT] R. Barbulescu, P. Gaudry, A. Joux , E. Thome, “A quasi-polynomial algorithm for discrete logarithm in finite
fields of small characteristic”, http://arxiv.org/abs/1306.4244
[Bar12] L. Bary-Soroker, Irreducible values of polynomials, Adv. Math., 229 (2), 854-874 (2012).
[Ber67] E. R. Berlekamp, Factoring Polynomials Over Finite Fields, Bell System Tech. J., 46:1853-1849. 1967.
[CM06] A. Cafure and G. Matera, Improved explicit estimates on the number of solutions of equations over a finite field,
Finite Fields and Their Applications Volume 12, Issue 2, April 2006, Pages 155185
[Coh] S. D. Cohen, The Distribution of Polynomials over Finite Fields, Acta Arith., 17 (1970), 255-271.
[CZ81] D. G. Cantor and H. Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp., vol.
36, 587592, 1981.
[CP14] A. C. Cojocaru and M. Papikian, Drinfeld Modules, Frobenius Endomorphisms, and CM-Liftings, Int Math Res
Notices (2014)
[Cor99] G. Cornellison, Deligne’s congruence and supersingular reduction of Drinfeld modules, Arch. Math. 72 (1999)
346-353.
[Del74] P. Deligne, “La conjecture de Weil. I”, Publications Mathematiques de l’IHES (43): 273-307.
[Deu41] M. Deuring, Die Typen der Multiplikatorenringe elliptischer Funktionenkorper, Abh. Math. Sem. Hamburg 14
(1941), 197272. MR0005125.

POLYNOMIAL FACTORIZATION AND EULER-POINCARE CHARACTERISTICS OF DRINFELD MODULES

23

[Dor] D. R. Dorman, On singular moduli for rank 2 Drinfeld modules, Compositio Mathematica (1991) Volume: 80, Issue:
3, page 235-256.
[Dri74] V. G. Drinfeld, Elliptic modules, Mat. Sb. (N.S.), 1974, Volume 94(136), Number 4(8), Pages 594627
[Dri77] V. G. Drinfeld, Elliptic modules. II, Mat. Sb. (N.S.), 102(144):2 (1977), 182-194.
[vzGS92] J. von zur Gathen and V. Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity,
vol. 2, 187-224, 1992.
[Gek08] E-U Gekeler, Frobenius distributions of Drinfeld modules over finite fields, Trans. Amer. Math. Soc. 360 (2008),
1695-1721.
[Gek91] E-U Gekeler, On finite Drinfeld modules, Journal of Algebra, Volume 141, Issue 1, 1 August 1991, Pages 187-203.
[Gos96] D. Goss, Basic Structures of Function Field Arithmetic, Ergeb. Math. Grenzgeb. (3), vol. 35, Springer, Berlin,
1996.
[GNU15] Z. Guo, A. Narayanan and C. Umans, Algebraic problems equivalent to beating the 3/2 exponent for polynomial
factorization over finite fields, In preparation.
[vdH04] G. J. van der Heiden, Factoring polynomials over finite fields with Drinfeld modules, Math. Comp. 73 (2004),
317-322.
[vdH04-1] G. J. van der Heiden, Addendum to “Factoring polynomials over finite fields with Drinfeld modules”,Math.
Comp. 73(2004), Number 248, Page 2109
[Jou] Antoine Joux. A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic. Cryptology
ePrint Archive, Report 2013/095, 2013.
[KL94] E. Kaltofen and A. Lobo, Factoring high-degree polynomials by the black box Berlekamp algorithm, ISSAC ’94
Proceedings of the international symposium on Symbolic and algebraic computation Pages 90 - 98.
[KS98] E. Kaltofen and V. Shoup, Subquadratic-time factoring of polynomials over finite fields, Math. Comput.,
67(223):1179-1197, July 1998.
[KU08] K. Kedlaya and C. Umans, Fast modular composition in any characteristic, Proceedings of the 49th Annual IEEE
Symposium on Foundations of Computer Science (FOCS). pages 146-155. 2008.
[Len87] H. W. Lenstra Jr, Factoring integers with elliptic curves, Annals of Mathematics 126 (3): 649673. (1987).
[Nar14] A. K. Narayanan, Computation of Class Groups and Residue Class Rings of Function Fields over Finite Fields,
Ph.d Dissertation, Computer Science Department, University of Southern California 2014.
[PP89] A. Panchishkin and I. Potemine, An algorithm for the factorization of polynomials using elliptic modules, In Proceedings of the Conference, Constructive methods and algorithms in number theory, p. 117. Mathematical Institute of
AN BSSR, Minsk, 1989 (Russian).
[Pol74] J. M. Pollard, Theorems of factorization and primality testing, Proceedings of the Cambridge Philosophical Society
76 (3): 521-528. (1974).
[Sch95] R. Schoof: Counting Points on Elliptic Curves over Finite Fields. J. Theor. Nombres Bordeaux 7:219254, 1995.
[Sto01] A. Storjohann, Deterministic computation of the Frobenius form, In Proc. 42nd Annual Symp. Foundations of
Comp. Sci., pages 368-377, 2001.
[VS] G. D. Villa Salvador, Topics in the Theory of Algebraic Function Fields, 2006. Birkhauser, 2006.
[Yu95] J-K Yu, Isogenies of Drinfeld modules over finite fields, J. Number Th. 54 (1995), 161-171.
[Yun76] D. Y. Y. Yun, On square-free decomposition algorithms, Proc. 1976 ACM Symp. on Symbolic and Algebraic
Computation ISSAC 76.
Anand Kumar Narayanan, Department of Computing and Mathematical Sciences, California Institute of
Technology, Pasadena, California, USA, 91125
E-mail address: anandkn@caltech.edu

