Revision #2 Authors: Li, Chen, Fu, Ye Bin

Accepted on: 21st April 2008 00:00

Downloads: 1824

Keywords:

It is well known that every finite Abelian group $G$ can be

represented

as a direct product of cyclic groups: $G=G_1\circ G_2\circ\cdots \circ

G_t$, where

each $G_i$ is a cyclic group of size $p^j$ for some prime $p$ and integer

$j\ge 1$.

If $a_i$ is the generator of the cyclic group of $G_i$, $i=1,2,\cdots, t$,

then the

elements a_1,a_2,\cdots, a_t$ are called a basis of $G$. In this paper,

we first

obtain an $O(n)$-time deterministic algorithm for computing the basis of

an Abelian

group with $n$ elements. The existing algorithms need $O(n^2)$ time by

Chen and

$O(n^{1.5})$ time by Buchmann and Schmidt.

We then derive an $O((\sum_{i=1}^k _i^{n_i/2}n_i^2)(\log n)\log\log

n)$-time randomized

algorithm to compute the basis of Abelian group $G$ of size $n$ with

factorization

$n=p_1^{n_1}\cdots p_t^{n_t}$, which is also a part of the input. It

implies

an $O(n^{1/2}(\log n)^3\log\log n)$-time randomized algorithm to compute

the basis of

an Abelian group $G$ of size $n$. It also implies that if $n$ is an

integer

in $\{1,2, \cdots, m\}-G(m,c)$, then the basis of an Abelian group of size

$n$ can be

computed in $O((\log n)^{{c\over 2}+3}\log\log n)$-time, where $c$ is any

positive constant

and $G(m,c)$ is a subset of the small fraction of integers in $\{1,2,

\cdots, m\}$ with

${|G(m,c)|\over m}=O({1\over (\log m)^{c/2}})$ for every integer $m$.

It is well known that every finite Abelian group $G$ can be

represented as a product of cyclic groups: $G=G_1\times

G_2\times\cdots G_t$, where each $G_i$ is a cyclic group of size

$p^j$ for some prime $p$ and integer $j\ge 1$. If $a_i$ is the

generator of the cyclic group of $G_i$, $i=1,2,\cdots, t$, then the

elements $a_1,a_2,\cdots, a_t$ are the basis of $G$. In this paper,

we first obtain an $O(n)$-time deterministic algorithm for

computing the basis of an Abelian group with $n$ elements. This

improves the previous $O(n^2)$ time algorithm found by

Chen. We then derive an $O((\sum_{i=1}^t p_i^{n_i-1}n_i^2\log p_i)(\log n)(\log\log n))$-time randomized

algorithm to compute the basis of Abelian group $G$ of size $n$ with

factorization $n=p_1^{n_1}\cdots p_k^{n_t}$, which is also a part of

the input. This shows that for a large number of cases, the basis of

a finite Abelian group can be computed in sublinear time. For

example, it implies an $O(n^{1-{1\over d}}(\log n)^3\log\log

n)$-time randomized algorithm to compute the basis of an Abelian

group $G$ of size $n=p_1^{n_1}\cdots p_t^{n_t}$, where $d=\max\{ n_i

| i=1,\cdots, t\}$. It is a sublinear time algorithm if $\max\{ n_i

| i=1,\cdots, t\}$ is bounded by a constant. It also implies that if

$n$ is an integer in $[1,m]-G(m,c)$, then the basis of an Abelian

group of size $n$ can be computed in $O((\log n)^{c+3}\log\log

n)$-time, where $c$ is any positive constant and $G(m,c)$ is a

subset of the small fraction of integers in $[1,m]$ with

${|G(m,c)|\over m}=O({1\over (\log m)^{c/2}})$ for every integer

$m$.