Saturday, August 18, 2007

 

JSH: Solving the factoring problem

After the explanation of my current factoring research that I just posted I realized that wrapped up in this latest analysis is solution to the factoring problem.

It's fairly easy but as usual I'll post what I think it is to see if I made any mistakes:

Starting as usual with the key congruences:

y^2 = x^2 mod T

and

k = 2x mod T

I note that a solution must exist for those equations for any non-zero x coprime to T, as I worked out in detail in my prior post.

Using them I easily get

(x+k)^2 = y^2 + 2k^2 + n*T

where n is some non-zero integer, which I've also explained and now I can address the value of n--and solve the factoring problem.

As we know a solution to the difference of square that non-trivially factors T must exist, so assume you have that x, and some arbitrary n, can it be reached?

The answer is yes if it is even, because

k = 2x mod T

explicitly is k = 2x + m*T, where m is some non-zero integer, so I can always use

(k+/-a*T) = 2x + ( m+/-a)*T

and letting k* = k+/-a*T, I then have

(x+k*)^2 = y^2 + 2k*^2 + n*T

so if k=2, I can add or subtract as needed to reach ANY even n, so n needs to be even.

Notice that knowing how much is being added or subtracted from k to get k* is unimportant as you're looking at everything mod T, so with even n, and k=2, the size limit discussed in my prior post is the only block and over that size limit you are 100% guaranteed to factor T non-trivially, which solves the factoring problem.

Note: You are moving in multiples of k*T, as remember k = 2x mod T is first multiplied by k and then added back to the congruence of squares.

The factoring problem is done.





<< Home

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