# RSA problem - how to find $d$ [duplicate]

For example, let $p = 3$ and $q= 11$, choose $e = 3$. What computation I have to apply in order to find the corresponding $d$? I know it's 7, but I want to know the exact process to be applied to find it.

• There are an incalculable number of threads on this site alone, let alone the whole internet, that address the process of deriving $d$ from $e$. Have you tried searching for them? Hint, there are at least two in the related questions list on the right. Aug 3 '15 at 11:29
• This is not exactly a duplicate because the linked question does not address how $d$ is found (only which property it satisfies). I think a good answer to this question should mention the extended Euclidean algorithm. Maybe it would be a good idea to add it to the answer in the linked question... Aug 3 '15 at 12:34
• @fkraiem I see your point. I've now closed it as a duplicate of a different question. Let me know what you think of this one. Aug 3 '15 at 12:50
• @mikeazo Yes this one is excellent. Aug 3 '15 at 12:52
• @fkraiem thanks for pointing it out. After looking at it close, you were definitely right that the first "duplicate" wasn't good enough. Aug 3 '15 at 12:54

Ok, RSA is a asymmetric crypto system. Which means you have a separate key for encryption and decryption.

Remember RSA is based on cyclic groups. So don't forget the modulo.

Here are the basic equations. $n$ is the product of $p$ and $q$. $\varphi(n) = (p-1)*(q-1)$

$gcd (e, \varphi(n)) = 1$ - for calculating the e. e is random but must fit this equation.

$d = e^{-1} \bmod{\varphi(N)}$ And now you can calculate d.

• You had a typo in the original. You had $d=e\bmod{\varphi(N)}$ instead of $d=e^{-1}\bmod{\varphi(N)}$. I also added tex formatting. Aug 3 '15 at 12:06
• Also, $e$ is typically not random. Usually $e=65537$ is used. There are a few other popular choices for $e$. Aug 3 '15 at 12:23
• I know what RSA is, I just don't understand how $3^{-1}\bmod{20}$ could be $7$. That's it. It's not a duplicate question because my question is focused only on finding $d$. I'm not asking what RSA is for god's sake. Aug 3 '15 at 12:46