C/C++ C++ function to tell whether a group is cyclic

[Jamin2112]

Is there anything wrong with my logic and is there any way to further optimize this potentially long-running function? I've put a lot of comments to explain what's going on.

template <typename ObType, typename BinaryFunction>
bool isCyclic(const std::set<ObType> & G, BinaryFunction & op, ObType & g)
{
	/*
	isCyclic returns true or false depending on whether the group G
	is an cyclic group, that is, whether it can be generated from
	one its elements. Formally, G is cyclic if there exists an 
	element g in G such that, for all elements h in g, 
	h = g^n for some n. 
	*/
	bool foundGenerator = false;
	size_t maxN = G.size();
	/*
	Guaranteed that for each x in G, x^(maxN + 1) will be in the set
	{x, x^2, ..., x^maxN}. That is the meaning of maxN. 
	*/
	
	for (typename std::set<ObType>::const_iterator it(G.cbegin()), offend(G.cend()); it != offend && !foundGenerator; ++it)
	{
		ObType e0 = *it; 
		ObType e = e0;
		std::set<ObType> powSet = {e};
		size_t k = 2;
		while (k <= maxN)
		{
			e = op(e, e0); /* Sets e equal to e^i */
			if (powSet.count(e) == 0)
				powSet.insert(e);
			else
				break;
			/* Why the break statement? 
			   If e is already in powSet, then we've found a cycle but 
			   powSet != G; therefore e cannot generate G.
			*/
			++k;
		}
		if (k == maxN) /* true iff (powSet == G) */
		{
			foundGenerator = true;
			g = e;
		}
	}
	return foundGenerator;
}

 

[jbunniii]

A couple of observations:

1. Your algorithm could be more efficient. If $e$ does not generate $G$, then no power of $e$ can generate $G$ either. Proof: if $\langle e\rangle$ is the subgroup generated by $e$, then $e^n \in \langle e \rangle$ and so $\langle e^n \rangle \subset \langle e \rangle$. So you don't have to test all of the elements.

2. Why don't you break out of the for loop when you set foundGenerator = true? [edit I just noticed the !foundGenerator condition on the for loop - I hadn't scrolled far enough to the right to notice it at first. So disregard this observation.]

I haven't checked your logic carefully, so I don't claim that these are the only problems.

 

[jbunniii]

Here is another optimization. Let $|G|$ denote the size (order) of $G$. Then for any element, $|\langle e \rangle|$ must be a divisor of $|G|$. So, in order to determine whether $e$ is a generator, you just need to check $e^n$ for each divisor $n$ of $|G|$. So let $n$ be the smallest divisor of $|G|$ such that $e^n$ equals the identity, or equivalently, $e^{n+1} = e$. There are only two possibilities:

1. $n$ is a proper divisor of $|G|$, in which case $e$ does not generate $G$

2. $n = |G|$, in which case $e$ generates $G$

 

[jbunniii]

[edited previous post for clarity]

 

[rcgldr]

just need to check $e^n$ for each divisor $n$ of $|G|$.

Isn't there a potential issue in the case $e^{(n/k)}$ % G == 1, where k could be 2, 3, ... ? I don't know if there is a fast way to determine the smallest m such that $e^m$ % G == 1.

Also, is this potential cyclic field based on a prime number, a Galios field, a Galios binary field, or something else?

 

[jbunniii]

Isn't there a potential issue in the case $e^{(n/k)}$ % G == 1, where k could be 2, 3, ... ? I don't know if there is a fast way to determine the smallest n such that $e^n$ % G == 1.

I'm not sure what you mean with the notation $e^{(n/k)}$ % G == 1. In general, a group only has one operation, multiplication. (Exponentiation is just repeated multiplication.) What do you mean by the % operation?

In any case, he doesn't need to find the smallest positive $n$ such that $e^n = 1$, he just needs to determine whether there are any such $n$ which are smaller than (hence strict divisors of) $|G|$. This is true if and only if the element is NOT a generator. A brute force way to do this would be (pardon my pseudocode):

