Factorization when a factor is partially known Let's say that I have a very large number of the order ($10^{250+}$) which is composite. I have been given one of its factor partially to a significant amount of digits (say 75+). Then, how can I figure out both its factors completely?
That is,
$$X = a b$$
where $X$ is known and $a$ is known to 75+ digits.
 A: You can use Coppersmith's algorithm [1] (or Howgrave-Graham's [2] simplification) to find the factor, which will be efficient if the number of remaining bits is not too large. The PARI/GP documentation
http://pari.math.u-bordeaux.fr/dochtml/html-stable/Arithmetic_functions.html#zncoppersmith
has an explicit example. Coron, Faugère, Renault, & Zeitoun [3] give an improved version with impressive speed improvements, though I don't know if their code has been released or re-implemented.
[1] D. Coppersmith. Finding a small root of a univariate modular equation. In U. Maurer, ed., Advances in Cryptology - EUROCRYPT '96, Springer, 1996, pp. 155-165.
[2]  Nicholas Howgrave-Graham, Finding small roots of univariate modular equations revisited. In Cryptography and Coding (Lecture Notes in Computer Science volume 1355), 1997, pp. 131-142.
[3] Jean-Sébastien Coron and Jean-Charles Faugère and Guénaël Renault and Rina Zeitoun, A variant of Coppersmith's algorithm with improved complexity and efficient exhaustive search, Cryptology ePrint 2013/483.
A: I assume you mean you know the leading 75 digits of a roughly 125-digit factor.  Then you can reconstruct the factorization using lattice basis reduction.  For an explicit algorithm, see the paper Small solutions to polynomial equations, and low exponent RSA vulnerabilities
by Coppersmith.  All it requires is that the number of digits you know of a factor is a little more than a quarter of the number of digits in the product, although it gets slightly less efficient if you don't know how large the factors are.
Coppersmith's algorithm is not just fast in theory, but also in practice.  In your case, 75 is enough greater than 62.5 that it should be easy.
