Thursday, October 26, 2006

 

Generalized factoring idea

Factoring may be simpler than previously believed as consider the following generalized factoring idea:

With T the target composite:

x^2 - y^2 = 0 mod T

is how far researchers previously went, and that area is well-worked showing it difficult to factor T as T increases in size, but my research shows it to just be a primitive case of a more general solution found by using two additional variables, S and k, where

S - 2xk = 0 mod T

which allows you to now use quadratic methods as usual as you easily then have

(x+k)^2 = y^2 + S + k^2 + nT

where n is some non-zero integer, and notice, importantly, these generalized factoring equations default to the well-known ones with S=k=0.

But with S and k non-zero they indicate a factorization of S + k^2 + nT as the route to factoring T itself, as the general factoring method.

My previous postings in this area from a quirk of how I did the research used n=0, and that not surprisingly didn't work! The math doesn't know what T is if n=0, so you get random behavior, and objections raised against these ideas depend on that quirk of how I initially talked about it.

They have to as the idea includes previously known factoring methods, and to seem to fail there had to be a simple reason.

However, with n nonzero, thorough analysis of when the ideas shown here lead to a non-trivial factorization of a composite T do not show the normal rules, like indications that the size of T matters. I've just done a bit of analysis in this area and as of yet have found no indication that these ideas cannot be made practical, though I haven't done it myself, only having done initial theory.

But consider, all that I did in actuality was find a more generalized set of factoring equations, which include those typically used in previously known approaches when S=k=0.

No demonstrations to date have been given that this approach fails as previous arguments on Usenet centered on cases where for reasons having to do with how I derived the equations, initially I focused on n=0, disconnecting T itself in a key place, giving random behavior.
Turns out there is a simple way to consider the problem, which is to assume x, y and T with a non-trivial factorization such that

x^2 - y^2 = mT

where m is some non-zero integer.

Then my idea says you can take ANY non-zero residue modulo T, S and k, so let's keep it simple and let S = k = 1, and then I have

1 = 2x + jT

where j is some non-zero integer.

Now you can just add that to the previous with some minor changes to get

x^2 + 2x + 1 = y^2 + 1 + 1 + (m-j)T

so you have

(x+1)^2 = y^2 + 2 + (m-j)T

and you may be asking, but what are m and j?

Well, you can't pick them, oddly enough as all YOU can pick with this idea is m-j, which I call n above. So what does that mean exactly?

Well, go back to 1 = 2x + jT, and add in factors of T, like add 2T, and you can get

1 = 2(x+T) + (j-1)T

and have

1 = 2x* + j*T

so you can move modulo 2T, and shift x at will. Why 2T? Because with k=1, I can add and subtract T as I did only in multiples of 2T.

So let's say you pick n=1 above. If the math can shift by 2T so that it can find

1 = 2x* mod T

then you must factor T non-trivially. The math will find it if it is there and it's all about whether or not you can add and subtract 2T in such a way that m-j* = 1, or whatever you pick.

So the inability to pick m and j is crucial to understanding why this idea is so scary, as you can only pick their difference, giving the math the ability to shift modulo 2T.

This idea at this point is more than enough to merit serious consideration. The problem I fear is that the math field has become corrupted so mathematicians kind of just hope that if they call me enough names no one will notice that the emperor has no clothes when it comes to current ideas for Internet security.

That is, it's the protection by stupid blind ignorance, as if the world will just kind of, well, not notice that there may be this route to cracking RSA with simple mathematics, as long as mathematicians can just keep quiet long enough, and hope no one is watching or paying attention.





<< Home

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