Harristotelian Logic

Simple relations connect every integer factorization to an infinity of others as I have shown with simple congruences:

In the ring of integers given

x^2 = y^2 mod T and k = 2x mod T

it must be true that

(x+k)^2 = y^2 + S

where S = 2k^2 mod T

so one congruence of squares is connected to an infinity of others.

That can be used to factor in either direction, but I will focus on letting S be the target composite to be factored in this post.

If S has non-unit factors f_1 and f_2, such that S = f_1*f_2, then a non-trivial factorization is given by

x + k - y = f_1

and

x + k + y = f_2

so

2(x+k) = f_1 + f_2 and

all you need do is determine x and y, and choose k.

So the algorithm is that given a target S to be factored, choose a non-integer k, and find T, from

S - 2k^2 = 0 mod T, so if factor_pool = S - 2k^2, then you factor factor_pool, and loop through combinations of factors of factor_pool, using each combination as T.

Then you find x from x = 2^{-1} k mod T, and can then check

sqrt((x+k)^2 - 4S)

to see if it is an integer and if it is then

f_1 = (-(x+k) + sqrt((x+k)^2 - 4S))/2

but how do you pick k? Well it can be shown that

3k - f_1 - f_2 = 0 mod T

so if S is odd, then k cannot be even, unless you get lucky and 3k - f_1 - f_2 = 0. So k should be odd. Also, if k has 3 as a factor, and f_1 + f_2 does as well, then it is blocked from working unless S has 3 as a factor, so k should be coprime to 3.

Other than that any k can be chosen so it would make sense to choose k such that S - 2k^2 is a minimum with k even and not divisible by 3.

Oddly enough this may be a perfect factoring algorithm which would end considering the factoring problem being a hard problem, but that depends on there not being some other conditions which would stop a particular k from working, or some other reason that looping through the combination of factors of the factor_pool would not give a non-trivial factorization.

This method is more specific than my previous surrogate factoring methods going the other way where T is a target as with those it was not possible to prove that only a single k with some minimal qualifications should work.