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.



Factorization when a factor is partially known
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](https://eprint.iacr.org/2013/483), Cryptology ePrint 2013/483.


