Computation of class groups and residue class rings of function fields over finite fields
Anand Kumar Narayanan · University of Southern California Digital Library · 2014
We study the computation of the structure of two finite abelian groups associated with function fields over finite fields: the degree zero divisor class group and the multiplicative group of the finite field itself. In addition, we present a novel algorithm to factor polynomials over finite fields using Carlitz modules. ? Let F_q denote the finite field with q elements and let k = F_q(t) be the rational function field with constant field F_q. Let F/k be a finite geometric abelian extension where an F_q?rational place in k denoted as ? splits completely. Stark units are certain functions in F whose existence is claimed in the function field analogue of the Brumer?Stark conjecture. In the function field setting, the Brumer?Stark conjecture and hence the existence of Stark units was proven by P. Deligne. Further, Stark units are determined by the evaluations at 0 of Artin's L?functions associated with the complex characters of Gal(F/k). We prove that for all primes ? not dividing q[F : k], the structure of the ??part of the divisor class group of F is determined by Kolyvagin derivative classes that are constructed out of Euler systems associated with the Stark units. ? Further, given a certain ?[Gal(F/k)] generator of the Stark units, we describe an algorithm to compute the structure of the ??part of the divisor class group. When F/k is a narrow ray class field (or a small index subextension of a narrow ray class field), such a generator of the Stark units module can be efficiently computed. ? The divisor class group Cl^0_F of F is a finite abelian group and fits in the exact sequence ? 0 ? R_F ? Cl^0_F ? pic(O_F) ? 0 ? where R_F is the regulator and pic(O_F) is the ideal class group of O_F. Our algorithm to compute the ??part of the divisor class group is heavily reliant on the machinery of Euler systems of Stark units and is efficient if the ??part of the ideal class group is small. Empirical and heuristic evidence point to the ideal class group being of very small order in comparison to the divisor class group. ? Other applications of our technique include a fast algorithm for computing the divisor class number of narrow ray class extensions. ? We next turn to computing primitive elements in finite fields of small characteristic. The multiplicative group of a finite field is cyclic and generators (primitive elements) are abundant. However, finding one efficiently remains an unsolved problem. We describe a deterministic algorithm for finding a generating element of the multiplicative group of the finite field F_{p^n} with p? elements where p is a prime. In time polynomial in p and n, the algorithm either outputs an element that is provably a generator or declares that it has failed in finding one. Under a heuristic assumption, the algorithm does succeed in finding a generator. The algorithm relies on a relation generation technique in a recent breakthrough by Antoine Joux's for discrete logarithm computation in small characteristic finite fields. ? Building upon Joux's algorithm, Barbulescu, Gaudry, Joux and Thome proposed a descent algorithm for computing discrete logarithms in finite fields of small characteristic in quasi?polynomial time. To succeed, both algorithms are reliant on heuristic assumptions. We identify obstructions that prevent certain heuristic assumptions they make from being true in general. Further, we describe methods to overcome these obstructions. ? The final chapter presents an intriguing connection between the structure of Carlitz modules and polynomial factorization over finite fields resulting in a new algorithm for distinct degree factorization.