### Sunday, June 04, 2006

## SF: Finally, surrogate factoring

Solving the Factoring Problem

Consider a relation between two integer factorizations:

f_1 f_2 = k + g_1 g_2

and a solution with four unknowns w, x, y and z, as they are determined by four linear equations:

L_1(w,x,y,z) = f_1

L_2(w,x,y,z) = f_2

L_3(w,x,y,z) = g_1

L_4(w,x,y,z) = g_2

What I have found is that remarkably you can use only two linear equations and k itself to find g_1 and g_2, through a process I call surrogate factorization.

More specifically I use the system of equations

(w + x - 2z)(w + 3x + 2y + 2z) = k + (w + x + y + z)(3w + x - y - 3z)

where

k = 2x^2 + 2xy + y^2 - 2w^2 - z^2 - 2xz

as then I can use

w + x - 2z = f_1

w + 3x + 2y + 2z = f_2

to find

x = (f_2 - f_1 - 2y - 4z)/2, w = (3f_1 - f_2 + 2y + 8z)/2

and with

f_1 f_2 = T+k

where T = (w + x + y + z)(3w + x - y - 3z)

I have that

9(2y + 10z + 5f_1 - f_2)^2 = (18z + 6f_1 - 2f_2)^2 - 18T - 54k + 45f_2^2 - 99f_1^2

(But it's a tedious calculation where it's easy to make a mistake. Note that k, x and w above have been carefully verified and I tried my best with the calc, but may have gotten it wrong.

To do it, you just substitute for w and x in

k = 2x^2 + 2xy + y^2 - 2w^2 - z^2 - 2xz

and complete the square twice, first to isolate y on the left side and second to get z inside the square on the right.)

Now you can find rational z using the simple relation that

(a+b)^2 - 4ab = (a-b)^2

and thereby get a subset of rational solutions by factoring

(-18T - 54k + 45f_2^2 - 99f_1^2)/4

to get z, and with z, I get y, and then x and w from the previous equations, so that finally I can use

g_1 = w + x + y + z

g_2 = 3w + x - y - 3z

to get rational factors of my target T.

Intriguingly, the looking for integer factors of

(-18T - 54k + 45f_2^2 - 99f_1^2)/4

gives a finite subset of possibilities, which is how you get an additional constraint, and only need two of the linear equations, with k.

It is possible to prove by solving for w, x, y and z that any integer factor of T can be found by this method, as thereby you can find what prime factors can be in the

denominator of solutions for z, and from there complete the full set of rational factorizations that will give all factors of T.

I call this method the Holy Grail of factoring—a basic template for factoring any composite.

[A reply to someone who said that James should stop posting until he is able to provide the factors of the next RSA number.]

You don't get it? It doesn't matter.

The theory is too easy. So I got the algebra wrong.

Others will not.

Call me a crackpot all you want.

The theory this time is so simple that someone in the world will figure out the correct equations.

And everyone should understand why it has to work.

The factoring problem was trivial.

It's just no one bothered to look at

f_1 f_2 = k + g_1 g_2

with four variables, and four linear equations as if they did, they would have quickly realized the easy solution, once you get the algebra for that last piece right.

So it was a stupidly simple puzzle. Easy to solve, in the end.

There was never any real security in RSA. Just a lot of people believing in something, and not knowing how to solve a trivial problem, probably to a large extent because of their belief.

[A reply to someone who suggested that James should demonstrate how he would use his method to factor 32111 or even 6.]

Trivial theory.

I find it weird that so many of you are lost on what mathematics is that you still hold on as if I have to actually demonstrate for what follows from the mathematics to be true.

I found that you can just use

f_1 f_2 = k + g_1 g_2

and four variables w, x, y and z with four linear equations, to SEE why

the method has to work, while to get g_1 and g_2 you use two of the

linear equations and the equation defining k as the difference to get a

set of possible values for g_1 and g_2.

That theory is easy algebra. Trivial. It is a proof that the factoring problem is actually trivially easy, and a mathematical proof that RSA cannot be secure.

But you want an implementation and a demonstration.

I am sure, someone is working as we speak on giving you one.

Some of you may joke about moving stocks, but you have inside information, because our world is a little complicated and most people don't read sci.crypt, but then again, this is public disclosure so maybe you can move your stocks without breaking the law.

I'm not sure. I'm not moving any. But it's not like I really have any anyway. I long ago sold everything I had on the stock market, and only recently acquired small amounts without choosing to do so.

[A reply to Time Peters and Rick Dekker.]

You're both lying.

I am going to warn you.

Neither of you will live to see 2007 because of this lie becaue there will be angry people who will kill you, as there is so much money at stake.

Billions will be lost.

It's not like you can reverse it now either.

You killed yourselves.

