Reversal with surrogate factoring
- From: jstevh@xxxxxxxxx
- Date: 29 Mar 2007 17:05:33 -0700
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 = (alpha + 1)k^2 mod T
and alpha and k are defined by
alpha*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 + (alpha + 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) = (alpha + 1)k^2 mod T
So for EVERY composite factorization of T using difference of square
that algebra tosses a factorization of ANOTHER composite (alpha +
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
alpha*k = 2x mod S
gives you
(x+k)^2 = y^2 + (alpha + 1)k^2 mod S
and now, of course, you'd want to choose
(alpha + 1)k^2 mod S = 0 mod T
and you can go explicit to start solving everything, so I have
alpha*k = 2x + u_1*S,
so alpha = (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 alpha back into
(x+k)^2 = y^2 + (alpha + 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.
James Harris
.
- Follow-Ups:
- Re: Reversal with surrogate factoring
- From: Bob Terwilliger
- Re: Reversal with surrogate factoring
- Prev by Date: Re: Looking for Rijndael javascript code
- Next by Date: Re: Reversal with surrogate factoring
- Previous by thread: fs module or kernel recompile
- Next by thread: Re: Reversal with surrogate factoring
- Index(es):