15
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 7
    $\begingroup$ Why the votes to close? It seems an interesting problem that people have worked on. $\endgroup$
    – Lucia
    Commented Mar 9, 2015 at 5:02

2 Answers 2

Reset to default
14
$\begingroup$

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.

Improve this answer
$\endgroup$
10
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ So if, unbeknownst to you, $a$ has 160 digits, and $b$ has 90, then knowing the first 75 digits of $a$ isn't much help? $\endgroup$
    – Gerry Myerson
    Commented Mar 9, 2015 at 5:18
  • 3
    $\begingroup$ Knowing the first 75 digits of $a$ is essentially the same as knowing them for $b$ (since you know all the digits of the product $ab$ and can do approximate division), so you can still apply Coppersmith's algorithm to $b$. It's a little less efficient if you don't know how big the numbers are: the setup I have in mind requires knowing the number of digits, but you can brute force this since there are only 125 possibilities. $\endgroup$
    – Henry Cohn
    Commented Mar 9, 2015 at 5:26
  • 1
    $\begingroup$ (I edited the answer to try to clarify this, since the original version did make it sound like the assumption of equal-sized factors might be essential.) $\endgroup$
    – Henry Cohn
    Commented Mar 9, 2015 at 5:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .