Factoring composite numbers into nearly equal factors
blog.plover.com
Factoring composite numbers into nearly equal factors
1–10 of 12 posts
Re: Factoring composite numbers into nearly equal factors
#2Here 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:
Re: Factoring composite numbers into nearly equal factors
#3Most 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-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.
Re: Factoring composite numbers into nearly equal factors
#4Here 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
I've added this to the article. Thanks very much for the reference.
Re: Factoring composite numbers into nearly equal factors
#5Here 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
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.
Re: Factoring composite numbers into nearly equal factors
#6Here 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
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 think it needs to be poly in the number of bits, not just the number, otherwise factoring would be poly, and it isn't.
Re: Factoring composite numbers into nearly equal factors
#7Earlier quoted context omitted.
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 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.
Re: Factoring composite numbers into nearly equal factors
#8Here 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
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.
Re: Factoring composite numbers into nearly equal factors
#9Earlier quoted context omitted.
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 s…
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| Then there exist L, R (either both integers or both half-integers) with L² - R² = n and |R| From which one can deduce:
R² L² - R² >= L² - (k²/4) √n
n >= L² - (k²/4) √n
L² L L If k If k (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).
Re: Factoring composite numbers into nearly equal factors
#10Earlier quoted context omitted.
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 s…
[deleted]