### Tuesday, January 18, 2005

## Factoring problem, solved

I am increasingly certain that I've solved the factoring problem.

That is a bold claim to add to previous bold claims of mine, but here in THIS post I'll give the underlying theory as it's very basic, and direct you to a site where you can download a rough, and somewhat flawed, but still good enough to show the idea, prototype factoring program, which implements some of the theory.

I'll explain why I say some of the theory in just a bit.

My work boils down to the analysis of a system of equations:

a_1 x + b_1 = f_1

a_2 x + b_2 = f_2

a_1 b_2 + a_2 b_2 = A

a_1 a_2 x^2 + Ax + b_1 b_2 = f_1 f_2

where to match the variables in my initial paper

y = a_1 a_2, T = f_1 f_2, and j^2 = - b_1 b_2.

(Here b_1 b_2 is a negative number so j is still an integer.)

I have a rather complex looking solution in the paper, but remarkably you can encompass it by solving the first three equations for key variables:

a_1 = A(b_1 - f_1)/(b_1 f_2 + b_2 f_1 - 2b_1 b_2)

and

x = (b_1 f_2 + b_2 f_1 - 2b_1 b_2)/A

which shows that you can actually factor simply by cycling through the factors of j and T, while my focus in the program is on cycling through the factors of T.

All together you then get the factors of your target M, as

M^2 = j^2 + T, so

a_1 a_2 x^2 + Ax + b_1 b_2 = f_1 f_2

is

a_1 a_2 x^2 + Ax - M^2 = 0

so x is a factor of M.

The idea may seem pathetically simple, but that is because you are programmed to believe that the factoring problem is hard. It is not.

I have just shown you in a few lines how to factor an arbitrary non-zero positive integer M in polynomial time.

Many of you are programmed to believe that mathematics must be abstruse and difficult to work. You are wrong. The factoring solution I've presented here while looking extremely simple can work and is simple because the PROBLEM is simple.

I have demonstration code, which is rough as I threw something together, to test out my own theory, and hopefully to be more convincing. That code implements a VERSION of my own theory, as I don't factor both j and T, but only T, as j gets background factored by the mathematics.

If you watch it factoring and spitting out primes (though it also mislabels some as prime and can't factor some easy numbers...rough version remember) then you can at least see that something is happening here worth investigating further.

In the hopes of convincing

http://groups.yahoo.com/group/sufactor/

It is CRITICAL that the information be taken seriously as soon as possible so that some other method can be used for Internet security, and quickly implemented.

Time is a factor.

That is a bold claim to add to previous bold claims of mine, but here in THIS post I'll give the underlying theory as it's very basic, and direct you to a site where you can download a rough, and somewhat flawed, but still good enough to show the idea, prototype factoring program, which implements some of the theory.

I'll explain why I say some of the theory in just a bit.

My work boils down to the analysis of a system of equations:

a_1 x + b_1 = f_1

a_2 x + b_2 = f_2

a_1 b_2 + a_2 b_2 = A

a_1 a_2 x^2 + Ax + b_1 b_2 = f_1 f_2

where to match the variables in my initial paper

y = a_1 a_2, T = f_1 f_2, and j^2 = - b_1 b_2.

(Here b_1 b_2 is a negative number so j is still an integer.)

I have a rather complex looking solution in the paper, but remarkably you can encompass it by solving the first three equations for key variables:

a_1 = A(b_1 - f_1)/(b_1 f_2 + b_2 f_1 - 2b_1 b_2)

and

x = (b_1 f_2 + b_2 f_1 - 2b_1 b_2)/A

which shows that you can actually factor simply by cycling through the factors of j and T, while my focus in the program is on cycling through the factors of T.

All together you then get the factors of your target M, as

M^2 = j^2 + T, so

a_1 a_2 x^2 + Ax + b_1 b_2 = f_1 f_2

is

a_1 a_2 x^2 + Ax - M^2 = 0

so x is a factor of M.

The idea may seem pathetically simple, but that is because you are programmed to believe that the factoring problem is hard. It is not.

I have just shown you in a few lines how to factor an arbitrary non-zero positive integer M in polynomial time.

Many of you are programmed to believe that mathematics must be abstruse and difficult to work. You are wrong. The factoring solution I've presented here while looking extremely simple can work and is simple because the PROBLEM is simple.

I have demonstration code, which is rough as I threw something together, to test out my own theory, and hopefully to be more convincing. That code implements a VERSION of my own theory, as I don't factor both j and T, but only T, as j gets background factored by the mathematics.

If you watch it factoring and spitting out primes (though it also mislabels some as prime and can't factor some easy numbers...rough version remember) then you can at least see that something is happening here worth investigating further.

In the hopes of convincing

**someone**willing to help I have put put up a Yahoo! Group with my paper and some rudimentary code:http://groups.yahoo.com/group/sufactor/

It is CRITICAL that the information be taken seriously as soon as possible so that some other method can be used for Internet security, and quickly implemented.

Time is a factor.