Linear and sublinear time algorithms for the basis of abelian groups

It is well known that every finite abelian group G can be represented as a direct product of cyclic groups: G≅G1×G2×⋯×Gt, where each Gi is a cyclic group of order pj for some prime p and integer j≥1. If ai generates the cyclic group of Gi, i=1,2,…,t, then the elements a1,a2,…,at are called a basis of G. We show a randomized algorithm such that given a set of generators M={x1,…,xk} for an abelian group G and the prime factorization of order , it computes a basis of G in time, where n=|G| has prime factorization (which is not a part of input). This generalizes Buchmann and Schmidt’s algorithm that takes time. In another model, all elements in an abelian group are put into a list as a part of input. We obtain an O(n) time deterministic algorithm and a sublinear time randomized algorithm for computing a basis of an abelian group.