Tuesday, July 11, 2006
Factoring and residues
Can you figure out something wrong with the following?
Start with the simple:
x^2 - y^2 = S - 2*x*k
You can solve for x and y in terms of the other variables easily as that is just
x^2 + 2*x*k + k^2 = y^2 + S + k^2
so
x+k = sqrt(y^2 + S + k^2)
and finding y is just a matter of factoring (S+k^2)/4.
But get this, now I just let
x^2 - y^2 = 0 mod T
then
S - 2*x_res*k = 0 mod T
where I put in x_res as I don't know x, so I'm using its residue.
So x_res = x mod T, and I can solve for k, assuming 2, S and x are coprime to T, with
k = S*(2*x_res)^{-1} mod T
where (2*x_res)^{-1} is the modular inverse of (2*x_res) mod T.
So just pick some x_res and S, and find k, which now allows calculation of y, and x.
Of course there will exist and x and y such that
x^2 - y^2 = 0 mod T
for any x_res you choose, which is trivial to prove.
So it looks like there is this almost impossible to believe simple answer to it all.
So what's wrong with the above?
Start with the simple:
x^2 - y^2 = S - 2*x*k
You can solve for x and y in terms of the other variables easily as that is just
x^2 + 2*x*k + k^2 = y^2 + S + k^2
so
x+k = sqrt(y^2 + S + k^2)
and finding y is just a matter of factoring (S+k^2)/4.
But get this, now I just let
x^2 - y^2 = 0 mod T
then
S - 2*x_res*k = 0 mod T
where I put in x_res as I don't know x, so I'm using its residue.
So x_res = x mod T, and I can solve for k, assuming 2, S and x are coprime to T, with
k = S*(2*x_res)^{-1} mod T
where (2*x_res)^{-1} is the modular inverse of (2*x_res) mod T.
So just pick some x_res and S, and find k, which now allows calculation of y, and x.
Of course there will exist and x and y such that
x^2 - y^2 = 0 mod T
for any x_res you choose, which is trivial to prove.
So it looks like there is this almost impossible to believe simple answer to it all.
So what's wrong with the above?