isGenerator = true; // until proven otherwise
for (n = 1; n <= N/2; n++) // N = |G|; we only need to loop to N/2 since this is the largest possible strict divisor of N
{
    if (n is not a divisor of N)
    {
        continue;
    }
    if (e^n == 1)
    {
        isGenerator = false;
        break;
    }
}

[edit] OK, I think I see your point: it might be more work to check "if (n is not a divisor of N)" than simply to check "if (e^n == 1)" for every n, in which case it might actually be faster without the first "if" block.

Also, is this potential cyclic field based on a normal prime number integer, or Galios prime polynomial, or something else?

I've been assuming that it's just an arbitrary finite group, and that the OP has a C++ class which "implements" the group, i.e. a finite set and a binary operation on the set which obey the group axioms. Jamin - is that correct?

 

[rcgldr]

It appears that the goal here is to find at least a muliplicative cyclic group or possibly a finite field where addition, multiplication and their inverses work with a finite set of elements. I did some testing with a binary Galios field composed of 8 bit elements modulo the thirty possible 9 bit "prime" polynomials. A generator e raised to m = $2^8$ - 1 = 255 results in $e^m$ % G == 1. The largest value I could get for m for a non-generator e such that $e^m$ % G == 1, was m = 85 = 255/3. So in the case of binary fields, jbunniii's for loop might be able to stop at n <= N/3, and n <= N/2 should be safe for most types of fields.

 

[Jamin2112]

A couple of observations:

1. Your algorithm could be more efficient. If $e$ does not generate $G$, then no power of $e$ can generate $G$ either. Proof: if $\langle e\rangle$ is the subgroup generated by $e$, then $e^n \in \langle e \rangle$ and so $\langle e^n \rangle \subset \langle e \rangle$. So you don't have to test all of the elements.

Updated it to incorporate that:

template <typename ObType, typename BinaryFunction>
bool GroupTheorizer::isCyclic(std::set<ObType> G, BinaryFunction & op, ObType & g) const
{
	/*
	isCyclic returns true or false depending on whether the group G
	is an cyclic group, that is, whether it can be generated from
	one its elements. Formally, G is cyclic if there exists an 
	element g in G such that, for all elements h in g, 
	h = g^n for some n. 
	*/
	bool foundGenerator = false;
	size_t maxN = G.size();
	/*
	Guaranteed that for each x in G, x^(maxN + 1) will be in the set
	{x, x^2, ..., x^maxN}. That is the meaning of maxN. 
	*/
	for (typename std::set<ObType>::iterator it(G.begin()); it != G.cend() && !foundGenerator; ++it)
	{
		ObType e0 = *it; 
		ObType e = e0;
		std::set<ObType> powSet = {e};
		size_t k = 2;
		while (k <= maxN)
		{
			e = op(e, e0); /* Sets e equal to e^i */
			if (powSet.count(e) == 0)
				powSet.insert(e);
			else
				break;
			/* Why the break statement? 
			   If e is already in powSet, then we've found a cycle but 
			   powSet != G; therefore e cannot generate G.
			*/
			++k;
		}
		if (k == maxN) /* true iff (powSet == G) */
		{
			foundGenerator = true;
			g = e;
		}
		else
		{
			for (std::set<ObType>::iterator i(powSet.begin()), j(powSet.end()); i != j; ++i)
				G.erase(*i)
				/* Why? 
				   powSet is the set of all powers of e0. If e0 does not generate G, then neither
				   does any of its powers. 
				*/
		}
	}
	return foundGenerator;
}

 

[rcgldr]

For most fields, even if e is not a generator, it should cycle through a sub-set of the elements. The inner loop could be changed to something like this:

        e = e0
        for(k = 2; k <= maxN; ++k)
        {
            e = op(e, e0);   // Sets e equal to e^k
            if(e == e0)      // break if e cycled back to e0
                break;
        }
        if(k == (maxN-1))    // maxN-1 == # of non-zero elements in the group
        {
            // found a generator
        }