5 ms·

Factoring composite numbers into nearly equal factors

27 points by ColinWright 5y ago

jdb1729 5y ago
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.
        5y ago
madcaptenor 5y ago
Most large numbers can't be factored into nearly equal factors, if we take "nearly equal" to mean "differ by less than a factor of two". I called these "puzzle numbers" because they're reasonable numbers of pieces for a jigsaw puzzle to have, and wrote about it a couple years ago: https://gottwurfelt.com/2020/08/17/how-many-pieces-can-a-puzzle-have/ https://gottwurfelt.com/2020/08/17/how-many-pieces-can-a-puz... For example you could have a 299-piece puzzle (13 by 23) or a 300-piece puzzle (15 by 20) but not a 301-piece puzzle (this will only factor as 7 by 43, which is an odd shape for a puzzle). Unsurprisingly such numbers were in the OEIS (and I didn't put them there): https://oeis.org/A071562 https://oeis.org/A071562.

27 points by ColinWright 5y ago

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.
      - 5y ago

madcaptenor 5y ago

Most large numbers can't be factored into nearly equal factors, if we take "nearly equal" to mean "differ by less than a factor of two". I called these "puzzle numbers" because they're reasonable numbers of pieces for a jigsaw puzzle to have, and wrote about it a couple years ago: https://gottwurfelt.com/2020/08/17/how-many-pieces-can-a-puzzle-have/ https://gottwurfelt.com/2020/08/17/how-many-pieces-can-a-puz... For example you could have a 299-piece puzzle (13 by 23) or a 300-piece puzzle (15 by 20) but not a 301-piece puzzle (this will only factor as 7 by 43, which is an odd shape for a puzzle). Unsurprisingly such numbers were in the OEIS (and I didn't put them there): https://oeis.org/A071562 https://oeis.org/A071562.