1

For the following encryption key $(n, E)$ in the RSA cryptosystem, compute $D$.

$(n, E)= (451, 231)$

So I know $n=11*41$, so $m=400$. Now $D=$ inverse of $231 \ (mod \ 400)$. However I am not sure how to find the inverse of $231$ in $mod\ 400$. Help with this would be great.

Ryan
  • 25

1 Answers1

1

Expanding on the comment, the Euclidean algorithm gives: \begin{align*} 400 &= 231 \times 1 + 169.\\ 231 &= 169 \times 1 + 62.\\ 169 &= 62 \times 2 + 45.\\ 62 &= 45 \times 1 + 17.\\ 45 &= 17 \times 2 + 11.\\ 17 &= 11 \times 1 + 6.\\ 11 &= 6 \times 1 + 5.\\ 6 &= 5 \times 1 + 1. \end{align*} Then, we do this in reverse... \begin{align*} 1 &= 6 - 5\\ &= 6 - (11 - 6)\\ &= 2 \times 6 - 11\\ &= 2 \times (17 - 11) - 11\\ &= ...\\ &= 71 \times 231 - 41 \times 400. \end{align*} (Check the details.) Viewing the last equation modulo $400$ gives $$ 231^{-1} \equiv 71 \mod 400. $$

Platehead
  • 738