Factoring composite numbers into nearly equal factors(blog.plover.com)
blog.plover.com
Factoring composite numbers into nearly equal factors
https://blog.plover.com/math/finding-factors.html
11 comments
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
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.
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.
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) 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).
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) 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).
In the meantime, I wrote this up in (too much elementary) detail: 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.
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.
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)
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]
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.
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
N is 256-bit a sample number.
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
N is 256-bit a sample number.
I've added this to the article. Thanks very much for the reference.
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.