Mdthbs

I only know one way, if this group is a cyclic group, and we know the element can be expressed in $g^m$, then $g^{(m/2)}$ is the answer.

• Another question, if $m$ is an odd number, can we be sure there is no answer?




• Is it possible to find another generator $g_1$ and an even number $k$ that satisfy the element = $g_1^k$?

If we don't know whether or not the group is cyclic group, the complexity to find the sqrt or to confirm such an answer not exists is as difficult as DLP ?

TL;DR: Efficient algorithm only exist in specific cases. The problem, in its full generality (finite abelian groups) is equivalent to the integer factorization problem.

How can we effectively compute the square root of an element in a group?

One case where we can compute a square root is when the group order is known and it is odd.
Any element $g$ in a group has the following property: if $q$ is the order of the group, then $g^q=1$. This is due to Lagrage's Theorem. Equivalently, $g^{q+1}=g$. If $q$ is odd then $frac{q+1}{2}$ is an integer, hence we can compute $h:= g^{frac{q+1}{2}}$, which is a square root of $g$.

Another case is the following: Assume $G$ is isomorphic to the direct product group of $k$ copies of the group of order 2 and a group of order odd $q$:
$$
G simeq mathbb{G}_q times prod_{i=1}^k mathbb{Z}_2
$$
where $mathbb{G}_q$ denotes a group of order $q$ and $mathbb{Z}_2$ the group of order 2. Also, importantly, assume you know how to compute this isomorphism.

In the group of order 2, the non-unit element is its own inverse, hence it has no square root. This implies the following: Let $g in G$. Apply the isomorphism to get the representation of $g$ as an element in the direct product above: $g = (g', g_1, ..., g_k)$, where $g' in mathbb{G}_q$ and $g_i$ is in the $i$'th $mathbb{Z}_2$. If there exists $i$ such that $g_i$ is not the unit element, then $g$ does not have a square root.

On the other hand, if $g_i$ is the unit element in all copies of $mathbb{G}_2$, then the problem reduces to the case of a group of odd order: you just raise $g$ to the power of $frac{q+1}{2}$.

Another question, if $m$ is an odd number, can we be sure there is no answer?

No. The above explains this too. Actually, for the above, you don't need to know $m$ (which is typically the case).

Is it possible to find another generator $g_1$ and an even number $k$ that satisfy the element is equal to $g^k$?

The above addresses this too, since it fully describes the set of squares in the group.

EDIT:

In "Oded Goldreich, Computational complexity: a conceptual perspective" it is shown that finding square roots modulo composite numbers is a computational problem equivalent to integer factorization. Hence, don't expect any "general purpose" algorithm, only algorithm for special cases. One such case is the multiplicative group of invertible element in a field of prime size $p$ - called Tonelli-Shanks.

In a generic group, I don't know if it exists really a generic algorithm to solve your problem, but if you group is also a field ($mathbb{Z}_p$ with $p$ a prime number for example), then you can use the Berlekamp algorithm to factorize $X^2 -x$ where $x$ is your element.

I made an error, I've deleted the wrong part.