Saturday, May 13, 2006


Solution of the factoring problem

Here is a post with the corrected derivation.

I know it will probably seem strange to now live in a world where a problem previously thought extremely difficult has now been shown to be trivially easy, but mathematics is a wonderful discipline because it's not about what you believe, but about what is proven.

It is a world of absolutes, and absolute truth.

It is bizarre beyond belief that one of the supposedly hardest problems in mathematics, is trivially easy--if you know how to solve it--but 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

k2 + 2kx + x2 - 1 - 8nkT - 8cT = 0

and collecting with respect to the k's I have

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

and completing the square gives

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


(k + x-4nT)2 + x2 - 1 - 8cT - x2 + 8xnT - 16n2 T2 = 0

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

(k + x-4nT)2 = 1 + 8cT + 16 n2 T2 - 8nTx

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 + 16n2 T2)/8nT)


k = 4nT - x + sqrt(1 + 8cT + 16n2 T2 - 8nTx)

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,

(I am not as certain now as the success rate may be much higher.)

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.

Amazing but true. It is the answer to the problem stepped out simply enough.

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.

I found a way where the mathematics looks for integers, as it "knows" that is the answer you want, so it just pops out the answer.

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

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.

<< Home

This page is powered by Blogger. Isn't yours?