Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint

Abstract. We address the problem of polynomial time factoring RSA moduli N1 = p1q1 with the help of an oracle. As opposed to other ap-proaches that require an oracle that explicitly outputs bits of p1, we use an oracle that gives only implicit information about p1. Namely, our or-acle outputs a different N2 = p2q2 such that p1 and p2 share the t least significant bits. Surprisingly, this implicit information is already suffi-cient to efficiently factor N1, N2 provided that t is large enough. We then generalize this approach to more than one oracle query. Key words: Factoring with an oracle, lattices