# In a group, is it hard to calculate the base $g$ given $g^a$ and $a$?

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$?

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.

• in case of RSA, it's know that in general there is no generator, $(\mathbb{Z}/n.\mathbb{Z})^*$ is not a cyclic group. – Robert NACIRI Feb 8 '15 at 11:48
• 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. – Aria Feb 8 '15 at 12:30
• Even if the "whole group" is not cyclic, you are actually working in the cyclic subgroup generated by $g$, so the distinction is irrelevant. – fkraiem Feb 8 '15 at 17:50
• Also, of course $a^{-1}\bmod m$ does not always exist. – fkraiem Feb 8 '15 at 17:53
• 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 . – tylo Feb 11 '15 at 15:53

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.

• @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) – poncho Feb 8 '15 at 18:07
• @poncho Not sure why you are telling me this, of course I know it. This should be in an answer. – fkraiem Feb 8 '15 at 18:15
• @RobertNACIRI you are wrong, please read carefully the discussion. – Fractalice Feb 12 '15 at 18:07
• @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. – Robert NACIRI Feb 14 '15 at 0:19
• @Hyperflame: Solving $X^r - a = 0$ ? Ah! That's the QUESTION. I edited my previous answer. – Robert NACIRI Feb 16 '15 at 22:17