4 ms·

Here is an argument I made that it is NP-complete to determine if a number n is the product of two numbers that differ by less than the fourth root of n: https

Here is an argument I made that it is NP-complete to determine if a number n is the product of two numbers that differ by less than the fourth root of n: https://cstheory.stackexchange.com/a/37439 https://cstheory.stackexchange.com/a/37439

mjd 5y ago
I've added this to the article. Thanks very much for the reference.
dmdox 5y ago
There's a trivial algorithm to do this in polynomial time. Let x = ceil(sqrt(n)). Let y = sqrt(x^2 - n). If y is an integer, then x^2 - y^2 = n = (x - y)(x + y). This provides the factorization a*b with a, b closest together. If y is an not an integer, increment x by one, recompute y, and try again. If n is a product of two numbers that differ by less than n^(1/4), this will find those numbers in 1 or 2 steps.
- nokita 5y ago
  I think it needs to be poly in the number of bits, not just the number, otherwise factoring would be poly, and it isn't.
  - dmdox 5y ago
    This is polynomial time in the number of bits. I did make one mistake. I forgot to mention the half-integer case for x and y, which requires some additional logic. I implemented it fully python: https://gdl.space/obiyukevit.py https://gdl.space/obiyukevit.py N is 256-bit a sample number.
- svat 5y ago
  I was skeptical at first, but this checks out: I think I was able prove that if N is a product of two numbers `a` and `b` (both odd or both even, for simplicity), such that a is less than b and (b-a) is less than 2√2 times N^(1/4), and if `r` is the ceiling of the square root of N, then r^2 - N is a square (say s^2), so we can find the factorization N = (r^2 - s^2) = (r-s)(r+s) without any searching (the very first step). The half-integer case I haven't thought about yet, but this suggests the claim is wrong... or maybe N^(1/4) needs to be replaced with N^(1/4+epsilon) or something.
  - dmdox 5y ago
    Right. Define L = (a+b)/2 and R = (a-b)/2, so that a * b = L² - R² for all a, b. If there exist positive integers a, b such that a * b = n with |a-b| <= k n^(1/4) [constant k] Then there exist L, R (either both integers or both half-integers) with L² - R² = n and |R| <= (1/2) k n^(1/4) From which one can deduce: R² <= (k²/4) √n L² - R² >= L² - (k²/4) √n n >= L² - (k²/4) √n L² <= n + (k²/4) √n L <= √(n + (k²/4) √n) L <= √n + k²/8 If k <= 1, then L must be ceil(√n) or ceil(√n) - 1/2 If k <= 2√2, then L must be ceil(√n), ceil(√n) - 1/2, or ceil(√n) + 1/2 (my original estimate of 2 steps was due a slight miscalculation) Adding epsilon would re-introduce an exponential component to the search. In fact, epsilon = 3/4 gives you total power. But this is only relevant if the reduction (https://cstheory.stackexchange.com/a/4785 https://cstheory.stackexchange.com/a/4785) can be made precise enough to bound L, U to within a fixed small epsilon. It could even be the case that you can bound to an arbitrarily small epsilon, but only at the expense of exploding other parameters. (B, T, k).
    - svat 5y ago
      In the meantime, I wrote this up in (too much elementary) detail: https://colab.research.google.com/drive/10t4WRhyAPK1pCzBkaauFIkRUYek6YN2p#scrollTo=o3-qIlIgt7zk https://colab.research.google.com/drive/10t4WRhyAPK1pCzBkaau... The funny thing is, it's often the case that already √(m^2 - 4N) > N^(1/4), so we can answer "No" to whether such a factorization exists, without even trying a single attempt.
      - dmdox 5y ago
        If you're interested in investigating more, take a look at "Continued Fraction Factorization". This is essentially the first step of that more advanced algorithm. From the continued fraction of √n, you get a series of best rational approximations a/b to √n. Each such approximation gives you: a/b ~ √n a² ~ b² n The first approximation is a = floor(√n), b = 1 These approximations satisfy |a² - b² n| < 2 √n. (this can be used for generating relations as input to Dixon's method)
  - deleted 5y ago
    [deleted]

