**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.

**Category / Keywords: **Implicit Factoring, Lattice, RSA moduli

**Publication Info: **The paper hasn't been published anywhere

**Date: **received 21 Mar 2009, withdrawn 30 Mar 2009

**Contact author: **panyanbin at amss ac cn

**Available format(s): **(-- withdrawn --)

**Version: **20090330:170455 (All versions of this report)

**Short URL: **ia.cr/2009/132

[ Cryptology ePrint archive ]