5
$\begingroup$

Discrete logarithm, that is: calculate $a$ given $g$ and $g^a$, is assumed to be a hard problem in some groups.

Is it also hard to calculate $g$ given $g^a$ and $a$?

$\endgroup$
12
$\begingroup$

It depends. If the order $m$ of $g$'s group is known and $a$ has an inverse modulo $m$ (which is the case if and only if $a$ is coprime to $m$), then it is easy: Calculate the inverse $b:=a^{-1}\bmod m$ (for instance, using the Euclidean algorithm), and compute the power $(g^a)^b$. By Lagrange's theorem, this equals $g$.

However, there are cases for which it's hard: for example, when $n=pq$ is the product of two unknown primes $p,q$ and $g\in\mathbb Z/n\mathbb Z$, then the task is equivalent to decrypting the RSA ciphertext $g^a$ with respect to the public key $(n,a)$, which is generally assumed to be hard.

$\endgroup$
  • $\begingroup$ in case of RSA, it's know that in general there is no generator, $(\mathbb{Z}/n.\mathbb{Z})^*$ is not a cyclic group. $\endgroup$ – Robert NACIRI Feb 8 '15 at 11:48
  • $\begingroup$ is it mean that in cyclic group it can be calculated by finding inverse of a, but in general like RSA encryption it is not true. $\endgroup$ – Aria Feb 8 '15 at 12:30
  • 2
    $\begingroup$ Even if the "whole group" is not cyclic, you are actually working in the cyclic subgroup generated by $g$, so the distinction is irrelevant. $\endgroup$ – fkraiem Feb 8 '15 at 17:50
  • 1
    $\begingroup$ Also, of course $a^{-1}\bmod m$ does not always exist. $\endgroup$ – fkraiem Feb 8 '15 at 17:53
  • 1
    $\begingroup$ The question about "a generator" is misleading, because it is wrong terminology. In general, there is a generating set and its elements are called generators - no signular. Elements can generate a group. And along this line a single element can generate a (sub)group, which implies that the set contains one element and the generated group is cyclic. But that doesn't mean there is a generator . $\endgroup$ – tylo Feb 11 '15 at 15:53
-1
$\begingroup$

If you know $a$, you also know $\frac{1}{a}$ then $g=(g^a)^{\frac{1}{a}}$.

Now, answering the question for solving $X^r - a = 0$, when $r \mid (p-1)$. If my analysis is correct, if $r\mid (p-1)$, the square root algorithm can easily be adapted depending on the form of prime $p$.

  • If $p=2rq + 2r -1$, this is a deterministic case: let $$y_0=a^{\frac{p+1}{2 \times r}} \quad \Longrightarrow \quad y_0^r=\left(\frac{a}{p}\right) \times a$$

Then if $a \in QR(p)$, a particular solution is $y_0=a^{\frac{p+1}{2 \times r}}$ otherwise there is no solution!

  • If $p$ in other form: a particular solution can be calculated by a probabilistic algorithm, and is too complicated to expose here.

By the way, when a particular solution is calculated, all the $r$ roots are conjugate to each other, and are of the form $y_i =\mu_i \times y_0 \;\cdots \; \mu_i$ is one of the $r$ $r$th roots of Unity.

I emphasize that the cryptographic protocol should appropriately specify the conditions for the uniqueness in the solution of a given protocol, and in this case, we can use abusive notation like $\frac{1}{a}$.

And there should always be a method for selecting the appropriate solution. The algorithm I mentioned here can be proved with the background given in Henri Cohen's book, a former professor in the Maths Dpt of BDX.

$\endgroup$
  • 1
    $\begingroup$ @fkraiem: if $1/a$ doesn't exist (that is, if $a$ and the group order $q$ are not relatively prime), then $g$ won't be uniquely determinable (if one exists, there might not); however it wouldn't be difficult to find a $g$ that does work (assuming, of course, that such a $g$ exists) $\endgroup$ – poncho Feb 8 '15 at 18:07
  • 1
    $\begingroup$ @poncho Not sure why you are telling me this, of course I know it. This should be in an answer. $\endgroup$ – fkraiem Feb 8 '15 at 18:15
  • 1
    $\begingroup$ @RobertNACIRI you are wrong, please read carefully the discussion. $\endgroup$ – Hyperflame Feb 12 '15 at 18:07
  • 1
    $\begingroup$ @Hyperflame: Suite Take a look over the web to this system and the use of Blum integers to learn how the system work. 4- You ask how to extract r-root if r | p-1. If you know Galois theory, you can transform the problem to extract the r-root of Unity, and by multiplying with on particular solution, you obtain all the others. if a is a r-power, x^r-a=0 has r-solution is a finite field, and all the solutions are conjugate with each 5- If you want to solve over the ring $(Z/p_1....p_k.Z)^*$, they are $r^k$ solutions. Hope this help your understanding. $\endgroup$ – Robert NACIRI Feb 14 '15 at 0:19
  • 1
    $\begingroup$ @Hyperflame: Solving $X^r - a = 0$ ? Ah! That's the QUESTION. I edited my previous answer. $\endgroup$ – Robert NACIRI Feb 16 '15 at 22:17

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.