Harristotelian Logic

Given

x^2 = y^2 mod T

where T is a non-zero integer, introducing k = 2x mod T, you can easily solve to find

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

so with S = 2k^2 mod T, you have a second difference of squares.

But what if S is your target composite to be factored?

Then S - 2k^2 = 0 mod T, so by some choice of k, you have T as a factor of S - 2k^2.

Then x = 2^{-1} k mod T, gives you x.

It can be shown that only for certain cases then will y exist as an integer, such that all congruences are satisfied and that if S = p_1*p_2 that case is equivalent to

2(x+k) = p_1 + p_2 or 2(x+k) = p_1 - p_2.

And then it is trivial to factor S now through a difference of squares.

Here is an example. Let the target composite to be factored be 77, so S = 77.

Looking for the smallest S - 2k^2, I take floor(sqrt(77/2)) = 6, so k = 6 gives me a minimum, so

S - 2k^2 = 77 - 72 = 5.

So T = 5. Now x = 2^{1}*6 mod 5 = 3*6 mod 5 = 3.

Then x+k = 9, and p_1 + p_2 = 18, so 2(x+k) = p_1 + p_2, and you can non-trivially factor by solving the quadratic formula as

m^2 + 18 + 77 = (m+7)(m+11).

So the algorithm that follows naturally is with a target S, let k = floor(sqrt(S/2)), then you factor

S - 2(floor(sqrt(S/2))^2

to get T, looping through its factors, and solve for x, using x = 2^{-1} k mod T, and then check

sqrt(((x+k)/2)^2 + 4*S)

to see if it is an integer and if it is, check to see if you have a non-trivial factorization of your target composite S.

Notice this technique can be recursive, as for a MAXIMUM for T you have sqrt(S/2), while it can be much smaller than that, so you have progressively smaller numbers to factor than your target.

There must exist an x for the given k that will work as

x = (p_1+p_2)/2 - k

while the only question then that remains is, how often will x < T, work, as it did with my example above, or can you have cases where abs(x)>T?

If so that could be a problem with this method, otherwise it is guaranteed to non-trivially factor.