My primary research interest is the computation of invariants of algebraic function fields and
algebraic number fields of small degree. This includes the design, analysis, and implementation of algorithms for determining these invariants. For now, the fields in question are quadratic and cubic extensions of a rational function field in one variable over a finite field (in the function field case) or of the rationals (in the number field case). In the future, the study will hopefully be extended to quartic extensions, and eventually to fields of higher degree.
For an algebraic function field K defined by an irreducible projective curve over some finite field of constants k, it is of interest to consider the formal group
generated by the points that lie on the curve, called the group of divisors of K. (In some cases, such as for elliptic curves, the points themselves form a group.) For a divisor D, written as a linear combination of points on our curve, the degree of D is the sum of all the integer coefficients in the linear combination. K itself can be embedded into the group of divisors, and all the divisors arising from elements in K (called principal divisors) have degree 0.
Thus, we have an equivalence relation on the set of divisors of degree 0: two such divisors are
equivalent if they differ by a principal divisor. The set of equivalence classes form themselves a finite Abelian group that is isomorphic to the group of k-rational points on the Jacobian of K. Algebraic geometers are interested in the order h
of this group, sometimes called the class number of K. It is an invariant of K that is generally very difficult to compute.
My goal is to develop algorithms for determining h. These methods exploit the fact
that the field has a representation as an extension of small degree of some suitable field of rational functions. For now, these procedures will only work in these low degree extensions, but they are significantly faster than the general techniques.
Ideal Class Group and Ideal Class Number
A fractional ideal is simply an ideal in the ordinary sense with a "denominator" which in our context is a nonzero integer (in the number field setting) or a polynomial (in
the function field case). The nonzero fractional ideals of the ring of integers O of a number of function field K form a group under multiplication, which contains the subgroup of all the nonzero fractional principal ideals. The factor group of the former
group by the latter is the ideal class group of K. Its order h' is the ideal class number of K. h' can be viewed as a measure of how badly the maximal order O of K fails at unique prime factorization: h' = 1 if and
only if O is a unique factorization domain, and the larger h' is, the further away O is from unique prime factorization. h' is another invariant of K (in the function field case, that's cheating a bit: we have to fix a transcendental element
for our extension, on which h' depends). The computation of h' is of interest in its own right, but it also aids in determining the class number h of a function field K because h' and h are equal up to a certain factor.
Fundamental Units and Regulator
The group of units O* of the maximal order O is an infinite Abelian group whose rank is the unit rank of K. Its torsion part consists of the roots of unity in K, and a set of generators for the torsionfree part of O* is a system of fundamental units of K. A central problem in number theory is finding such a system of fundamental units. This is hard (especially for large unit rank), so for now, I am restricting myself to the cases of unit rank 1 and 2, although I hope to tackle
higher unit rank some day.
One difficulty in computing fundamental units is the fact that they can be extremely large, so we compute the regulator R instead. In number fields of unit rank 1, this is simply the logarithm of a (positive) fundamental unit. In unit rank 1 function fields, the regulator R is (up to possibly a small factor) equal to the degree of a fundamental unit of positive degree (once again, we've slightly cheated here: if t is our transcendental element, we need to be able to embed K into the field k((1/t)) of Laurent series over k in 1/t, so the notion of "degree" makes sense, and this isn't always possible). In unit rank 2 extensions, we need to take the logarithms (in the number field case) or the degrees (in the function field scenario) of two fundamental units and of any one set of their
conjugates, and R is essentially the absolute value of the determinant of these four quantities. R is another invariant of K (once again depending on the transcendental element t in a function field extension). In
the function field case, R is equal to the quotient h/h' up to a small constant
(and easily computable) factor.
Why all this?
The above discussion shows that one way to compute the class number h (which, remember, is just the order of the group of k-rational points on the Jacobian of K) is to determine the ideal class number h' and the regulator R. The advantage of this method is that the computation of these two quantities in number fields has been studied in considerable detail and is quite well understood. Several of these techniques have already been
successfully adapted to work in certain function fields (particularly fields of small degree), so this seems like a promising approach.
Cryptology is the combined study of cryptography and cryptanalysis. Cryptography provides secure communication across insecure channels, while cryptanalysis investigates how secure these communications are, usually by exploring ways of breaking into them. My interest is in those cryptographic systems whose design is based on number theoretic concepts. Typically, the security of such a scheme is based on a mathematical problem that is known (or at least widely believed) to be very difficult to solve; the idea being that an adversary would have to solve an instance of this very hard problem in order to break the
system.
Public Key Systems
In a conventional or single-key system, such as the Data Encryption Stadard (DES) or the Advanced Encryption Standard (AES), any two communicants use the same secret key, which needs to be transmitted to both parties prior to communication. Public key systems eliminate the need for key transfer by assigning each user a publicly known encryption key (so anyone can send secret messages to the user) and a decryption key that is only known to that user (so only he/she is able to decipher those messages).
The most widely used public key system is RSA, named after its designers R. Rivest, A. Shamir, and L. Adleman. Its security is based on the very difficult problem of factoring a large integer into its prime factors. Unfortunately, it is unknown whether an adversary must really factor this large number in order to illegitimately read secret traffic or even obtain the secret decryption key. So far, nobody has found any other way to break RSA. To avoid this uncertainty, my coauthors and I designed several provably secure public key systems. These schemes are somewhat slower and more complicated than RSA (although the complications can be hidden from the user), but their security can be proven to be equivalent to the problem of factoring in the sense that an adversary can illegitimately decipher secret messages quickly if and only if he/she can factor large numbers just as quickly.
Key Exchange Protocols
Another solution to the problem of secret key transfer arising in single-key crytosystems is given by key exchange protocols. Here, two communicants conduct a sequence of information transfers across a possibly insecure channel. At the end of their conversation, both are in possession of a common secret key, but an eavesdropper is unable to derive that key.
The most well known key exchange protocol was developed by W. Diffie and M. Hellman and is
based on the discrete logarithm problem in finite fields. In collaboration with
several other researchers, I developed key transfer protocols whose security is based on finding the distance of a reduced principal ideal in a real quadratic number field or function field. Again, these schemes are somewhat slower and more complex than the original Diffie-Hellman protocol, but they are likely more secure in that the underlying problem of distance computing is (according to our current state of knowledge) more difficult than the discrete logarithm problem for finite fields.
Digital Signatures
These are the electronic equivalent of ordinary hand-written signatures and satisfy the same requirements of authentication and validation. Many public key systems, including RSA and our provably secure schemes, can be used to generate digital signatures. I also designed a digital
signature system whose security relies once again on the difficulty of computing distances of reduced ideals in quadratic function fields.
Renate Scheidler's
home page