In RSA: Fast factorization of N if d and e are known a comment under the OPs question stated that if the encrytion exponent $e$ is small compared to $N=p\cdot q$ for the RSA-primes $p,q$ (like $e<\sqrt{N}$) one could find $k$ in $de=1+k\varphi(N)$ by rounding $\frac{de}{N}$ as $k$ is an integer and $\varphi(N)\approx N$.
I don't know how to show this rigorously as I don't find a way to use $e<\sqrt{N}$ and I'm unsure whether the floor function or some other approximation was meant. (For the following i went with the floor as it seemed to be the most reasonable)
As $\varphi(N)\le N$ I know that:
$$k=\left\lfloor \frac{1}{N}+k\right\rfloor\ge\left\lfloor \frac{de}{N}\right\rfloor$$
As $\varphi(N)=N-p-q+1$ is also know that:
\begin{align*}
\left\lfloor\frac{de}{N}\right\rfloor&=\left\lfloor\frac{1}{N}+k\frac{\varphi(N)}{N}\right\rfloor\\
&=\left\lfloor\frac{1}{N}+k\frac{pq-p-q+1}{pq}\right\rfloor\\
&=\left\lfloor\frac{1}{N}+k\left(\frac{1}{N}-\frac{1}{q}-\frac{1}{p}\right)\right\rfloor+k
\end{align*}
So it would be nice to have $\left\lfloor\frac{1}{N}+k\left(\frac{1}{N}-\frac{1}{q}-\frac{1}{p}\right)\right\rfloor=0$ as this would show the preposition.
Does this result even hold true?
No comments:
Post a Comment