[svat]

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]

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).

[svat]

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.

[dmdox]

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)