Counting Polynomials over Finite Fields and Analysis of Algorithms
University of Toronto
October 7, 1996
[summary by Mireille Régnier]
A properly typeset version of this document is available in postscript
and in pdf
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
In this talk, we comment on
several problems in finite fields,
and their relation with analytic combinatorics.
Algebraic algorithms that deal with polynomials
over finite fields can often be analyzed by counting
polynomials with particular properties.
We show that the most important characteristics
of these algorithms can be treated systematically
by a methodology based on generating functions
and asymptotic analysis.
We focus on three problems: polynomial factorization,
irreducibility tests for polynomials, and
discrete logarithm. For each problem,
we present an efficient algorithm,
we derive interesting counting
we mention known results.
2 Basic methodology
2.1 Generating functions
Let F be a class of monic polynomials,
c some integer-valued parameter on
The coefficient [znuk]F(z,u)
represents the number of polynomials
of degree n with c-parameter
equal to k.
Averages and standard deviations are
obtained by taking successive derivatives
of bivariate generating functions with
respect to u, then setting u=1.
For instance, the mean is:
2.2 Asymptotic analysis
Generating functions encode exact
informations on their coefficients.
Their behavior near their dominant
singularity is an important source
of coefficient asymptotics.
A first method is known as singularity
analysis due to Flajolet & Odlyzko.
This requires analytic continuation
However, there are some problems in which
the generating functions
present a natural boundary at |z|=1
(each point at the unit circle is singular).
Darboux's method could be
used as an alternative in these cases.
Finally, in some cases we use also a saddle point
2.3 Permutation model
The joint distribution of degrees in the prime
decomposition of a random polynomial over Fq
having degree n admits as a limit, when q®¥
(n staying fixed!), the joint distribution of cycle
lengths in random permutations of size n.
This gives rise to a useful heuristic:
probabilistic properties of polynomial factorization
often have a shape resembling that of corresponding
properties of the cycle decomposition of permutations
to which they usually reduce as q®¥.
3 Factoring polynomials over finite fields
The results in this part of the talk are from .
The Polynomial factorization algorithm proceeds in three steps:
As our interest is in dominant asymptotics,
we restrict our attention to the costs
of products and gcd's that we assume to have
constant costs t1 and t2 respectively.
- Elimination of repeated factors
replaces a polynomial by square-free ones that
contain all the irreducible factors of the
original polynomial with exponents reduced to 1.
- Distinct-degree factorization
splits a square-free polynomial into a product
of polynomials whose irreducible factors
all have the same degree.
- Equal-degree factorization
factors a polynomial whose irreducible factors
have the same degree.
3.1 Elimination of repeated factors (ERF)
The first step in the factorization chain
of a polynomial is the elimination of
repeated factors (ERF).
One proves that:
(i) A random
polynomial of degree n³ 2 in Fq[x] has
a probability 1-1/q to be square-free.
(ii) The degree of the non-square-free part
of a random polynomial has expected value
where In is the number of irreducible polynomials of degree n,
and a geometrically decaying probability tail.
When q® ¥, then Cq ~ 1/q.
Consequently, the overall cost of the recursive
calls in the elimination of repeated factors
remains O(1) on average;
alternative strategies giving the
full square-free factorization will
lead to asymptotically equivalent
costs; the ERF phase has a cost
dominated by that of its first gcd.
The expected cost of
the ERF phase applied to a random polynomial
of degree n satisfies
3.2 Distinct-degree factorization (DDF)
The second stage of our factorization
algorithm requires finding the distinct-degree factorization (DDF)
of the square-free polynomial a, i.e.,
splitting a under the form
b1··· bn where bk
is the product of irreducible factors
of a of degree k.
The algorithm is O(n3).
We provide a precise comparison of three
strategies for the DDF phase: the basic
rule, the ``half-degree'' rule and the
``early abort'' rule.
The global saving of the early abort
rule is of 36%, and the expected cost
of O(log q · n3) for DDF clearly
dominates the whole factorization chain.
3.3 Equal-degree factorization (EDF)
DDF does not completely factor a
polynomial that has different factors of same degree.
probability that DDF yields the complete
factorization is asymptotic to
(ii) The degree of the part of the polynomial
that remains to be factored by the EDF
algorithm is asymptotic to log n.
The factorization problem is reduced
to factoring polynomials bk that
have all their irreducible
factors of the same (known) degree k.
Our reference is Cantor-Zassenhaus'
Each factor of b has probability
a=(q-1)/(2q) to be a
factor of d, and probability
b=(q+1)/(2q) to divide b/d.
A random choice splits b in
factors with Bernoulli probability
() al bj-l.
The analysis combines a recursive
partitioning problem akin to digital
tries with estimates on the degree
of irreducible factors of random
The expected cost of the EDF phase satisfies
this cost is O(n2), and for
|| µk, µk=
||log2 q· n2
4 Irreducibility tests for polynomials
A fundamental problem in finite fields
is the construction of extension fields, that may be done
an irreducible polynomial over
the ground field with degree equal to the
degree of the extension.
Therefore, finding irreducible polynomials
is a central problem in finite fields.
A probabilistic algorithm is presented in .
The central idea is to take polynomials
at random and test them for irreducibility.
This suggests the study of the
probability that a random polynomial
of degree n contains no irreducible
factors of degree up to certain value
m (such polynomials are called m-rough).
Gao and Panario  considered the case m=O(log n) and proved:
Denote by Pq(n,m) the probability of a random
monic polynomial of degree n over Fq being m-rough.
Then when n ® ¥ and uniformly for q and 1 £ m £ O(log n),
Let gq(m) = Õk=1m
(1 - 1/qk)Ik.
Then, for any prime power q and
positive integer m,
When q ® ¥,
£ gq(m) £
where g is Euler's constant
and e-g = 0.56416....
5 Discrete logarithm problem
For any element b Î Fq, b ¹ 0,
there exists an integer x, 0£ x £ q-2,
such that b=ax, where a is a generator.
We call x the discrete
logarithm of b in the base a.
We present here the index calculus algorithm
to compute the discrete logarithm of
any b Î Fq, b ¹ 0 and restrict ourselves to the case of F2n.
This method consists of two parts. First, one builds
a large database of logarithms by finding
the logarithms of all irreducible
polynomials of degree at most m, where m
is a fixed positive integer.
Second, one computes individual logarithms.
To compute the logarithm of an
element g Î F2n, g¹0, one takes a random
integer a, computes h=g· aa, where
a generates F2n and factors h in
If each irreducible factor pi has degree
pi £ m, then
which can be easily evaluated by looking up in the database.
If not all pi have degree £ m, then one
generates another integer a and repeats.
Theorem 7 []
Let Fq be fixed, fm(z) = Õk=1m
(1-zk)-Ik, and r0=r0(n,m) be the
unique solution in (0,1) of the equation r0(fm'/fm)(r0) = n,
|(log n)(loglog n )-1£
m £ n loglog n (log n)-1, n® ¥,
|fm(z) = (1 + o(1))
|fm (r0) r0-n
|(2 p b(r0))1/2
Soundararajan (1995) completed the full range
of m estimating [zn]fm(z) using
This could be done
using partial fraction expansions for
1£ m £ (log n)(loglog n )-1,
and singularity analysis for n loglog n
Generating functions and
singularity analysis allow for
counting random polynomials over finite fields.
We applied this methodology to give
precise average-case analysis of a
complete polynomial factorization
Using this methodology,
von zur Gathen, Gourdon & Panario
(work in progress) present
further research related to the
average-case analysis of
algorithms. This work centers
and the factoring algorithms
of the 90's.
We also commented on other problems
using polynomials over finite fields:
tests and constructions of irreducible
discrete log in F2n ;
(see also Panario & Viola, work in progress).
Flajolet (Philippe), Gourdon (Xavier), and Panario (Daniel). --
Random Polynomials and Polynomial Factorization. --
Research Report n°2852, Institut National de Recherche en
Informatique et en Automatique, March 1996. To appear in the
Proceedings of ICALP'96, Lecture Notes in Computer Science.
Gao (Shuhong) and Panario (Daniel). --
Density of normal elements. Finite Fields and their
Applications, vol. 3, n°2, 1997, pp. 141--150.
Kaltofen (E.) and Shoup (V.). --
Subquadratic-time factoring of polynomials over finite fields. Mathematics of Computation, April 1998. --
Odlyzko (A. M.). --
Discrete logarithms in finite fields and their cryptographic
significance. In Advances in cryptology. Lecture Notes in Computer
Science, vol. 209, pp. 224--314. --
Berlin, 1985. Proceedings of a conference held in
Rabin (Michael O.). --
Probabilistic algorithms in finite fields. SIAM Journal on
Computing, vol. 9, n°2, 1980, pp. 273--280.
This document was translated from LATEX by