Research Statement
Eric J. Landquist
1. Introduction
My primary research interests are computational
algebraic number theory and cryptography. More specifically, these
interests include integer factorization and the discrete logarithm
problem in various groups, but my current research focuses on cubic
function fields of large prime characteristic. In particular, my
research centers on the computation of certain invariants of these
fields: the divisor and ideal class numbers, regulator, and the
fundamental units of the maximal order. The computation of these
invariants of number fields and function fields are central problems in
algebraic number theory. One of the main reasons for their importance,
especially the class numbers, is that they are the order of certain
groups that have potential application to cryptography. Any
cryptographic setting requires, among other things, a group of large
non-smooth order. Although it is possible that cubic function fields
will be of direct use for cryptography, it is more likely that insights
gained from their study may be applied for use in protocols based on
quadratic, i.e. elliptic and hyperelliptic, function fields, which do
have serious potential for use today. Aside from these applications,
these fields do give rise to some very interesting theoretical problems
which we have only begun to understand.
2. Background
Let Fq(x) be the
field of rational functions with coefficients in Fq
, where q > 3 is prime. Analogously to number fields, we may
define a finite algebraic extension K over Fq(x).
Let F(x,y) be an absolutely irreducible
cubic polynomial in y with
coefficients in Fq[x]. We can write F(x,y)
= y3 − A(x)y + B(x)
= 0, where B(x) is nonzero, and there does not
exist a polynomial Q(x) ∈ Fq[x] such that Q2(x)| A(x)
and Q3(x)|B(x). Then K = Fq(x,y)
is a separable extension of Fq(x) of degree 3. If A(x)
= 0, then K is said to be a
purely cubic function field. We define h to be the divisor class number of
K, or in other words, the
order of the divisor class group, or Jacobian, of K. The Hasse-Weil Theorem tells us
that h lies in the interval [
(√(q) − 1)2g, (√(q) + 1)2g ], where g is the genus of K.
Let OK be the maximal order of K, let OK* ≅ Fq × Z r be the unit group of OK, and let hK denote the (ideal)
class number of OK, that is the order of the
(ideal) class group of OK. If the unit rank r is positive, then we define any
generating set of the free part of OK*
as the fundamental units of OK
(or K). We denote this set {ε1,
..., εr}. We note that in the
unit rank 1 case, ε is unique up to constant multiples and inversion,
but in the unit rank 2 case, the set of fundamental units is not
uniquely determined in this way.
The εi
are doubly exponential in the size of K,
so fundamental units cannot be computed in fields of large
characteristic or genus. For fields of large characteristic or genus,
we instead wish to compute a related, but more tractable quantity
called the regulator, R. We
will define this for the various unit ranks based on the splitting of
infinity. If the place at infinity splits ∞ = ∞1 … ∞r+1,
then let vi be the
additive discrete valuation corresponding to ∞i. In unit rank 0, R = 1; in unit rank 1, R = |v2(ε)| = |v1(ε)|/2; and finally in
unit rank 2,
R = |
v1(ε1)
v1(ε2) |
| v2(ε1)
v2(ε2) |
.
Despite the fact that the set of fundamental units is not unique, R is independent of these choices
in any unit rank.
To relate these quantities, if f is the greatest common divisor of
the inertia degrees of the ∞i,
then fh = RhK. In most cases, f = 1 so that h = RhK. For positive unit
rank, hK will
generally be very small, usually trivial, so that h is a small multiple of R.
In the unit rank 1 and 2 cases, the ideal class
group is not very exciting, but in the principal ideal class, we
instead find a very interesting object of study that in addition aids
us in computing the fundamental units and regulator. This is the
infrastructure of the principal ideal class, a set of reduced principal
ideals that almost forms a group under ideal composition, i.e. ideal
multiplication followed by reduction. In fact, any function field or
number field of positive unit rank exhibits an infrastructure. The
infrastructure was first discovered in real quadratic number fields by
Shanks [4], and provides the framework for the fastest known algorithms
to compute the desired invariants in many of these fields.
Infrastructure in unit rank 1 fields is a cycle with an additional
operation called a baby step that maps an ideal to an adjacent ideal on
the cycle. This baby step is similar to addition by 1 in Z/nZ. In unit rank
2 however, the infrastructure is toroidal in structure, bicyclic, but
irregular; there are baby steps in two directions in this situation.
The unit rank 2 situation is very interesting mathematically, and
presents us with some unique problems because we must now study how two
cycles behave and interact. This is one of the main motivations for my
research.
3. Current Research
My thesis research is divided into three components.
The first component develops ideal arithmetic in purely cubic function
fields. The second gives results on optimizing class number computation
in unit rank 0 fields, and the last seeks to understand the structure
and arithmetic of unit rank 2 infrastructure, leading to insights into
how general infrastructure behaves in function fields of higher degree.
This understanding will allow us to then compute class numbers and
regulators in unit rank 2 fields much faster than current methods
allow. In fact, there is evidence that class numbers can be computed
faster in the unit rank 2 setting than in the other cases.
The first contribution of my thesis work describes
the ideal arithmetic of all purely cubic function fields. In [2],
Scheidler describes ideal squaring and the multiplication of two ideals
that do not share any factors. Later, Bauer [1] described this
arithmetic for all nonsingular fields. Therefore my thesis extends this
work to describe the multiplication of any two ideals in the singular
case as well, completing the description of ideal arithmetic in purely
cubic function fields of characteristic at least 5. This arithmetic was
then implemented in order to compute divisor class numbers.
A method due to Scheidler and Stein [3] computes
divisor class numbers in time roughly O(q(2g−1)/5), an improvement over
previous techniques for g ≥
3. They use an Euler product form of the L-polynomial of a cubic function
field K to find an estimate E of h and an upper bound U on the error |h − E| so that h lies in the interval [E − U, E + U]. For fields of genus at least 3,
this interval is smaller than the Hasse-Weil interval. One of two
methods then searches for h,
either Shanks' baby step-giant step algorithm or the parallelized
kangaroo method due to Pollard. My work in this area centers on looking
for ways to improve either the estimation phase or the search phase,
and then implementing these methods and improvements. The most fruitful
results thus far have been in the search phase. Class numbers are not
evenly distributed in the interval [E
− U, E + U], so I have collected data to
find the average error |h − E|/U
for various genera. This allows us to make near optimal parameter
selections and speed up overall running times. Using these techniques,
25-digit class numbers have been computed for fields of unit rank 0 of
genus 3 and 4.
It is not yet known how to apply the aforementioned
technique to compute regulators of unit rank 2 fields, so the last
portion of my thesis work seeks to understand this case. Regulator and
class number computation in unit rank 1 infrastructure usually involves
performing a baby step-giant step procedure on the cycle, advancing
along the cycle quickly via ideal composition. In unit rank 2
infrastructure, however, we must traverse both cycles in order to find
the regulator. A major obstruction, though, is that the composition of
two ideals on one period is not always an ideal on that same period. So
one problem my research addresses is how to properly move along either
cycle using giant steps. This requires the proper definition of the
notion of distance, which will generalize an analogous property of unit
rank 1 infrastructure. My approach to this involves explaining the
theory of infrastructure in terms of divisor arithmetic rather than
ideal arithmetic. This will also provide an explanation of
infrastructure that is clearer and more intuitive than most other
treatments.
4. Future Research
The next steps of my research will pursue the
natural extensions of my thesis work, along with unanswered questions
that will undoubtedly arise in the course of my research. I wish to
learn more about period lengths and arithmetic of unit rank 2
infrastructure and use that to apply Scheidler and Stein's class number
computation method to the unit rank 2 setting. By splitting their
interval [E − U, E + U] into two, significant speed
gains should be realized. Another goal is to generalize the arithmetic
of purely cubic function fields to arbitrary cubic function fields of
characteristic greater than 3. I wish to develop libraries that perform
arithmetic in cubic function fields as well, building on the package
that I am currently using. When it is completed, this library will be
available for public use. A deeper knowledge and understanding of unit
rank 2 infrastructure in general will also be sought. With some more
light shed on this case, I believe that we will be able to understand
general infrastructure of arbitrary unit rank more fully.
5. Career Research Goals
Understanding unit rank 2 infrastructure in cubic
function fields is a pivotal step to understanding infrastructure of
fields of higher degree and of greater unit rank because of the
presence of multiple periods and structural dimensions. One of my long
term visions is therefore to work towards the development of a general
infrastructure theory spanning global fields of all unit ranks. This
will have to be a team effort, and I have contact with a number of
other researchers working in this area, so this goal is certainly
attainable. After sufficient progress has been made in cubic fields of
unit rank 2, the next step in this generalization will be to consider
quartic function fields of unit rank 2 and 3. This theory will be
applied to computing class numbers and regulators, with explorations
into improved techniques for effective computations. This area of study
as a whole is relatively unexplored, but is a mathematically
fascinating area of research with consequences that cannot yet be
imagined.
References
[1] M. Bauer. The Arithmetic of Certain Cubic Function Fields. Math. Comp., 73: 387 − 413, 2004.
[2] R. Scheidler. Ideal arithmetic and infrastructure in purely cubic
function fields. Journal de Théorie
des Nombres de Bordeaux, 13:
609 − 631, 2001.
[3] R. Scheidler and A. Stein. Class number approximation in cubic
function fields. Contributions to
Discrete Mathematics, 2:
107 − 132, 2007.
[4] D. Shanks. The infrastructure of a real quadratic field and its
applications. Proc. 1972 Number
Theory Conference, Boulder, 217 − 224, 1972.