mjd 5y ago

I've added this to the article. Thanks very much for the reference.

dmdox 5y ago

There's a trivial algorithm to do this in polynomial time. Let x = ceil(sqrt(n)). Let y = sqrt(x^2 - n). If y is an integer, then x^2 - y^2 = n = (x - y)(x + y). This provides the factorization a*b with a, b closest together. If y is an not an integer, increment x by one, recompute y, and try again. If n is a product of two numbers that differ by less than n^(1/4), this will find those numbers in 1 or 2 steps.

nokita 5y ago
I think it needs to be poly in the number of bits, not just the number, otherwise factoring would be poly, and it isn't.
- dmdox 5y ago
  This is polynomial time in the number of bits. I did make one mistake. I forgot to mention the half-integer case for x and y, which requires some additional logic. I implemented it fully python: https://gdl.space/obiyukevit.py https://gdl.space/obiyukevit.py N is 256-bit a sample number.
svat 5y ago
I was skeptical at first, but this checks out: I think I was able prove that if N is a product of two numbers `a` and `b` (both odd or both even, for simplicity), such that a is less than b and (b-a) is less than 2√2 times N^(1/4), and if `r` is the ceiling of the square root of N, then r^2 - N is a square (say s^2), so we can find the factorization N = (r^2 - s^2) = (r-s)(r+s) without any searching (the very first step). The half-integer case I haven't thought about yet, but this suggests the claim is wrong... or maybe N^(1/4) needs to be replaced with N^(1/4+epsilon) or something.
- dmdox 5y ago
  Right. Define L = (a+b)/2 and R = (a-b)/2, so that a * b = L² - R² for all a, b. If there exist positive integers a, b such that a * b = n with |a-b| <= k n^(1/4) [constant k] Then there exist L, R (either both integers or both half-integers) with L² - R² = n and |R| <= (1/2) k n^(1/4) From which one can deduce: R² <= (k²/4) √n L² - R² >= L² - (k²/4) √n n >= L² - (k²/4) √n L² <= n + (k²/4) √n L <= √(n + (k²/4) √n) L <= √n + k²/8 If k <= 1, then L must be ceil(√n) or ceil(√n) - 1/2 If k <= 2√2, then L must be ceil(√n), ceil(√n) - 1/2, or ceil(√n) + 1/2 (my original estimate of 2 steps was due a slight miscalculation) Adding epsilon would re-introduce an exponential component to the search. In fact, epsilon = 3/4 gives you total power. But this is only relevant if the reduction (https://cstheory.stackexchange.com/a/4785 https://cstheory.stackexchange.com/a/4785) can be made precise enough to bound L, U to within a fixed small epsilon. It could even be the case that you can bound to an arbitrarily small epsilon, but only at the expense of exploding other parameters. (B, T, k).
  - svat 5y ago
    In the meantime, I wrote this up in (too much elementary) detail: https://colab.research.google.com/drive/10t4WRhyAPK1pCzBkaauFIkRUYek6YN2p#scrollTo=o3-qIlIgt7zk https://colab.research.google.com/drive/10t4WRhyAPK1pCzBkaau... The funny thing is, it's often the case that already √(m^2 - 4N) > N^(1/4), so we can answer "No" to whether such a factorization exists, without even trying a single attempt.
    - dmdox 5y ago
      If you're interested in investigating more, take a look at "Continued Fraction Factorization". This is essentially the first step of that more advanced algorithm. From the continued fraction of √n, you get a series of best rational approximations a/b to √n. Each such approximation gives you: a/b ~ √n a² ~ b² n The first approximation is a = floor(√n), b = 1 These approximations satisfy |a² - b² n| < 2 √n. (this can be used for generating relations as input to Dixon's method)
- deleted 5y ago
  [deleted]