Wednesday, July 12, 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?





<< Home

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