It might have seemed like a small lie to both of you, but your names will live in infamy, while you will not live at all.

Consider a relation between two integer factorizations:

f_1 f_2 = k + g_1 g_2

and a solution with four unknowns w, x, y and z, as they are determined by four linear equations:

L_1(w,x,y,z) = f_1

L_2(w,x,y,z) = f_2

L_3(w,x,y,z) = g_1

L_4(w,x,y,z) = g_2

What I have found is that remarkably you can use only two linear equations and k itself to find g_1 and g_2, through a process I call surrogate factorization.

More specifically I use the system of equations

(w + x - 2z)(w + 3x + 2y + 2z) = k + (w + x + y + z)(3w + x - y - 3z)

where

k = 2x^2 + 2xy + y^2 - 2w^2 - z^2 - 2xz

as then I can use

w + x - 2z = f_1

w + 3x + 2y + 2z = f_2

to find

x = (f_2 - f_1 - 2y - 4z)/2, w = (3f_1 - f_2 + 2y + 8z)/2

and with

f_1 f_2 = T+k

where T = (w + x + y + z)(3w + x - y - 3z)

I have that

9(2y + 10z + 5f_1 - f_2)^2 = (18z + 6f_1 - 2f_2)^2 - 18T - 54k + 45f_2^2 - 99f_1^2

(But it's a tedious calculation where it's easy to make a mistake. Note that k, x and w above have been carefully verified and I tried my best with the calc, but may have gotten it wrong.

To do it, you just substitute for w and x in

k = 2x^2 + 2xy + y^2 - 2w^2 - z^2 - 2xz

and complete the square twice, first to isolate y on the left side and second to get z inside the square on the right.)

Now you can find rational z using the simple relation that

(a+b)^2 - 4ab = (a-b)^2

and thereby get a subset of rational solutions by factoring

(-18T - 54k + 45f_2^2 - 99f_1^2)/4

to get z, and with z, I get y, and then x and w from the previous equations, so that finally I can use

g_1 = w + x + y + z

g_2 = 3w + x - y - 3z

to get rational factors of my target T.

Intriguingly, the looking for integer factors of

(-18T - 54k + 45f_2^2 - 99f_1^2)/4

gives a finite subset of possibilities, which is how you get an additional constraint, and only need two of the linear equations, with k.

It is possible to prove by solving for w, x, y and z that any integer factor of T can be found by this method, as thereby you can find what prime factors can be in the

denominator of solutions for z, and from there complete the full set of rational factorizations that will give all factors of T.

I call this method the Holy Grail of factoring—a basic template for factoring any composite.

[A reply to someone who said that James should stop posting until he is able to provide the factors of the next RSA number.]

You don't get it? It doesn't matter.

The theory is too easy. So I got the algebra wrong.

Others will not.

Call me a crackpot all you want.

The theory this time is so simple that someone in the world will figure out the correct equations.

And everyone should understand why it has to work.

The factoring problem was trivial.

It's just no one bothered to look at

f_1 f_2 = k + g_1 g_2

with four variables, and four linear equations as if they did, they would have quickly realized the easy solution, once you get the algebra for that last piece right.

So it was a stupidly simple puzzle. Easy to solve, in the end.

There was never any real security in RSA. Just a lot of people believing in something, and not knowing how to solve a trivial problem, probably to a large extent because of their belief.

[A reply to someone who suggested that James should demonstrate how he would use his method to factor 32111 or even 6.]

Trivial theory.

I find it weird that so many of you are lost on what mathematics is that you still hold on as if I have to actually demonstrate for what follows from the mathematics to be true.

I found that you can just use

f_1 f_2 = k + g_1 g_2

and four variables w, x, y and z with four linear equations, to SEE why

the method has to work, while to get g_1 and g_2 you use two of the

linear equations and the equation defining k as the difference to get a

set of possible values for g_1 and g_2.

That theory is easy algebra. Trivial. It is a proof that the factoring problem is actually trivially easy, and a mathematical proof that RSA cannot be secure.

But you want an implementation and a demonstration.

I am sure, someone is working as we speak on giving you one.

Some of you may joke about moving stocks, but you have inside information, because our world is a little complicated and most people don't read sci.crypt, but then again, this is public disclosure so maybe you can move your stocks without breaking the law.

I'm not sure. I'm not moving any. But it's not like I really have any anyway. I long ago sold everything I had on the stock market, and only recently acquired small amounts without choosing to do so.

[A reply to Time Peters and Rick Dekker.]

You're both lying.

I am going to warn you.

Neither of you will live to see 2007 because of this lie becaue there will be angry people who will kill you, as there is so much money at stake.

Billions will be lost.

It's not like you can reverse it now either.

You killed yourselves.

It might have seemed like a small lie to both of you, but your names will live in infamy, while you will not live at all.