Is there any lower bound for basis computation in finite Abelian groups?

Question

Victor Shoup in this paper has given a lower bound for discrete logarithm. The algorithms that I have come across use discrete logarithms (extended discrete logarithms) to compute a basis for a finite Abelian group. For instance, in this paper Andrew Sutherland gives a probabilistic algorithm that computes a basis of finite abelian group $G$ using an expected $O(|G|^{1/2})$ group operations. Is it known if there exists a lower bound on basis computation or if the computation of basis is in general tougher than computing discrete logarithms for generic groups?