Structure computation and discrete logarithms in finite abelian $p$-groups

We present a generic algorithm for computing discrete logarithms in a finite abelian $p$-group $H$, improving the Pohlig-Hellman algorithm and its generalization to noncyclic groups by Teske. We then give a direct method to compute a basis for $H$ without using a relation matrix. The problem of computing a basis for some or all of the Sylow $p$-subgroups of an arbitrary finite abelian group $G$ is addressed, yielding a Monte Carlo algorithm to compute the structure of $G$ using $O(\vert G\vert^{1/2})$ group operations. These results also improve generic algorithms for extracting $p$th roots in $G$.