1
$\begingroup$

$r$ is a primitive root for the prime $p$

$x_1\equiv r^a \pmod{p}$

$x_2\equiv r^b \pmod{p}$

If $gcd(b, p-1)=1$, how can I determine $r$ if $p$, $x_2$, and $b$ are known?

  • 0
    That's the problem as it was assigned :)2010-10-16

2 Answers 2

5

HINT: If gcd$(b,p-1)=1$, then we can write $1 = tb + s(p-1)$. So $tb\equiv 1 \pmod{p-1}$.

  • 0
    What happens if you take $x_2^t$? Since $x_2\equiv r^b\pmod{p}$, the result will be congruent to..., which in turn is congruent to... (why?).2010-10-16
2

HINT $\ $The isomorphism $\rm n\to r^n\:$ from the additive group $\rm \mathbb Z/(p-1)$ to the multiplicative group $\rm \mathbb Z/p^*\:$

maps $\rm\ b\to x,\ 2b\to x^2,\: \cdots\:,\: nb\to x^n$. You seek $\rm 1\to r\ $ so you need $\rm\ nb\equiv 1\ $ so $\rm\ n\equiv \:\ldots$

  • 0
    Yes, $1/b \in \mathbb Z/(p-1)$, i.e. $1/b$ mod $p-1$. Note how understanding the isomorphism makes the way to the solution obvious.2010-10-16