Is there an easy way to calculate "d" in the RSA algorithm?

Quite frankly, it is a pain to use the Extended Euclidean Algorithm to calculate d (the private exponent) in RSA. The equation used to find d is:

$$ e d \equiv1~(\mathrm{mod}~ \varphi(n)).$$

Does anyone have a way to solve for d using basic algebra or something simpler? If not, can someone explain how to use the Extended Euclidean Algorithm to find d?


The easiest way which is widely known to calculate a modular inverse is finding the smallest $k\in\mathbb N$ such that the following expression is an integral integer:

$$\frac{1+k\cdot \varphi}{e}$$

If this is an integral integer, it is the inverse of $e$ modulo $\varphi$ and thus $d$ and you'll find it with at most $e$ tries.

The issue obviously know is that the run-time of this will grow linearly with the size of $e$, as opposed to the extended euclidean algorithm (EEA) which will run in time proportional to (a power of) the logarithm of $e$, which will especially be much faster than the above method when $e$ is chosen as large as the modulus. If you want to see examples and how-tos on the algorithm, Wikipedia is your friend as usual.

Category: encryption Time: 2016-07-30 Views: 2

Related post

iOS development

Android development

Python development

JAVA development

Development language

PHP development

Ruby development


Front-end development


development tools

Open Platform

Javascript development

.NET development

cloud computing


Copyright (C), All Rights Reserved.

processed in 2.431 (s). 13 q(s)