# How can we effectively compute the sqrt of some element in the group?

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 ?

• This is a pure math question with no effort. If you now $m$ everything easy. Alos, see Rabin Cryptosystem. – kelalaka Aug 20 '19 at 9:33

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.

• Maybe you did it as a simplification, but your decomposition as a product of groups does not always work. Example : $\mathbb Z/2^k\mathbb Z$ is not isomorphic to $(\mathbb Z/2\mathbb Z)^k$. – LeoDucas Aug 21 '19 at 10:40
• @LeoDucas Yes, you're right. Thanks for pointing that out. I edited. – Chipotle Aug 21 '19 at 14:34
• @Chipotle Thanks! I managed to understand what you mean. It opens a new perspective to me. – Ray James Sep 3 '19 at 2:50
• if q is an odd prime number, and g is co-prime with q, and the group is a multiplicative mod p group, then g the power (q-1)/2 also applies? – Ray James Sep 24 '19 at 3:20
• @RayJames If we are talking about an abstract group, there is no meaning to g co-prime to q. Perhaps you meant the order of g? and anyway, any number is co-prime to any prime number. – Chipotle Sep 24 '19 at 6:14

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.

• Thanks, I am trying to understand Berlekamp algorithm and discrete logarithms. – Ray James Sep 3 '19 at 2:52