International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Mathias Herrmann

Publications

Year
Venue
Title
2010
PKC
2009
ASIACRYPT
2009
PKC
2008
ASIACRYPT
2007
EPRINT
On Factoring Arbitrary Integers with Known Bits
Mathias Herrmann Alexander May
We study the {\em factoring with known bits problem}, where we are given a composite integer $N=p_1p_2\dots p_r$ and oracle access to the bits of the prime factors $p_i$, $i=1, \dots, r$. Our goal is to find the full factorization of $N$ in polynomial time with a minimal number of calls to the oracle. We present a rigorous algorithm that efficiently factors $N$ given $(1-\frac{1}{r}H_r)\log N$ bits, where $H_r$ denotes the $r^{th}$ harmonic number.

Coauthors

Gregor Leander (1)
Alexander May (4)