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

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

For a congruent to more than half of n:

  • take $y\equiv n-(a \bmod n)$
  • find $y^{-1}\equiv x \bmod n$
  • take $a^{-1}\equiv n-x\bmod n$
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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