Multiplicative Inverse and RSA

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

-
Why do you want a method other than the extended Euclidean algorithm? It is extremely simple and fast to compute. –  Brandon Carter Mar 5 '11 at 5:08
@Brendom : I am just enthusiastic –  Prasoon Saurav Mar 5 '11 at 5:09
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. –  Henno Brandsma Mar 5 '11 at 12:44

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

-

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

-

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.

-