# Determining the primitive root $g$ of $p$, given $B=g^b \pmod p$

This is related to Diffie-Hellman key exchange.

Suppose you're given a prime $p, b \in \{0,1,...,p-2\}$, and $B$, such that $$B= g^b \pmod p.$$

Assuming that $$\gcd(b, p-1)=1$$ How could you determine the primitive root $g$?

• Aw, come on, $g = B^{1/b}$... – fkraiem Apr 5 '17 at 18:17
• Maybe you could explain the reasoning, instead of a snarky one-liner. Just because its obvious to you doesn't mean its obvious to everyone – JackB Apr 5 '17 at 18:32
• @fkraiem We get it, you know the answer. This is not helpful though, and a sure way to prevent new users from staying around on this site. On that note, welcome JackB. – CurveEnthusiast Apr 5 '17 at 19:56
• @curveenthusiast Are you serious? This was a very low quality question, not deserving of more than that; for one thing it was probably a homework dump, which is discouraged in the faq sections that everyone is supposed to read before posting. – fkraiem Apr 6 '17 at 4:43
• @fkraiem Not homework. Just learning some basics. On the other hand, if you can't even be bothered to help beyond snarky one-liners, then why even bother posting? It's a fair question for those of us who are new to the field. – JackB Apr 6 '17 at 4:52

If $\gcd(b,p-1)=1$ you have $u\cdot b + y\cdot (p-1) = 1$ where $u=b^{-1} \bmod {(p-1)}$. With Euler's theorem $B^{p-1} \equiv 1\bmod p$ you get $$g \equiv B^u \bmod p.$$
Right you are with your comment, I have included the changes. Euler's theorem is used at the penultimate step: This is the 'easy case' on page 4 of the reference given by SEJPM $$g^u \equiv (B^u)^b \equiv B^{ub} \equiv B^{1-y(p-1)} \equiv B \cdot (B^{p-1})^{-y}\equiv B \cdot 1^{-y}\equiv B \bmod p$$ Example: $p=11, b=7, B=4$. Compute: $$u \equiv 7^{-1} \equiv 3 \bmod {10}$$ $$g \equiv 4^3 \equiv 9 \bmod {11}$$ and check: $$9^7 \equiv 4 \bmod 11$$
• Shouldn't it be $$u = b^{-1} mod (p-1)$$ ? Also, I'm not clear how you arrive at the result from Euler's theorem. – JackB Apr 5 '17 at 19:50
• @JackB Yes, $\bmod(p-1)$ is meant (the parenthesization is a bit ambiguous). By definition, we have $ub=1+k(p-1)$ for some $k$, hence $$B^u\equiv g^{bu}\equiv g^{1+k(p-1)}\equiv g\cdot(g^{p-1})^k\pmod{p}\text.$$ By the theorem, $g^{p-1}\equiv1\pmod p$, hence any power of this is also congruent to $1$ modulo $p$, thus $B^u\equiv g\pmod p$. – yyyyyyy Apr 5 '17 at 22:49