Paper 2009/132

A New Lattice for Implicit Factoring

Yanbin Pan and Yingpu Deng


In PKC 2009, Alexander May and Maike Ritzenhofen\cite{MR} proposed an ingenious lattice-based method to factor the RSA moduli $N_1=p_1q_1$ with the help of the oracle which outputs $N_2=p_2q_2$, where $p_1$ and $p_2$ share the $t$ least significant bits and $t$ is large enough when we query it with $N_1$. They also showed that when asking $k-1$ queries for RSA moduli with $\alpha$-bit $q_i$, they can improve the bound on $t$ to $t\geq\frac{k}{k-1}\alpha$. In this paper, we propose a new lattice for implicit factoring in polynomial time, and $t$ can be a little smaller than in \cite{MR}. Moreover, we also give a method in which the bound on $t$ can also be improved to $t\geq\frac{k}{k-1}(\alpha-1+\frac{1}{2}\log{\frac{k+3}{k}})$ but with just only one query. Moreover we can show that our method reduces the running time of the implicit factoring for balanced RSA moduli much efficiently and makes it practical.

Available format(s)
-- withdrawn --
Publication info
Published elsewhere. The paper hasn't been published anywhere
Implicit FactoringLatticeRSA moduli
Contact author(s)
panyanbin @ amss ac cn
2009-03-30: withdrawn
2009-03-27: received
See all versions
Short URL
Creative Commons Attribution
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.