# Given $g$, $b$, $g^{ab}$, is finding $g^a$ a hard problem?

As in the title, given $g$, $g^{ab}$ are big elements in a prime group $Z_p$ and $b$ in prime group $Z_r$ ($p > r$, $g$ is one generator of $Z_p$). $a$ is unknown and also in $Z_r$, is finding $g^a$ a hard problem?

update $a$, $b$ and $ab$ are group elements of $Z_r$..

• By "in group $\mathbb Z_r$" are you meaning $a$ and $b$ are in $\mathbb N$ and less than $r$, or that $a\cdot b$ is computed in that group? – fgrieu Jul 17 '14 at 13:45
• @fgrieu $a$ and $b$ are group elements of $Z_r$, and $a.b$ should be computed in that group. – Loi.Luu Jul 17 '14 at 13:59
• @fgrieu its just a mathematics group, am I having something confusing here? en.wikipedia.org/wiki/Group_(mathematics) – Loi.Luu Jul 17 '14 at 14:48
• Probably $r$ is the order of $g$ in $\mathbf{Z}_p^*$, otherwise it makes no sense that the exponents should be in $\mathbf{Z}_r$... – fkraiem Jul 17 '14 at 14:49
• @Loi.Luu I'm sorry but no, unless $r$ is the order of $g$ in $\mathbf{Z}_p^*$ or a multiple thereof, the exponents being in $\mathbf{Z}_r$ makes no sense, because you could have $a = b$ in $\mathbf{Z}_r$ but $g^a \ne g^b$ in $\mathbf{Z}_p^*$. – fkraiem Jul 17 '14 at 14:57

The question as currently worded, and considering comments by its author, would boil down to: is it a hard problem finding $g^a\bmod p$, given

• large prime $p$
• large integer $g$ less than $p$ that is a generator of $\mathbb Z_p$ [see note 1]
• prime $r$ less than $p$
• knowledge that unknown $a$ is a positive integer less than $r$
• positive integer $b$ less than $r$
• $g^{a\cdot b\bmod r}\bmod p$ [see note 2]

Note 1: We can safely assume I have assumed this means $g$ is a generator of the multiplicative group $\mathbb Z_p^*$ of $\mathbb Z_p$; that is, the application $x\to g^x\bmod p$ is a mapping over the set of positive integers less than $p$; this can be efficiently tested when the factorization of $p-1$ is known, by checking $g^{(p-1)/q}\bmod p\;\ne1$ for every prime $q$ dividing $p-1$.

Note 2: The statement uses the notation $g^{ab}$, with the indication that $g$ is in prime group $\mathbb Z_p$ [which we can safely assume is the multiplicative group $\mathbb Z_p^*$], meaning that element $g^{ab}$ of $\mathbb Z_p$ is given as the integer $g^{ab}\bmod p$; and the indication that $a$ and $b$ are in prime group $\mathbb Z_r$, with comment that $ab$ is computed in $\mathbb Z_r$ [which I similarly assume is the multiplicative group $\mathbb Z_r^*$], and comment suggesting that an element of $\mathbb Z_r$ is assimilated to a non-negative integer less than $r$; hence my interpretation that the given stated as $g^{ab}$ really is $g^{a\cdot b\bmod r}\bmod p$.

We can NOT guess/hope/assume that $g^r\bmod p\;=1$ [including that $r=p-1$, the order of $g$], because that would contradict the givens that $p$ and $r$ are primes [see comment] with $p$ large and larger than $r$, and $g$ is a generator. Thus $g^{a\cdot b}\bmod p$ with $a\cdot b$ obtained by integer multiplication has no reason to be $g^{a\cdot b\bmod r}\bmod p$, and typically is not.

Right now I do not see how to solve that problem in the general case, or even count its solutions. That's far fetched from a justification of my impression that it might be a hard problem for some parameters.

