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

  • 2
    $\begingroup$ Aw, come on, $g = B^{1/b}$... $\endgroup$ – fkraiem Apr 5 '17 at 18:17
  • 2
    $\begingroup$ 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 $\endgroup$ – JackB Apr 5 '17 at 18:32
  • 5
    $\begingroup$ @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. $\endgroup$ – CurveEnthusiast Apr 5 '17 at 19:56
  • 1
    $\begingroup$ @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. $\endgroup$ – fkraiem Apr 6 '17 at 4:43
  • 3
    $\begingroup$ @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. $\endgroup$ – 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$$

  • $\begingroup$ 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. $\endgroup$ – JackB Apr 5 '17 at 19:50
  • 1
    $\begingroup$ @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$. $\endgroup$ – yyyyyyy Apr 5 '17 at 22:49

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.