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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.