If we knew $g^{a\cdot b}\bmod p$ [rather than $g^{a\cdot b\bmod r}\bmod p$, as I assume we do], we could ignore the given $r$ and often solve the problem by the method outlined in that other answer, since that method works when $\gcd(b,p-1)=1$. Depending on $p$ that might be common, or not; e.g. for the prime $p=$1719620105458406433483340568317543019584575635895742560438771105058321655238562613083979651479555788009994557822024565226932906295208262756822275663694111, $\gcd(b,p-1)=1$ when $b$ has no divisor less than 383, and that occurs for few $b$.

Update: it is now asked in comment if we could compute $c=b^{−1}$ in $\mathbb Z_r$, and then compute $(g^{ab})^c$ to get $g^a$. This suggests something is wrong in my interpretation of the statement above, despite the answer being accepted.

That method won't work for most primes $r$ less than $p$ and most pairs $(a,b)$, no matter if $ab$ is computed in $\mathbb Z_r$ or in $\mathbb N$.

That does work if $g^r\bmod p\;=1$ and $\gcd(b,r)=1$, for either way to compute $ab$ (which become equivalent). However, if we trust the given that $g$ is a generator, the only $r$ less than $p$ with $g^r\bmod p\;=1$ is $r=p-1$. And [using that $p$ is huge], such $r=p-1$ is not prime, contrary to $r$ prime suggested by the statement and confirmed in comment. Also that won't works with $b$ even, or otherwise not co-prime with $p-1$.

Illustrations with small values $p=23$, $g=19$ [which matches the condition that $g$ is a generator], $r=17$ unless otherwise stated, $a=8$, and $b=6$ :

• with multiplication in $\mathbb Z_r$: $ab=14$, $g^{ab}=18$, $c=3$, $(g^{ab})^c=13$, not matching $g^a=9$

• with multiplication in $\mathbb N$: $ab=48$, $g^{ab}=3$, $c=3$, $(g^{ab})^c=4$, not matching $g^a=9$

• replacing $r$ with $p-1=22$: $ab=14$ or $48$, $g^{ab}=18$ [either way], $c$ can not be computed.

My final(?) guess of the intended statement is that $g$ is NOT a generator, contrary to the question as currently worded, but rather that

### $g$ is an element of prime order $r$ in the multiplicative group $\mathbb Z_p^*$

Notice how this creates a condition linking $r$ to $p$ (and $g$), absent from the question's wording! With that novelty, it holds that $g^r\bmod p\;=1$, therefore it does not matter if $g^{ab}$ is computed with the product ${ab}$ in $\mathbb Z_r$ or in $\mathbb N$. It also holds that $\gcd(b,r)=1$ [since $r$ is prime], thus the method in the recent comment always work, and the answer is NO.

We could illustrate this with $p=23$, $g=13$ [which is not a generator since $g^{11}\bmod p\;=1$], $r=11$ [which is prime], $a=8$, and $b=6$ :

• $ab=14$ or $48$, $g^{ab}=18$ [either way], $c=2$, $(g^{ab})^c=2$, matching $g^a=2$.
• Is this true if we compute $c = b^-1$ in $Z_r$ and then compute ${g^{ab}}^c$ to get $g^a$? – Loi.Luu Jul 18 '14 at 3:13

Not at all. It's very trivial: $$(g^{ab})^{b^{-1}}=g^a$$

• In what group is $b^{-1}$ computed? – mikeazo Jul 17 '14 at 13:24
• I guess in $\mathbb{Z}_p$ after finding it's inverse – curious Jul 17 '14 at 13:27
• @curious Sorry, but is it gonna work in $Z_p$? – Loi.Luu Jul 17 '14 at 13:40
• @curious: I can't parse what "it's" refers to in your previous comment. Rather, my bets are on the inverse $\pmod{p-1}$ – fgrieu Jul 17 '14 at 13:41
• @curious p is known, and r is known also. – Loi.Luu Jul 17 '14 at 13:52