3
$\begingroup$

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 ?

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – LeoDucas Aug 21 at 10:40
  • $\begingroup$ @LeoDucas Yes, you're right. Thanks for pointing that out. I edited. $\endgroup$ – Chipotle Aug 21 at 14:34
  • $\begingroup$ @Chipotle Thanks! I managed to understand what you mean. It opens a new perspective to me. $\endgroup$ – Ray James Sep 3 at 2:50
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, I am trying to understand Berlekamp algorithm and discrete logarithms. $\endgroup$ – Ray James Sep 3 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.