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