JCSBimp's Hexagonal Orthogonal

Let m=pq, where p and q are unknown odd prime numbers, be an integer we wish to factor.

Let c=ceil(sqrt(m)) be the integer ceiling of the square root of m.

Evaluate r₁=c²-m. Evaluate r₂=(c+1)²-m.

If either r₁ or r₂ are perfect squares, this leads to a quick factorization due to c²-n² being equal to (c+n)(c-n) for all c, n, and we can exit the process. Otherwise, keep going.

Now determine values of positive integers a and b such that x²+ax+b will equal r₁ when x=0, and will equal r₂ when x=1. b will equal r₁ and a will equal r₂-(r₁+1).

With a and b thus determined, the least positive value of x that makes x²+ax+b a perfect square will be the value of x such that (c+x)²-m will also be a perfect square, from which m=(c+x)²-n² will give a simple factorization of m.

I suspect this might not be a simpler problem than factorization by known methods – it might be equivalent to trial of different values of x; i.e., using simple trial-candidates-based implementation of Fermat’s difference-of-squares method. But I do not yet know that for sure. Someone may have an algorithm to determine straightforwardly the values of x for which x²+ax+b is a perfect square, given a and b.