I'm trying to write a computer program to determine the primary cyclic structure of $\mathbb{Z}_n^*$. However the standard proof requires a very computational intensive step.
More explicitly the standard proof algorithm has 2 main parts:
- Decompose G into a direct sum of it's sylow p-subgroups
- Decompose each sylow p-subgroup into a direct sum of cylic p-groups
The first step is a very straightfoward calculation, however in most standard proofs of the abelian group structure theorem the 2nd step goes like this:
$$\text{Let} \ G \ \text{be a finite abelian p-group and choose} \ x \in G \text{ with maximal order}$$ $$\text{Then G = } \langle x \rangle \oplus H$$
where this $H$ subgroup is determined by a recursive step.
Translating this into an concrete algorithm, this means that i need to find a maximal order element in $G$ and then a maximal order element whose generated group dosen't intersect the first and so on recursively picking the maximal order element that dosen't intersect the direct sum of the previous.
This seems terrible. I don't think there's any way of doing this that isn't just checking the order of every element individually and comparing them one by one to find a maximal element, and then manually checking for intersections of their cyclic groups untill we're done.
I can think of a few simplifications: for exemple if I actually do check every element's order and they're all equal to $p$ then $$G = \bigoplus_{i = 0}^{n-1} \mathbb{Z}_p \quad (|G| = p^n)$$
Also, of course, if there is an element with order $p^n$ then $G = \mathbb{Z}_{p^n}$ is cyclic.
My question is: is there a good (better) algorithm for finding the cyclic decomposition of abelian p-groups (p-primary groups) or how can the standard proof algorithm be simplified as to be less computational intensive?