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 congruent to G(1) x G(2) x ... x G(t), where each G(i) is a cyclic group of order p(j) for some prime p and integer j >= 1. If a(i) generates the cyclic group of G(j), i = 1,2, ..., t, then the elements a(1), a(2), ..., a(t) are called a basis of G. We show a randomized algorithm such that given a set of generators M = {x(1), ..., x(k)} for an abelian group G and the prime factorization of order ord(x(i)) (i = 1, ..., k), it computes a basis of G in O(vertical bar M vertical bar(log n)(2) + Sigma(t)(i=1) n(i)p(j)(nj/2)) time, where n = vertical bar G vertical bar has prime factorization p(1)(n1)p(2)(n2) ... p(t)(nt) (which is not a part of input). This generalizes Buchmann and Schmidt's algorithm that takes O(vertical bar M vertical bar root vertical bar G vertical bar) 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. (C) 2010 Elsevier B.V. All rights reserved.
basis of abelian group abelian group randomization decomposition