\section{Algorithms for groups}
The following section is loosely based on the study of algorithms for
groups as in the work of Schoup, Schnorr, Buchmann and others. How
does one specify a group to a computer? First of all the elements of
the group are represented by ``words'' of some fixed length
(bitstrings of a fixed length). Let us denote the set of such words by
$F$. However, since the group does not have order a power of two, not
all such words will be elements of the group. Thus we have a
membership function $\mu:F\to\{0,1\}$ that takes the value $1$ for
elements of the group. We then have the group operations which
usually ``expand'' the word length. In other words we have a superset
$F^2$ containing $F$ which has ``double words'' (words of twice the
size of those in $F$) and the group multiplication operation usually
gives $m:F\times F\to F^2$. There is usually also an inverse
operation $i:F^2\to F^2$ which takes $F$ to itself; more often a
``ratio'' operation $d:F\times F\to F^2$ is provided instead. Finally,
there is a reduction operation $r:F^2\to F$. The actual group
operations are defined by
\begin{eqnarray*}
x \cdot y & = & r(m(x,y)) \\
x \cdot y^{-1} & = & r(d(x,y)) \\
x^{-1} & = & r(i(x,y))
\end{eqnarray*}
This specification should satisfy the condition that these operations,
when restricted to the set $G=\mu^{-1}(1)$ satisfy the axioms for an
abelian group. We will assume that such a collection of operations has
indeed been provided to us as a ``black box''. We will look at
algorithms that study the properties of this group {\em without}
looking into the details of how the maps $\mu$, $m$, $d$ and $r$ are
defined. Some have called this the study of ``generic group
algorithms''.
One way to represent a finite abelian group $G$ and compute its
structure is to write it via generators and relations. Suppose we are
given a collection $g_1$, $g_2$, \dots, $g_r$ of generators of $G$ and
we can find a collection $\rho_1$, $\rho_2$, \dots, $\rho_s$ of
relations of the form
\[ \rho_j = \prod_i g_i^{a_{ij}} \]
If this collection of relations is sufficient, we obtain an exact
sequence
\[ \bbZ^s \by{A} \bbZ^r \by{g} G \to 0 \]
where $A$ is given by the matrix $(a_{ij})$ and $g$ the ``vector'' of
generators of $G$. Such a description reduces the computation of the
{\em abstract} structure of $G$ to matrix manipulations. For example,
by reducing the matrix to echelon form we can exhibit an isomorphism
{\em from} a product of cyclic groups {\em to} the group $G$. However,
it is not so easy(!) to write the inverse of this isomorphism. To do that
one must exhibit a (computable) set-theoretic splitting $G\to\bbZ^r$.
One way to compute such a splitting on an element $g$ of $G$ is to
find enough relations between $g$ and the collection of the $g_i$'s.
It is thus clear that the important problem in the algorithmic
analysis of finite abelian groups is that of finding (sufficiently
many) relations between elements of the group.
There are essentially three classes of ``generic group algorithms''
which can be called the Pollard $\rho$ method, Shanks' Baby Step Giant
Step method and the Pohlig-Hellman factor method. We illustrate these
methods by seeing how they can be used to find a relation between some
given elements $g_1$, $g_2$, \dots, $g_r$ of the group.
\subsection{Pollard's $\rho$}
This method uses the least amount of information about the group and
also uses the least amount of storage. We choose a ``random''
partition of the elements of the group into disjoint sets $S_0$,
$S_1$, \dots, $S_r$ (which are specified by their membership functions
$\mu_i$). We now define a collection of maps as follows. Start with a
``random'' element $x_0$ of the group. Let $v_0=(0,\dots,0)$ be the
origin in the group $\bbZ^r$. We define an iterated map as follows
\[ (x_{i+1},v_{i+1}) = \Phi(x_i,v_i) =
\begin{cases}
(x_i^2,2\cdot v_i) & x_i\in S_0 \\
(g_j\cdot x_i,e_j + v_i) & x_i\in S_j \\
\end{cases}
\]
By the techniques due to Pollard, Brent and Floyd described earlier we
can find an integer $T$ such that $(x_{2T},v_{2T})=(x_T,v_T)$. It
follows that if $v_{2T}-v_T = (a_1,a_2,\dots,a_r)$, then
\[ \prod_i g_i^{a_i} = 1 \]
Some aspects of Brent's method can be used to further ensure that
$v_i$ does not grow too large (since we are only interested in
$v_{2T}-v_{T}$). Assuming that the choice of $S_i$ is ``random''
enough we should be close to a relation of the smallest size in the
sense that $\sum_i a_i$ is the shortest. That is also an estimate of
the number of steps upto a small constant factor.
\subsection{Shanks' Baby step-Giant step}
Now suppose that we know that we are given bounds $L_1$, $L_2$, \dots
$L_r$ with the assurance that there is a relation $\prod_i q_i^{a_i}$
with $0\leq a_i < L_i$. (We will see below how such a collection of
bounds can be constructed inductively given a bound $L$ on the order
of $G$).
Let $h(x)$ be a collision free function for $x\in G$ (for example $h$
is a ``hash function''). Let $(a_1, \dots, a_r)$ be a sequence with
$a_i$ an integer not larger than $n_i=\lceil{\sqrt{L_i}}\rceil$. We
compute the terms
\[
(\prod_i g_i^{a_i}; a_1, \dots, a_r; h(\prod_i g_i^{a_i}))
\]
for all $a_i$ in this range and store them sorted according the final
entry. This allows us to perform a search operation in a time
proportional to the logarithm of the length of the list. Now, for each
sequence $(b_1, \dots, b_r)$ where $b_i$ is an integer not larger
than $\lfloor{\sqrt{L_i}}\rfloor+1$, we compute the expression
$h(\prod_i (g_i^{-n_i})^{b_i})$ and try to find it in the given sorted
list. Clearly, if it is found then we have a relation of the form
\[ \prod_i g_i^{a_i+n_i b_i} = 1 \]
By the given assertion on $L_i$, such relation will eventually be
found.
One way to approach this algorithm given only a bound on the size of
the group $G$ is to go inductively. First find a relation involving
$g_1$ alone (in other words find the order of $g_1$) by using $L_1=L$.
For the remainder of the algorithm we put $L_1=o(g_1)$ as found in
this step. In the second iteration we work with $g_1$ and $g_2$ with
$L_2=L/L_1$. Iteratively, we would have computed $L_i$ which is the
order of $g_i$ in the group $G/$. We now work with
$g_1$, \dots, $g_{i+1}$ and take $L_{i+1}=L/(\prod_{k=1}^i L_i)$.
Using the above algorithm we obtain the order of $g_{i+1}$ in the
group $G/$. For the remainder of the iterations we take
$L_{i+1}$ to be this order. Thus, at the end we would have found a
{\em minimal} relation among the $g_i$'s rather than just one
relation.
\subsection{Pohlig-Helman factor method}
We now assume that we are given the factorisation of the order $n$ of
the group $G$ and we want to find another relation which is smaller
than the obvious relation $(n,\dots,n)$.
Let $p$ be a prime factor of $n$ and $k$ such that $p^k|n$ while
$p^{k+1}\not|n$. Replacing $g_i$ by $g_i^{n/p^k}$, we have effectively
replaced the given problem to the case of $G(p)$, the $p$-adic part of
$G$. By the Chinese Remainder Theorem these solutions can later be
combined. Thus we may assume that the order of $G$ is a power $p^k$ of
a prime $p$.
In the case when $k=1$ we can apply the Baby step-Giant step method to
find a relation as above. When $k>1$, we inductively find a relation
$(b_1,\dots,b_r)$ between the elements $g_i^p$ which lie in the group
$G^p$ which has order $p^j$ for some $j$. This probabilistically determines
the order of $G$ as the product of the $n_i$.
Given $h$ and $g$ in $G$ and the fact that $h$ is a power of $g$ we
determine this power (the Discrete Log problem) by finding
a minimal relation between $g$ and $h$.
\subsection{Applicability and efficiency}
The fundamental theorem for finite abelian groups states that every
abelian group is isomorphic to product of cyclic groups. We have seen
that the all-pervading question in algorithmic abelian group theory is
``To what extent can we (efficiently) compute this isomorphism and its
inverse?'' Because of the efficiency aspect it is important to count
the number of steps and the amount of storage that our algorithms
require. In such measurement numbers of the size of the cardinality of
$F$ are considered ``large'', numbers of the size of the number of
bits in the {\em elements} of $F$ are considered ``reasonable'' and
numbers of the size of the logarithm of the latter number are
considered ``small'' or insignificant.
One can show that the expected running time of the algorithms
described above is of the same order as the bounds available. Since
these bounds are crudely measured as the order of the group $G$ this
makes the algorithms ``slow''. However, in a given case where not
enough information is available or it is suspected that the elements
$g_i$ generate a much smaller group one can start with artificially
chosen small bounds and run the algorithms; if the assumptions (on the
``real'' bounds) are valid these will run to completion.
\subsection{Index calculus}
Another useful tool goes by the name ``Index Calculus''. Suppose that
we are given a set of generators $g_1$, \dots, $g_r$ of $G$ and {\em
another} ``black-box'' which computes a function $A:G\times
R\to\bbZ^r$; here $R$ is used to denote random input. The property of
$A$ is that given $(g,k)$ (with $k$ random) the output is an $r$-tuple
$(a_1,\dots,a_r)$, such that with probability greater than
$1-(1/2)^{r+t}$ (for some small integer $t$) we have the relation
\[ g^k = \prod_i g_i^{a_i} \]
(Note that one can quickly check whether this is indeed true). We can
use such a black-box $A$ to give a probabilistic solution to the group
structure problem. By running the algorithm at most $r+t$ times we
will (with high probability) obtain sufficiently many relations to
write $g$ in terms of the elements $g_i$. Thus we can use this to
construct a probabilistic algorithm that splits the map $\bbZ^r\to G$
as required.
Since this algorithm makes use of one additional ``black-box'' it is
not a ``generic group algorithm''.
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "main"
%%% End: