### Saturday, May 13, 2006

## JSH: Why factoring solution works

I've been going back and forth for days with what I now am certain is a simple solution to the factoring problem, as in you just plug and chug as they say, and out pops the answer a very high percentage of the time, and I can't find a damn thing wrong with the argument.

The math is simple, but the idea that something believed for so long to be very difficult, is not, is very hard.

So I keep going over the idea, over and over again, trying to figure out what must be wrong, because so many people thought the factoring problem was hard.

I can't find anything wrong.

I did something different by looking at solutions to

sqrt(1+8mT)

where T is the target, and m is selected by quadratic residue modulo n, where n is some odd natural coprime to T, of your choosing.

So I have m = kn + c, where c is the residue mod n, and k is a number to be determined to solve the factoring problem.

Then I did something very clever, as I let

k+x = sqrt(1+8T(kn+c))

where x is just some number, and now there is something weird you can do, as though I want c to be a residue, presumably less than n, but greater than 0, that is not mathematically required, so I can have

k'+x' = sqrt(1+8T(k'n + c'))

where k'+x' = k+x, and k'n + c' = kn + c

as I can subtract n from kn, and add it to c, so I have explicitly

(k+1)+(x-1) = sqrt(1+8T((k+1)n + c-n))

and the math is none the wiser, as in it can't just decide that the c I'm using is not something mod n, so this route actually forces the mathematics to show you how to pick only integers, as if you keep incrementing k, you are DECREMENTING x, and, of course, at some point then x=0.

But when you solve for k, you can solve for the x=0 case, getting the answer.

There is a lot of interesting mathematics in there, but the big deal now will not be about the mathematics but about the factoring problem being solved.

The answer is bizarrely simple considering that for over ten years RSA has been in use, when the answer is such a trivial one to factoring numbers:

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

and

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

The one tricky part is that

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

so you have to pick n, which has to be odd and coprime to T, for the modular inverse to be guaranteed to exist, and you also have to pick r, a quadratic residue of n.

Who knew that such a seemingly hard problem requiring huge amounts of computer resources and efforts of hundreds of people worldwide could be reduced to something trivial enough to give to a kid to program for homework?

It is amazing how powerful mathematics can be.

Some of you have not a clue what mathematics is, or just how powerful it can be.

I want some of you to consider how weak some people try to make it.

They fight me, but their fight just forced my hand here.

By using social forces they could convince people of things not true, but what happens when the truth is forced?

Things break. And it's the fault not only of the people who lied to you, and convinced you, but your fault for believing, and believing in them, against mathematical proof.

Mathematical proof is not about opinion, politics, or what makes you feel good.

And it doesn't care about your bank account.

The math is simple, but the idea that something believed for so long to be very difficult, is not, is very hard.

So I keep going over the idea, over and over again, trying to figure out what must be wrong, because so many people thought the factoring problem was hard.

I can't find anything wrong.

I did something different by looking at solutions to

sqrt(1+8mT)

where T is the target, and m is selected by quadratic residue modulo n, where n is some odd natural coprime to T, of your choosing.

So I have m = kn + c, where c is the residue mod n, and k is a number to be determined to solve the factoring problem.

Then I did something very clever, as I let

k+x = sqrt(1+8T(kn+c))

where x is just some number, and now there is something weird you can do, as though I want c to be a residue, presumably less than n, but greater than 0, that is not mathematically required, so I can have

k'+x' = sqrt(1+8T(k'n + c'))

where k'+x' = k+x, and k'n + c' = kn + c

as I can subtract n from kn, and add it to c, so I have explicitly

(k+1)+(x-1) = sqrt(1+8T((k+1)n + c-n))

and the math is none the wiser, as in it can't just decide that the c I'm using is not something mod n, so this route actually forces the mathematics to show you how to pick only integers, as if you keep incrementing k, you are DECREMENTING x, and, of course, at some point then x=0.

But when you solve for k, you can solve for the x=0 case, getting the answer.

There is a lot of interesting mathematics in there, but the big deal now will not be about the mathematics but about the factoring problem being solved.

The answer is bizarrely simple considering that for over ten years RSA has been in use, when the answer is such a trivial one to factoring numbers:

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

and

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

The one tricky part is that

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

so you have to pick n, which has to be odd and coprime to T, for the modular inverse to be guaranteed to exist, and you also have to pick r, a quadratic residue of n.

Who knew that such a seemingly hard problem requiring huge amounts of computer resources and efforts of hundreds of people worldwide could be reduced to something trivial enough to give to a kid to program for homework?

It is amazing how powerful mathematics can be.

Some of you have not a clue what mathematics is, or just how powerful it can be.

I want some of you to consider how weak some people try to make it.

They fight me, but their fight just forced my hand here.

By using social forces they could convince people of things not true, but what happens when the truth is forced?

Things break. And it's the fault not only of the people who lied to you, and convinced you, but your fault for believing, and believing in them, against mathematical proof.

Mathematical proof is not about opinion, politics, or what makes you feel good.

And it doesn't care about your bank account.