# RSA cryptosystem: If $k$ is a multiple of $\phi(N)$, then $k=2^t r$ with $r$ odd and $t\geq1$

I'm reading Twenty Years of Attacks on the RSA Cryptosystem by Dan Boneh and trying to understand the proof of the Fact 1 on page 3.

Fact 1: Let $(N,e)$ be an RSA public key. Given the private key $d$, one can efficiently factor the modulus $N = pq$.

Dan says that since $\phi(N)=(p-1)(q-1)$ is even, $k=de-1=2^t r$ with $r$ odd and $t\geq1$. $k$ is a multiple of $\phi(N)$. Well, I tried to derive that formula for $k$, but didn't succeed. Any ideas?

-
$k$ must be multiple of $\lambda(N)=$lcm$(p-1,q-1)$ See mathworld.wolfram.com/CarmichaelFunction.html – lab bhattacharjee May 21 '13 at 16:25

The condition $de \equiv 1 \mod \phi(N)$ can also be written as $$de - 1 = k = m\phi(N)$$ with some integer $m$. Now $\phi(N)$ is divisible by 4 since $p-1$ and $q-1$ are both even, hence $k$ is divisible by 4. Keep dividing $k$ by 2 until you get an odd quotient. Then $k = 2^tr$ with $t \ge 2$ and odd $r$.