Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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
add comment

3 Answers

up vote 5 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.