Harristotelian Logic

It is bizarre beyond belief that one of the supposedly hardest problems in mathematics, is trivially easy--if you know how to solve it--and in this post I will step through a trivial solution to the factoring problem.

Earlier I noted a way to use quadratic residues to find m as a congruence relationship to factor with

sqrt(1 + 8*mT)

where the idea of looking mod some particular n, goes back to Fermat and later Gauss, which shows you how old this way of looking at things is.

Since m = (r-1)*(8*T)^{-1} mod n, where n is an odd natural of your choosing coprime to T--the target to be factored--and r is some quadratic residue of n, where I was just picking r=4.

So you can let

c = (r-1)*(8*T)^{-1) mod n

to have explicitly

m = kn + c

where k is to be determined.

But, it must be true that sqrt(1+8*mT) for a solution is a natural equal to k plus some number, which I will call x, so I have

(k+x)^2 = 1 + 8(kn + c)T

and expanding and collecting to the left side I have

k^2 + 2kx + x^2 - 1 - 8nkT - 8cT = 0

and collecting with respect to the k's I have

k^2 + 2(x-4nT)k + x^2 - 1 - 8cT = 0

and completing the square gives

k^2 + 2(x-4nT)k + (x-4nT)^2 + x^2 - 1 - 8cT - (x-rnT)^2= 0

so

(k + x-4nT)^2 + x^2 - 1 - 8cT - x^2 + 2xnT - n^2 T^2 = 0

and simplifying further and collecting everything outside the square to the right side gives

(k + x-4nT)^2 = 1 + 8cT + n^2 T^2 - 2nTx

but notice that c because it is defined as

c = (r-1)*(8*T)^{-1) mod n

can be an infinite number of possible values based on adding or subtracting multiples of n, but you can change c without changing m, by incrementing k, as

m = kn + c

so if you subtract n from c, you can add 1 to k, so that m does not change.

e.g. m = (k-1)n + c-n

but by not changing m, you don't change k+x, but if you are incrementing k, then you must be decrementing x, and you can do that to the point that x=0.

Logically then the solution to the factoring problem is

x = floor((1+8ct + n^2 T^2)/2nT)

and

k = 4nT - x + sqrt(1 + 8cT + n^2 T^2 - 2nTx)

with N = sqrt(1 + 8(kn + c)T), giving a non-trivial factor of T, from N-1 or N+1, 50% of the time, where remember,

c = (r-1)*(8*T)^{-1) mod n

and r is any quadratic residue modulo n, and n is a natural number of your choosing, so you have a complete solution to the factoring problem.

So why must it work? Well, consider that with some natural number k, to have some integer x, it just must be that x can be decremented in the way I described, forcing a 0, so there is this way of figuring out integer solutions.

Oddly enough, it also must be true that only one m exists for any given quadratic residue r mod n.

The 50% comes in because the mathematics doesn't distinguish between "trivial" or "non-trivial" factorizations.

The equations outlined here are a complete solution to the factoring problem and represent my SECOND solution to that problem.

My previous solution is just a lot more complicated using what I call surrogate factoring.

This second method though, is trivial enough even for humans to understand.

You people have been calling hard, something so easy it almost brings me to tears contemplating it.

I wonder what is wrong with you.