You are looking at a specific version 20090701:110016 of this paper.
See the latest version.
Paper 2009/323
Factoring Unbalanced Moduli with Known Bits
Eric Brier and David Naccache and Mehdi Tibouchi
Abstract
Let $n = pq > q^3$ be an RSA modulus. This note describes a LLL-based method allowing to factor $n$ given $2log_2q$ contiguous bits of $p$, irrespective to their position. A second method is presented, which needs fewer bits but whose length depends on the position of the known bit pattern. Finally, we introduce a somewhat surprising ad hoc method where two different known bit chunks, totalling $\frac32 log_2 q$ bits suffice to factor $n$.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- factoringLLL
- Contact author(s)
- david naccache @ ens fr
- History
- 2009-07-01: received
- Short URL
- https://ia.cr/2009/323
- License
-
CC BY