Counting Polynomials over Finite Fields and Analysis of Algorithms

Daniel Panario

University of Toronto

Algorithms Seminar

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

1   Motivation

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 expressions, and 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 F. Let
F(z,u)=
 
�
w�F
z
|w|
 
u
c(w)
 
.
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:
[zn]
� P(z,u)
� u
�
�
�
�
 



u=1
[zn]P(z,1)
=
pn'(1)
pn(1)
.

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 (isolated singularity). 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 approximation.

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 [1]. The Polynomial factorization algorithm proceeds in three steps:

ERF
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.
DDF
Distinct-degree factorization splits a square-free polynomial into a product of polynomials whose irreducible factors all have the same degree.
EDF
Equal-degree factorization factors a polynomial whose irreducible factors have the same degree.
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.

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:

Theorem 1   (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 asymptotic to
Cq=
 
�
n� 1
nIn
q2n-qn
,
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.

Theorem 2   The expected cost of the ERF phase applied to a random polynomial of degree n satisfies
ERF
n~ t2 n2.

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.

Theorem 3   (i) The probability that DDF yields the complete factorization is asymptotic to
cq=
 
�
n� 1
�
�
�
�		 1+
In
qn-1
�
�
�
�		 (1-q-n)
In
 
,
c2 �
=		 0.6656, c257 �
=		 0.5618,  c
 
�
=e
-g
 
�
=		 0.5614.

(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' probabilistic algorithm.

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 � l,j-l� factors with Bernoulli probability (
j
l
) al bj-l. The analysis combines a recursive partitioning problem akin to digital tries with estimates on the degree of irreducible factors of random polynomials.

Theorem 4   The expected cost of the EDF phase satisfies
EDF
n~
t1
ab
[n/2]
�
k=1
�k,    �k= \lfloor log2(qk-1)/2 \rfloor +n(qk-1)/2-1.
In addition, this cost is O(n2), and for -1/3� xn�1/3,
EDF
n~ �
�
�
�
3
4
t1
q2
q2-1
log2 q� n2 �
�
�
�		 (1+xn+o(1)).

4   Irreducibility tests for polynomials

A fundamental problem in finite fields is the construction of extension fields, that may be done by using 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 [5]. 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 [2] considered the case m=O(log n) and proved:
Theorem 5   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),
Pq(n,m) =
m
�
k=1
�
�
�
�		 1 -
1
qk
�
�
�
�
Ik



 
(1+ o(1)),

Theorem 6   Let gq(m) = �k=1m (1 - 1/qk)Ik. Then, for any prime power q and positive integer m,
e
-Hm
 
� gq(m) � �
�
�
�		 1-
1
(q)1/2
�
�
�
�
-
q
q-1



 
e
-Hm
 
.
When q � �, we have
gq(m) =
m
�
k=1
�
�
�
�		 1 -
1
qk
�
�
�
�
Ik



 
� e
-Hm
 
~
e
-g
 
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 h=�i=1t piei. If each irreducible factor pi has degree pi � m, then
log g =
t
�
i=1
ei log pi - a,
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  [[4]]   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, and let
b(r0)= �
�
�
�
fm
'
 
fm
(r) �
�
�
�
'



 
�
�
�
�
�
�
�
 






r=r0
.
Then, for
(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 recurrences relations. This could be done using partial fraction expansions for 1� m � (log n)(loglog n )-1, and singularity analysis for n loglog n (log n)-1.

6   Conclusions

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 algorithm [1]. Using this methodology, von zur Gathen, Gourdon & Panario (work in progress) present further research related to the average-case analysis of polynomial factorization algorithms. This work centers around [3], and the factoring algorithms of the 90's.

We also commented on other problems using polynomials over finite fields: tests and constructions of irreducible polynomials [2]; discrete log in F2n [4]; (see also Panario & Viola, work in progress).

References

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

[2]
Gao (Shuhong) and Panario (Daniel). -- Density of normal elements. Finite Fields and their Applications, vol. 3, n°2, 1997, pp. 141--150.

[3]
Kaltofen (E.) and Shoup (V.). -- Subquadratic-time factoring of polynomials over finite fields. Mathematics of Computation, April 1998. -- To appear.

[4]
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 Paris, 1984.

[5]
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 HEVEA.