One common way of constructing public-key cryptographic systems is to
utilize the problem of finding a discrete logarithm in some abelian
group. Groups that have been utilized for this purpose include
$\F_{q}^{*}$ in the Massey-Omura and ElGamal cryptosystems and the
group of points on an elliptic curve in elliptic curve
cryptosystems. (See~\cite{Koblitz} for background, for example.)
Another possibility which has been proposed by Buchmann and Williams
(see, e.g., \cite{BW90}) is to use the group of ideal classes in a
number field. In order to make sure that the discrete logarithm
problem is computationally hard, one needs to know something about the
structure of the group involved, e.g. that it is divisible by a large
prime. One situation in which it is easy to show this is in the case
of the class group of $\Q(\zeta_{p})$; according to a well-known
theorem of Kummer, $p$ divides the order of the class group of
$\Q(\zeta_{p})$ if and only if $p$ divides the numerator of a
Bernoulli number $B_{m}$ for some even $m$ such that $2 \leq m \leq
p-3$. Such primes are called irregular; the others are called
regular.
We extend the concept of regular and irregular primes to the setting
of arbitrary totally real number fields $k_{0}$, using the values of
the zeta function $\zeta_{k_{0}}$ at negative integers as our ``higher
Bernoulli numbers''. In this setting the author proved in his
thesis~(\cite{dissert}), building on work of Greenberg and Kudo, that
under a certain technical condition Kummer's criterion can be extended
to give information about whether $p$ divides the class group of
$k_{0}(\zeta_{p})$. Thus we are interested in the feasibility of
finding these analogues of irregular primes, since their associated
class groups may be especially suitable for cryptography.
In the case where $k_{0}$ is a real quadratic field, Siegel,
in~\cite{Siegel68}, presented two formulas for calculating these
zeta-values: one using entirely elementary methods and one which is
derived from the theory of modular forms. (See also~\cite{Zagier}
and~\cite{Cohen76} for a discussion of these formulas. The author
would like to thank Henri Cohen for suggesting an analysis of the
second formula.) We will briefly discuss several algorithms based on
these formulas and compare the running time involved in using them to
determine the index of $k_{0}$-irregularity of a prime number. (The
author has already discussed one of these algorithms
in~\cite{Holden98}.)