Earlier quoted context omitted.
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 woul…
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.