1
$\begingroup$

What's the approximate computational cost of factoring $N=u^2-v^2$ when $v\ll u$? Assume $u$ and $v$ are unknown integers, with $u$ large enough that $n$ has the size of an RSA modulus.

I suspect there will be at least four ranges of $v$ as it grows, and wonder where the cutoffs are:

  1. $v$ is small enough that for $u_0=\left\lceil\sqrt N\,\right\rceil$ , ${u_0}^2-n$ is an integer, thus $u=u_0$ , $v=\sqrt{u^2-N}$ , and $n=(u-v)(u+v)$.
  2. Fermat factoring and simple improvements is competitive. The baseline tries $i$ sequentially until $(u_0+i)^2-N$ is a square, thus $u=u_0+i$ , and the rest as above.
  3. A method based on the Coppersmith theorem is best. I didn't knew it existed before this answer.
  4. GNFS becomes king.

Update: I find that (1) works for $v$ up to $\sqrt2\,N^{1/4}$.

$\endgroup$
5
  • 1
    $\begingroup$ In the linked answer the Coppersmith theorem is an overkill. The Fermat method succeeds immediately, I added my answer there. $\endgroup$
    – Fractalice
    Jun 5, 2021 at 8:45
  • 1
    $\begingroup$ Around step 3 you can also try Shank's Square Root Factorization, which should be strictly better than Fermat's, but for large integers worse than the "bigger guns" (GNFS, and possibly variations of the quadratic sieve) $\endgroup$
    – tylo
    Jun 5, 2021 at 16:17
  • $\begingroup$ @tylo: I agree SQUFOF would go after 2 if there was not 3. But with 3, I have no idea if there remains a spot where it's best. $\endgroup$
    – fgrieu
    Jun 5, 2021 at 21:30
  • $\begingroup$ @fgrieu Also integers need to be quite large, before GNFS becomes actually better than other methods. At least a couple of hundred bits in length. I can't recall any source, but plotting the L notation shows that it's quite bad for small numbers. That's not an issue for today's RSA lengths, though. $\endgroup$
    – tylo
    Jun 6, 2021 at 11:40
  • 1
    $\begingroup$ It is 100% overkill. The original question sounded like homework. The bivariate method from 2009/318 looks interesting, though I don't know if you can realistically get to 1/3. $\endgroup$ Jun 7, 2021 at 0:04

1 Answer 1

2
$\begingroup$

Fermat method succeeds immediately when $|p-q| = 2v < N^{1/4}$.

There is a paper claiming polynomial time factoring when $|p-q| = 2v < N^{1/3}$ using Coppersmith-based methods.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.