Monday, June 26, 2006
SF: Tandem factorization, factoring problem solved?
I have the theory, and while I've not worked out the equations in detail, I feel confident enough to say, the factoring problem is done, as a hard problem.
Remember I finally came up with
S = (k_1*sqrt(x) + k_2*sqrt(y))*(k_3*sqrt(x) + k_4*sqrt(y))
and
T = (k_1*sqrt(x) - k_2*sqrt(y))*(k_3*sqrt(x) - k_4*sqrt(y))
which means that
S - T = 2*(k_2*k_3 + k_1*k_4)*sqrt(xy)
and
S+T = 2*k_1*k_3*x + 2*k_2*k_4*y
notice that to be integers, sqrt(xy) must be a factor of S-T, and the point of this method is to look for integer solutions to all the variables.
Here's why.
It's trivial to show that with S = f_1*f_2 and T = g_1 * g_2
2*sqrt(x)*k_1 = f_1 + g_1
2*sqrt(y)*k_2 = f_1 - g_1
2*sqrt(x)*k_3 = f_2 + g_2
2*sqrt(y)*k_4 = f_2 - g_2
and what's remarkable here is that with over a century of methods focusing on just one number to factor, where you tend to end up with maybe g_1 + g_2 or g_1 - g_2, when T is your target, here by simply using TWO NUMBERS, in a tandem factorization, the algebra just tosses up a route to factoring both, trivially.
Why is it trivial?
Because when you use squares for x and y that work, then you have 4 variables left with two equations, and rather trivial Diophantine methods for solving those out to get the finite set of integer solutions.
More specifically, you focus on k_1 and k_2 or k_3 and k_4, solving for them using your two equations, as then you get a ratio with the remaining two variables.
e.g.
k_1 = F_1(k_3, k_4)/G_1(k_3, k_4)
k_2 = F_2(k_3, k_4)/G_2(k_3, k_4)
where the F's and G's are functions of the remaining k's.
>From that equation it is trivial to solve out for the finite set of integer values that will work.
So the factoring problem is simply solved by a bit of lateral thinking:
Don't just factor one number, but factor two at a time.
The algebra for the tandem factorization gives up solutions without forcing you to search through as large a space as focusing on one.
It's a counter-intuitive thing that factoring two numbers at a time would break the problem.
But that's how easy problems become hard:
To get to the solution, you have to think outside the box, and do the unexpected.
Factoring problem is done. Deny it if you wish. Shouldn't take long for the news to travel though.
<Quote>
> Here, I'll hand them to you for the x=y=1 case:
> k_1 = (k_3*(S+T) - k_4*(S-T)) / d
> k_2 = (k_3*(S-T) - k_4*(S+T)) / d
> where:
> d = 2*(k_3 + k_4)*(k_3 - k_4)
> Do you truly have any idea how to go about finding integer solutions to
> those efficiently? Didn't think so, and bluffing isn't good enough.
</Quote>
Here's how you do it.
k_3 + k_4 = h_1, so
k_3 + k_4 = 0 mod h_1
k_3*(S+T) - k_4*(S-T) = 0 mod h_1
and you solve out for k_3 or k_4 by, for instance, multiplying the first equation by (S+T) and subtracting.
Here you see why using x=y=1 is a trivial case as notice then h_1 is a factor of S.
Next you use k_3 - k_4 = h_2, so
k_3 - k_4 = 0 mod h_2
k_3*(S+T) - k_4*(S-T) = 0 mod h_2
and you have that h_2 is a factor of T.
Now use another case besides x=y=1, and watch it work.
Oh yeah, once you get h_1 and h_2, of course, then you have k_3 and k_4.
As, for instance,
k_3 = (h_1 + h_2)/2
and now all anyone has to do is use something other than x=y=1.
If I'm wrong, post it! See if again you find that h_1 or h_2 has to be a factor of T.
But the problem with current math society is that is a social society.
You people lack comprehension of what mathematics is.
To you it's what you believe to be true.
But I say, mathematics is what's proven to be true.
The mathematical community today has a lot of power to convince, and from what I've seen, it is religious in its ability to fight against mathematical proof.
So this may still take a while.
Notice for those of you who thought you were doing something important with your involvement in the mathematical community, if you were fighting me, you were wrong.
You were fighting against civilization itself.
People like me have fought for the truth against people like you for millennia.
Remember I finally came up with
S = (k_1*sqrt(x) + k_2*sqrt(y))*(k_3*sqrt(x) + k_4*sqrt(y))
and
T = (k_1*sqrt(x) - k_2*sqrt(y))*(k_3*sqrt(x) - k_4*sqrt(y))
which means that
S - T = 2*(k_2*k_3 + k_1*k_4)*sqrt(xy)
and
S+T = 2*k_1*k_3*x + 2*k_2*k_4*y
notice that to be integers, sqrt(xy) must be a factor of S-T, and the point of this method is to look for integer solutions to all the variables.
Here's why.
It's trivial to show that with S = f_1*f_2 and T = g_1 * g_2
2*sqrt(x)*k_1 = f_1 + g_1
2*sqrt(y)*k_2 = f_1 - g_1
2*sqrt(x)*k_3 = f_2 + g_2
2*sqrt(y)*k_4 = f_2 - g_2
and what's remarkable here is that with over a century of methods focusing on just one number to factor, where you tend to end up with maybe g_1 + g_2 or g_1 - g_2, when T is your target, here by simply using TWO NUMBERS, in a tandem factorization, the algebra just tosses up a route to factoring both, trivially.
Why is it trivial?
Because when you use squares for x and y that work, then you have 4 variables left with two equations, and rather trivial Diophantine methods for solving those out to get the finite set of integer solutions.
More specifically, you focus on k_1 and k_2 or k_3 and k_4, solving for them using your two equations, as then you get a ratio with the remaining two variables.
e.g.
k_1 = F_1(k_3, k_4)/G_1(k_3, k_4)
k_2 = F_2(k_3, k_4)/G_2(k_3, k_4)
where the F's and G's are functions of the remaining k's.
>From that equation it is trivial to solve out for the finite set of integer values that will work.
So the factoring problem is simply solved by a bit of lateral thinking:
Don't just factor one number, but factor two at a time.
The algebra for the tandem factorization gives up solutions without forcing you to search through as large a space as focusing on one.
It's a counter-intuitive thing that factoring two numbers at a time would break the problem.
But that's how easy problems become hard:
To get to the solution, you have to think outside the box, and do the unexpected.
Factoring problem is done. Deny it if you wish. Shouldn't take long for the news to travel though.
<Quote>
> Here, I'll hand them to you for the x=y=1 case:
> k_1 = (k_3*(S+T) - k_4*(S-T)) / d
> k_2 = (k_3*(S-T) - k_4*(S+T)) / d
> where:
> d = 2*(k_3 + k_4)*(k_3 - k_4)
> Do you truly have any idea how to go about finding integer solutions to
> those efficiently? Didn't think so, and bluffing isn't good enough.
</Quote>
Here's how you do it.
k_3 + k_4 = h_1, so
k_3 + k_4 = 0 mod h_1
k_3*(S+T) - k_4*(S-T) = 0 mod h_1
and you solve out for k_3 or k_4 by, for instance, multiplying the first equation by (S+T) and subtracting.
Here you see why using x=y=1 is a trivial case as notice then h_1 is a factor of S.
Next you use k_3 - k_4 = h_2, so
k_3 - k_4 = 0 mod h_2
k_3*(S+T) - k_4*(S-T) = 0 mod h_2
and you have that h_2 is a factor of T.
Now use another case besides x=y=1, and watch it work.
Oh yeah, once you get h_1 and h_2, of course, then you have k_3 and k_4.
As, for instance,
k_3 = (h_1 + h_2)/2
and now all anyone has to do is use something other than x=y=1.
If I'm wrong, post it! See if again you find that h_1 or h_2 has to be a factor of T.
But the problem with current math society is that is a social society.
You people lack comprehension of what mathematics is.
To you it's what you believe to be true.
But I say, mathematics is what's proven to be true.
The mathematical community today has a lot of power to convince, and from what I've seen, it is religious in its ability to fight against mathematical proof.
So this may still take a while.
Notice for those of you who thought you were doing something important with your involvement in the mathematical community, if you were fighting me, you were wrong.
You were fighting against civilization itself.
People like me have fought for the truth against people like you for millennia.
# posted by James Harris @ 20:37 
