0
$\begingroup$

I need to use Euclid's algorithm to find d in the following equation. Given values for e and p

$$(e\times d)\mod p = 1$$

I have used Euclid's algorithm to find the gcd of two numbers but can't see how to apply it to the above.

$\endgroup$
0
$\begingroup$

Hint: The Euclid algorithm not only allows to find the gcd of two numbers, it also allows to find $u$ and $v$ such that if $(a,b)=1$ one has $ua+vb=1$. Now we have $(e,p)=1$ because $p$ is prime and $e$ should not be a multiple of $p$ otherwise $\forall g\in\Bbb{Z},\,e\times g\equiv 0\pmod{p}$. So use the Euclid algorithm to find $u$ and $v$ such that $ue+vp=1$. And this is rewriten $\pmod{p}$ as $u\times e\equiv 1$ and therefore $d\equiv u\pmod{p}$

$\endgroup$

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.