# RSA: How to calculate the private exponent?

I have this problem: In RSA algorithm considering $n=33$ (modulus) and public exponent $e=3$, calculate the corresponding private exponent $d$.

I know that $d = e^{-1} \pmod{\varphi(n)}$ and $\varphi(n) = (p – 1) (q – 1)$ but I don't know $p$ and $q$.

How can I do this?

• So you're been given a public key, and asked to compute the private key. That is, by definition, hard (although for small numbers you can probably just try combinations of p, q until one works). That is why RSA is considered safe. May 9 '15 at 16:23
• @MikeOunsworth Things can't be "hard by definition". It is unknown whether the RSA problem is hard — although for small $n$, it certainly isn't. May 9 '15 at 16:47
• Well it's known that the RSA problem is at maximum as hard as the integer factorization problem, but the lower bound is missing... And nothing is hard for bad parameters.
– SEJPM
May 9 '15 at 16:58
• You could factor $n$. 33=3*11 May 9 '15 at 20:55

If I'm understanding your question right, you want to obtain $d$ from given $n$ and $e$.
You'll have to factor $n=33=3*11$ and as $N=p*q$ you have obtained your $p=11$ and $q=3$. Now proceed as usual with calculating the inverse.
As pointed out correctly above, you can't easily generalize this approach to larger numbers as factoring $n$ will be infeasible. Now you see how to factor the number but for larger numbers even the best algorithms fail.
Concerning your $e=3$ I'd consider using Coppersmith's attacks on low exponent RSA.