Harristotelian Logic

Here's a simpler and more reliable version of my latest factoring idea, with T the target composite to be factored, start with the following congruences:

x^2 - y^2 = 0 mod T

S = 2*x*k mod T

The rest is trivially easy, as then you have

x^2 = y^2 mod T, and adding the second equation in gives

x^2 + 2*x*k = y^2 + S mod T

so I can complete the square with

x^2 + 2*x*k + k^2 = y^2 + S + k^2 mod T

and here's where I go differently than before as I focus on y to get

y^2 = (x+k)^2 - S - k^2 mod T

and now you can factor to solve for x and y, but here it's a little tricky, as they are meant to be residues modulo T, so you solve for x+k by picking some S and k, and some n so that you have the explicit

y = sqrt( (x+k)^2 - S - k^2 + n*T) mod T

where I stuck the mod T on the end to remind to take the residue modulo T, for y, and also you have to do the same internally in the calculation of x, which is done by factoring

S+k^2 - n*T

where since you can pick n, it probably would make sense to pick n=1.

This approach solves the problems with my earlier one focusing on x, where I was enthralled with the modular inverse and you'd pick S and x_res, where x_res = x mod T.

Once you've solved for x and y, you just plug back into the first congruence, so you'd check x+y and x-y for factors in common with T.

And that is the solid approach, which I don't like as much as the other route, but at least it doesn't have the problems of the other route in terms of sometimes not being modulo T.