4
$\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$
1
  • $\begingroup$ This is a pure math question with no effort. If you now $m$ everything easy. Alos, see Rabin Cryptosystem. $\endgroup$
    – kelalaka
    Aug 20, 2019 at 9:33

2 Answers 2

4
$\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$
6
  • 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, 2019 at 10:40
  • $\begingroup$ @LeoDucas Yes, you're right. Thanks for pointing that out. I edited. $\endgroup$
    – Snoop Catt
    Aug 21, 2019 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, 2019 at 2:50
  • $\begingroup$ 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? $\endgroup$
    – Ray James
    Sep 24, 2019 at 3:20
  • $\begingroup$ @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. $\endgroup$
    – Snoop Catt
    Sep 24, 2019 at 6:14
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$
1
  • $\begingroup$ Thanks, I am trying to understand Berlekamp algorithm and discrete logarithms. $\endgroup$
    – Ray James
    Sep 3, 2019 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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