We are given $B \equiv g^b \mod p$ and the values for $B,b,p$ but not $g$.
How can we determine $g$ from the knowledge of $p, b$ and $B$, provided that $\gcd(b, p − 1) = 1$.
The only solution that I can come up with is finding all of the primitive roots of $p$ and then brute forcing the solution but there must be an easier way. Thanks.
Since $b$ and $p-1$ are relatively prime, you can find $u,v$ such that $ub+v(p-1)=1$. you have $g=g^{ub+v(p-1)} = g^{ub}$ mod $p$. Here I use little fermat theorem which says that $g^{p-1}=1$. So given $B,u$, you have just to compute $B^u=g^{ub}=g$ mod $p$.