2
$\begingroup$

In order to solve an ElGamal cryptographic problem, I need to solve

8x≡1 (mod 17)

Or simply, find the inverse of 8 in the context of modular 17.

By the Extended Euclidean Algorithm, we get:

17=8(2)+1
=> 1=17-8(2)

So, simply, the inverse of 8 (mod 17) should be 2, but this is not the case, It is indeed 15. What am I missing here? My experience with number theory is touchy, and this code theory course requires it.

$\endgroup$
  • 3
    $\begingroup$ The inverse of $8$ is $\color{red} -2$, by your calculation, and $-2\equiv 15\mod 17$. $\endgroup$ – Bernard Mar 24 '19 at 21:17
2
$\begingroup$

$\bmod 17\!:\,\ 1 = 17-8(2)\equiv -8(2)\equiv 8(\color{#c00}{-2})\,$ so $\,8^{-1}\equiv \color{#c00}{-2}\equiv 15\ \ $

Remark $ $ Generally $\,\gcd(a,n)=1\,\Rightarrow\,\underbrace{ 1=ja+kn}_{\rm Bezout}\,\Rightarrow\,\bmod n\!:\ 1\equiv ja\,\Rightarrow\, j\equiv a^{-1}$

$\endgroup$
  • $\begingroup$ Perfect! I should have been thinking of it as 17+(8*-2), thank you (will accept when the timer allows)! $\endgroup$ – TryingToPassCollege Mar 24 '19 at 21:18

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.