Solving the factoring problem, easy

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.


James Harris