Thursday, March 29, 2007
Reversal with surrogate factoring
Abstracting to the gist of surrogate factoring I realized it says that for every factorization of a composite T, with difference of squares
x^2 = y^2 mod T
which of course is the same as
(x-y)*(x+y) = 0 mod T
and is for that reason a factorization, there is an alternate factorization of an integer S, where
S = (α + 1)k^2 mod T
and α and k are defined by
α*k = 2x mod T
as then trivially you can multiply both sides of that relation by k, add back to the original difference of squares, add k^2 to both sides and find
(x+k)^2 = y^2 + (α + 1)k^2 mod T
explaining the second factorization, as now you have a factorization of this alternate number using the same x, y and this extra variable k:
(x+k - y)*(x+k+y) = (α + 1)k^2 mod T
So for EVERY composite factorization of T using difference of square that algebra tosses a factorization of ANOTHER composite (α + 1)k^2 mod T back at you!!!
It's just been there all the time. There has just been another factorization out there all along with difference of squares and I call the second factorization the surrogate factorization.
But hey, that goes both ways! I like to use T as the target, and S as the surrogate, but what if you reverse the equations so that you pick some surrogate and factor it to see how easily you can factor the target T?
Equations then become
x^2 = y^2 mod S
and
α*k = 2x mod S
gives you
(x+k)^2 = y^2 + (α + 1)k^2 mod S
and now, of course, you'd want to choose
(α + 1)k^2 mod S = 0 mod T
and you can go explicit to start solving everything, so I have
α*k = 2x + u_1*S,
so α = (2x + u_1*S)/k, and
((2x + u_1*S)/k + 1)k^2 + u_2*S = 0 mod T, so
2xk + u_1*S*k + k^2 + u_2*S = 0 mod T
so you can collect to get
k^2 + (2x + u_1*S)k + u_2*S = 0 mod T
and now complete the square to get
(k + (2x + u_1*S)/2)^2 = (2x + u_1*S)^2/4 + u_2*S mod T
and now you have a fairly trivial way to solve for k, as u_1 and u_2 are integers of your choice, so you can, intriguingly enough, simply CHOOSE a quadratic residue of T, pick some S, factor it, get x, and then find u_1 and u_2 that will work!
What makes this reversal fascinating to me is that it turns the factoring problem on its head, where instead of searching for quadratic residues modulo T, like most major factoring methods work to do to solve the congruence of squares, you just pick one. You pick a quadratic residue of your target T, and use it and the surrogate factorization to get a difference of squares with your target, so then you should have a 50% chance of factoring your target with that choice, as then you just plug your solutions for k and α back into
(x+k)^2 = y^2 + (α + 1)k^2 mod S
as then also you will have an alternate factorization, the surrogate factorization
(x+k)^2 = y^2 mod T
as shown above with trivial algebra.
Remember people very trivial algebra that turns the factoring problem upside down.
If my suspicions are correct because many modern mathematicians willfully lie to the public, they will try their best to ignore this result, like they have with the previous surrogate factoring theory.
Or hey, they can surprise me—and do a press release—and then I'll apologize for saying they are willful con artists.
I don't think I'll be surprised, as I fear they will fight to the bitter end and the Math Wars will end nastily, unfortunately.
Do the press release people, and notify your governments. Or try the waiting game one last time, and prove to the world that every nasty thing I've said about you is true.
x^2 = y^2 mod T
which of course is the same as
(x-y)*(x+y) = 0 mod T
and is for that reason a factorization, there is an alternate factorization of an integer S, where
S = (α + 1)k^2 mod T
and α and k are defined by
α*k = 2x mod T
as then trivially you can multiply both sides of that relation by k, add back to the original difference of squares, add k^2 to both sides and find
(x+k)^2 = y^2 + (α + 1)k^2 mod T
explaining the second factorization, as now you have a factorization of this alternate number using the same x, y and this extra variable k:
(x+k - y)*(x+k+y) = (α + 1)k^2 mod T
So for EVERY composite factorization of T using difference of square that algebra tosses a factorization of ANOTHER composite (α + 1)k^2 mod T back at you!!!
It's just been there all the time. There has just been another factorization out there all along with difference of squares and I call the second factorization the surrogate factorization.
But hey, that goes both ways! I like to use T as the target, and S as the surrogate, but what if you reverse the equations so that you pick some surrogate and factor it to see how easily you can factor the target T?
Equations then become
x^2 = y^2 mod S
and
α*k = 2x mod S
gives you
(x+k)^2 = y^2 + (α + 1)k^2 mod S
and now, of course, you'd want to choose
(α + 1)k^2 mod S = 0 mod T
and you can go explicit to start solving everything, so I have
α*k = 2x + u_1*S,
so α = (2x + u_1*S)/k, and
((2x + u_1*S)/k + 1)k^2 + u_2*S = 0 mod T, so
2xk + u_1*S*k + k^2 + u_2*S = 0 mod T
so you can collect to get
k^2 + (2x + u_1*S)k + u_2*S = 0 mod T
and now complete the square to get
(k + (2x + u_1*S)/2)^2 = (2x + u_1*S)^2/4 + u_2*S mod T
and now you have a fairly trivial way to solve for k, as u_1 and u_2 are integers of your choice, so you can, intriguingly enough, simply CHOOSE a quadratic residue of T, pick some S, factor it, get x, and then find u_1 and u_2 that will work!
What makes this reversal fascinating to me is that it turns the factoring problem on its head, where instead of searching for quadratic residues modulo T, like most major factoring methods work to do to solve the congruence of squares, you just pick one. You pick a quadratic residue of your target T, and use it and the surrogate factorization to get a difference of squares with your target, so then you should have a 50% chance of factoring your target with that choice, as then you just plug your solutions for k and α back into
(x+k)^2 = y^2 + (α + 1)k^2 mod S
as then also you will have an alternate factorization, the surrogate factorization
(x+k)^2 = y^2 mod T
as shown above with trivial algebra.
Remember people very trivial algebra that turns the factoring problem upside down.
If my suspicions are correct because many modern mathematicians willfully lie to the public, they will try their best to ignore this result, like they have with the previous surrogate factoring theory.
Or hey, they can surprise me—and do a press release—and then I'll apologize for saying they are willful con artists.
I don't think I'll be surprised, as I fear they will fight to the bitter end and the Math Wars will end nastily, unfortunately.
Do the press release people, and notify your governments. Or try the waiting game one last time, and prove to the world that every nasty thing I've said about you is true.
# posted by James Harris @ 20:05 
