### A New Lattice for Implicit Factoring

Yanbin Pan and Yingpu Deng

##### Abstract

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.

##### Metadata
Available format(s)
-- withdrawn --
Publication info
Published elsewhere. The paper hasn't been published anywhere
Keywords
Implicit FactoringLatticeRSA moduli
Contact author(s)
panyanbin @ amss ac cn
History
2009-03-30: withdrawn
2009-03-27: received
See all versions
Short URL
https://ia.cr/2009/132
License

CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.