ON SOME COMPUTATIONAL PROBLEMS IN FINITE ABELIAN-GROUPS

We present new algorithms for computing orders of elements, discrete l ogarithms; and structures of finite abelian groups. We estimate the co mputational complexity and storage requirements, and we explicitly det er mine the O-constants and Omega-constants. We implemented the algori thms for class groups of imaginary quadratic orders and present a sele ction of our experimental results. Our algorithms are based on a modif ication of Shanks' baby-step giant-step strategy, and have the advanta ge that their computational complexity and storage requirements are re lative to the actual order, discrete logarithm, or size of the group, rather than relative to an upper bound on the group order.