0
$\begingroup$

I have been reading the wiki article about Modular multiplicative inverse and I don't understand it. Can you explain it to me in better way.

To be more specific I am trying to understand the RSA algorithm and I stuck in their working example paragraph 5. I don't understand the math behind this calculation:

The modular multiplicative inverse of $17\pmod{\phi(3233)}$ yielding $2753$.

$\endgroup$
  • 1
    $\begingroup$ Which part don't you understand? Do you see that the given number is in fact the inverse? $\endgroup$ – Tobias Kildetoft Feb 25 '14 at 10:30
  • 1
    $\begingroup$ Check this answer math.stackexchange.com/a/437978/72031 It uses different numbers to explain RSA. You can see that the inverse is calculated using the Euclid's algorithm for HCF/GCD $\endgroup$ – Paramanand Singh Feb 25 '14 at 10:30
3
$\begingroup$

What they refer to as a "worked example" is just a verification of the fact that the multiplicative inverse of $17$ modulo $\phi(3233) = 3120$ is $2753$.

In order to find the multiplicative inverse of $17$ modulo $3120$, suppose $17x \equiv 1 \bmod 3120$. Then $3120 \mid (17x - 1)$ so $17x - 1 = 3120y$ for some $y \in \mathbb{Z}$. Rearranging, we obtain the equation $17x - 3120y = 1$. Now we use the Euclidean algorithm to find the greatest common divisor of $17$ and $3120$:

\begin{align*} 3120 &= 183\times 17 + 9\\ 17 &= 1\times 9 + 8\\ 9 &= 1\times 8 + 1. \end{align*}

So the greatest common divisor of $17$ and $3120$ is $1$; note, if it weren't $1$, then the equation $17x - 3120y = 1$ would have no solutions. Using back substitution, we have

\begin{align*} 1 &= 9 - 1\times 8\\ &= 9 - 1\times(17 - 1\times 9)\\ &= 2\times 9 - 1\times 17\\ &= 2\times(3120 - 183\times 17) - 1\times 17\\ &= 2\times 3120 - 367\times 17. \end{align*}

Therefore $x = -367$, $y = 2$ is a solution to $17x - 3120y = 1$. So $(-367)\times 17 \equiv 1 \bmod 3120$. Note that for any $t \in \mathbb{Z}$, $(-367 + 3120t)\times 17 \equiv -367\times 17 \bmod 3120 \equiv 1\bmod 3120$. Taking $t = 1$, we see that $-367 + 3120\times 1 = 2753$.

$\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.