# Find inverse in RSA

I've been reading on RSA for a while but there's something I still can't understand. When generating the key: once you find n = pq and φ(n), you choose a number d coprime with φ(n) and then you need to find e the inverse of d mod φ(n).

Don't you need to do that to know φ(φ(n)) and then use Fermat Little Theorem? If so you would need to find the factorisation of φ(n) = (p-1)(q-1) and therefore factorise (p-1)/2 and (q-1)/2. Isn't that potentially very long?

Gabriele

once you find $n = pq$ and $\phi(n)$, you choose a number $d$ coprime with $\phi(n)$ and then you need to find $e$ the inverse of $d \bmod \phi(n)$
Actually, what we usually do is: select $e$; then find primes $p$ and $q$ with $p-1, q-1$ coprime with $e$, and then find $d$ which is the inverse of $e \bmod \text{lcm}(p-1,q-1)$. But that doesn't answer your question.
Don't you need to do that to know $\phi(\phi(n))$ and then use Fermat Little Theorem?
I suppose we could select the primes $p$ and $q$ in a way so that we know the factorization of $p-1, q-1$.
However, we (typically) don't. Instead, we use the Extended Euclidean Method to find the needed inverse; that doesn't require us to know the factorization of $\phi(n)$ (or $\text{lcm}(p-1, q-1)$)