### Factoring Unbalanced Moduli with Known Bits

Eric Brier, 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$.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
factoringLLL
Contact author(s)
david naccache @ ens fr
History
Short URL
https://ia.cr/2009/323

CC BY

BibTeX

@misc{cryptoeprint:2009/323,
author = {Eric Brier and David Naccache and Mehdi Tibouchi},
title = {Factoring Unbalanced Moduli with Known Bits},
howpublished = {Cryptology ePrint Archive, Paper 2009/323},
year = {2009},
note = {\url{https://eprint.iacr.org/2009/323}},
url = {https://eprint.iacr.org/2009/323}
}

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