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
  • 3
    $\begingroup$ Why do you want a method other than the extended Euclidean algorithm? It is extremely simple and fast to compute. $\endgroup$
    – bzc
    Commented Mar 5, 2011 at 5:08
  • $\begingroup$ @Brendom : I am just enthusiastic $\endgroup$ Commented Mar 5, 2011 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$ Commented Mar 5, 2011 at 12:44

4 Answers 4

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$
1
  • $\begingroup$ Right, so when n is on 512 bits this will take longer than the age of the universe... ;p $\endgroup$ Commented Nov 26, 2022 at 12:47
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .