1
$\begingroup$

I have been going through the RSA cipher and have been wondering if there is a way other than the Extended Euclid Method to find

$a^{-1} \mod n$

where a,n $\in$ Z

P.S : n is not necessarily prime

  • 0
    To check that the inverse mod n exists at all you need to do Euclid (the basic version). With a little extra bookkeeping (extended Euclid) we get the inverse for free. BTW, to do RSA itself you do not need this operation at all. Only at set-up, where we have to compute $d = e^{-1} \mod \phi(n)$ do we need it.2011-03-05

4 Answers 4

6

Let $a \in \mathbb{Z}$ with $(a,n)=1$. Then by Euler's Theorem, $a^{\varphi(n)} \equiv 1 \pmod n$ Then, it follows, since $a$ is invertible mod $n$, that $a^{-1} \equiv a^{\varphi(n)-1} \pmod n$ As a note, in practice this is much harder to compute than by using the extended Euclidean algorithm, as computing $\varphi(n)$ requires factoring $n$.

1

Step 1: Compute the product $ax$ for all integers $1\leq x \leq n-1$. Stop when $ax\equiv 1 \pmod n$.

Step 2: The $x$ you get from the previous step is $a^{-1}$.

DONE

0

Do the standard Euclidean algorithm with n^2 and an+1. The first remainder less than n that appears is the inverse of a.

Example:

Find the inverse of 16 mod 21:

Apply the Euclidean algorithm to 21^2 = 441 and 16*21+1 = 337 to get

441 = 337 + 104 337 = 3*104 + 25 104 = 4*25 + 4

Since 4 is less than 21, 4 is the inverse of 16 mod 21.