# Inverse of an element in a RSA group

Consider a RSA group $$Z_N$$ for $$N=pq$$, where $$p,q$$ are large prime numbers. Under strong RSA assumption, can an adversary efficiently compute the inverse of a random element $$z$$ from $$Z_N$$ without access to $$p,q, \phi(N)$$? Mathematically does there exists efficient algorithm $$\mathcal{A}$$ s.t

$$\mathbb{P}\left( z.u=1,\quad z \leftarrow Z_N,\; u=\mathcal{A}(x,N) \right) \geq \text{neglible}?$$

PS: I am learning cryptography so my notations are quite shaky.

• Welcome to crypto.stackexchange - How does the reference-request tag fit into your question? Are you hoping to find some kind of paper with the solution or ? If so then you may want to state that explicitly in your answer. – Ella Rose Feb 10 '19 at 20:43
• @EllaRose: I was hoping to find a reference to lecture notes. – Vivek Bagaria Feb 10 '19 at 21:57

## 1 Answer

Mathematically does there exists efficient algorithm $$\mathcal{A}$$

Yes; the Extended Euclidean algorithm can be used to efficiently compute multiplicative inverses modulo $$N$$, without knowledge of the factorization of $$N$$.

• Addition: this works by using the Extended Euclidean algorithm to find the $(u,v)$ in Bézout's identity $u\,z+v\,N=1$. We do not need $v$, and that allows to reduce the cost by a small factor, see this. There's also a binary variant, see this. – fgrieu Feb 12 '19 at 10:51