0
$\begingroup$

I am solving RSA algorithm wherein I have to find d by finding $7$ inverse modulo $480$. Please help in solving till end using extended euclidean algorithm

Using extended Euclidean Algorithm for finding inverse as follows:

$$480 = 7(68) + 4$$ $$68 = 4(17) + 0$$

Now, I am getting remainder 0 here. How shall I proceed ahead after this first step

$\endgroup$
  • 2
    $\begingroup$ " Please solve using extended euclidean algorithm and show all steps till end." that's a very unreasonable request. More reasonable would be help to get you started or a rough outline $\endgroup$ – fleablood Feb 21 '19 at 20:53
  • 1
    $\begingroup$ $\frac{7}{480}=[0;68,1,1,3]$ and $[0;68,1,1]=\frac{2}{137}$ imply $$7\cdot 137-2\cdot 480 = -1,$$ hence the inverse of $7\pmod{480}$ is given by $-137\equiv 343\pmod{480}$. $\endgroup$ – Jack D'Aurizio Feb 21 '19 at 21:01
  • $\begingroup$ A more efficient technique is probably to find $7^{-1}\pmod{32},\pmod{3},\pmod{5}$, then invoke the Chinese remainder theorem. $\endgroup$ – Jack D'Aurizio Feb 21 '19 at 21:04
  • 1
    $\begingroup$ See here for a very convenient form of the Extended Euclidean Algorithm. $\endgroup$ – Gone Feb 21 '19 at 22:04
  • $\begingroup$ @Jack Unlikely - it's rare that CRT is more efficient than the Extended Euclidean Algorithm, e.g. it took me $10$ seconds of mental arithmetic in my answer below. $\endgroup$ – Gone Feb 21 '19 at 22:06
0
$\begingroup$

$480 = 7*68 + 4$ so $4 = 480 - 7*68$

$7 = 4 + 3$ so $3 = 7-4$

$4 = 3 + 1$ so $1 = 4 - 3$

So $1 = 4-3=$

$(480 - 7*68) - (7-4)=$

$(480-7*68) - (7-(480 - 7*68))=$

$(480-7*68) -(7*69 - 480)=$ $2*480 - 137*7$

=====

So how do you solve $7k \equiv 1 \pmod{480}$?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you please solve till end $\endgroup$ – first last Feb 21 '19 at 21:16
  • $\begingroup$ Yes, I can. But I won't. If $1 = 2*480 - 137*7$ then $-137*7 \equiv 1\pmod {480}$. $\endgroup$ – fleablood Feb 21 '19 at 21:21
  • $\begingroup$ @firstlast You'll find it much easier (and less error prone) to use the method I linked in a comment on your question (similar to the method in Doug's answer). $\endgroup$ – Gone Feb 21 '19 at 22:12
  • $\begingroup$ Yes. I have to agree with Bill and Doug about the ease of their methods. This was a simple case but the errors one usually has..... (#@%*) $\endgroup$ – fleablood Feb 21 '19 at 22:19
1
$\begingroup$

By here $\,\ \overbrace{7^{-1}_{480} \equiv \dfrac{1-480(\color{#c00}{480^{-1}_7})}7}^{\rm\large inverse\ reciprocity}\equiv \dfrac{1-480(\color{#c00}2)}7\equiv -137,\ $ by $\bmod 7\!:\ \color{#c00}{\dfrac{1}{480}}\equiv \dfrac{8}4\equiv\color{#c00} 2$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is essentially a special case (single step) of the Extended Euclidean Algorithm that is more convenient in certain cases. $\endgroup$ – Gone Feb 21 '19 at 22:01
1
$\begingroup$

Here is how I do it and keep myself organized

$\begin {array}{crl} \times480&\times 7\\ 1&0&480\\ 0&1&7\\ 0&68&476\\ 1&-68&4\\ 2&-136&8\\ 2&-137&1 \end{array}$

Number in the first column, I multiply by 480. The number in the second column, I multiply by 7. The third column is their sum.

I do what are effectively matrix row operations to the right column as far as it will go.

$480\times2 + (-137\times 7) = 1$

$-137\equiv 343 \equiv 7^{-1}\pmod{480} $

Worth noting:

$343 = 7^3\\ 7^4\equiv 1\pmod{480}$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

My computation of the gcd of $480$ and $7$ in tabular form:

$$ \begin{matrix} 480 & - & 1 & 0\\ 7 & 68 & 0 & 1\\ 4 & 1 & 1 & -68\\ 3 & 1 & -1 & 69\\ 1 & - & 2 & -137\\ \end{matrix}$$

(where the second column has the quotients $q$, and we subtract $q$ times the row of two after it from the row of $2$ above it, for the last two columns. We stop when we reach divisibility as with $1$ and $3$.
So we get $$1 = 2 \cdot 480 + (-137) \cdot 7$$

which we take modulo $480$ and get $$7^{-1} \equiv -137 \equiv 343 \pmod{480}$$

So, e.g. when in RSA we have $\phi(n)=480$ and $e=7$ we take $d=343$.

| cite | improve this answer | |
$\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.