Events Calendar

PhD Defense- Anand Kumar Narayanan

Title: Computation of Class Groups and Residue Class Rings of Function Fields over Finite Fields.

PhD Candidate: Anand Kumar Narayanan

Committee: Ming-Deh Huang (Chair), Leonard Adleman, Sheldon Kamienny (External member)

Time: Monday, Jun 16, 1:00pm-3:00pm. Location: EEB 248

Abstract.

We study the computation of the structure of two naturally occurring 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.

Let k be the rational function field over a finite field and let F/k be a finite geometric abelian extension with a rational place that completely splits. We prove that for all primes p neither dividing the characteristic of k nor the degree of F/k, the structure of the p-part of the divisor class group of F is determined by Kolyvagin derivative classes that are constructed out of Euler systems associated with Stark units. Further, we describe an algorithm to compute the structure of the p-part of the divisor class group given a certain Galois module generator of the Stark units. Unlike index calculus methods, our algorithm for computing divisor class groups is deterministic. Other applications of our technique include a fast algorithm for computing the divisor class number of narrow ray class extensions.

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 with p^n 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.

In addition, we present a novel algorithm to factor polynomials over finite fields using Carlitz modules from the arithmetic theory of function fields.

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Lizsl De Leon