In RSA, to calculate $d$, when given $\phi(n)$ and $e$, I stumbled upon this formula:
$$d = \dfrac{k \phi(n) + 1}{e}$$
But what does $k$ stand for? How to obtain the value for $k$?
Thank you,
Chris
2 Answers
$\begingroup$$d$ in an integer which satisfies
$ed\equiv 1\mod \phi(n)$,
which means that there exists an integer $k$ such that
$ed = 1 + k\cdot \phi(n).$
$\endgroup$ $\begingroup$We can rearrange your equation to obtain:
$$de = k\phi(n)+1$$
or:
$$de \equiv 1 \pmod {\phi(n)}$$
Therefore $d$ is the inverse of $e$ in $\mathbb Z_{\phi(n)}$. (This only makes sense if $e$ and $\phi(n)$ are coprime, by Bezout's Lemma.)
To find this $d$ (and the less important $k$), we can use the Euclidean Algorithm.
$\endgroup$
