Harristotelian Logic

If you have a target composite T, and use

z^2 = y^2 + nT

where n is used to force z to be divisible by 3, then there will be an integer k such that

z = 3k/2.

But now find an integer x and odd prime p such that

x^2 = y^2 mod p

where also

2x = k.

So given k as defined before, you find an x that equals one half of it, and consider a prime p where

(k/2)^2 = y2 mod p.

Then it's trivial to show that

k^2 = 2^{-1}(nT) mod p

and, if f_1*f_2 = nT, then

f_1 = k mod p

and

f_2 = 2k mod p.

But that then shows that k, when a positive integer, must be greater than p, which is the crucial requirement. That is because

z = 3k/2

and

f_1 = k mod p

so if k is less than p, then f_1 = k, which contradicts with z having prime factors in common with k.

So how do I get the requirement on k?

Well given

x^2 = y^2 mod p and

2x = k, I multiply both sides of the latter by k and add to the first to get

x^2 + 2xk = k^2 + y^2 mod p

and then add k^2 to both sides to complete the square so that I have

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

and get back to my original equation with z = x+k, and nT = 2k^2 mod p.

Given that z = 3k/2, if I have integer factors f_1 and f_2, where

f_1*f_2 = nT

then

z = (f_1 + f_2)/2, so

k = (f_1 + f_2)/3.

The minimum positive integer k then is greater than or equal to 2sqrt(nT)/3 because that value is when f_1 = f_2.

Now then if you find a prime p less than the minimum positive value for k, where

2^{-1}(nT) mod p

is a quadratic residue modulo p, then the residue of k is found as

k^2 = 2^{-1}(nT) mod p

which follows from

nT = 2k^2 mod p.

So now you can search for k modulo p, but as you search up from the minimum possible k with the correct residue modulo p, you open up the minimum prime p, so, say, once you get to 10 times your original p, you find another prime p* that is 10 times the size of the previous one but still less than k for which

2^{-1}(nT) mod p*

is a quadratic residue, then you can now iterate upward from that point modulo that prime as well as the previous one. With only 10 primes used in this way, you would move up at least 10^100.

Which looks like a solution to the factoring problem.

Checking each k is easy enough, you just solve for z, with

z = 3k/2

and check to see if y is an integer, since y = sqrt(z^2 - nT).

That solution is trivially easy. There is not a real mathematician in the world who cannot trace out the steps of the proof.

The factoring problem is solved.