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?
Thanks in advance