Saturday, November 21, 2009


JSH: But is quadratic residue idea new?

Finding a result is one thing but often I wonder afterwards, why is this result new? Now I'm in pondering mode as I consider something so trivially simple that it seems weird if it's NOT previously known.

Because of the way congruences work, it's possible to do something interesting with quadratic residues, where I've simplified from the heavy machinery of the full idea, to make things understandable, and now it looks like I'm grabbing certain equations from a hat, but at least it should be easily understood.

Imagine you have k^2 = q mod p, where p is an odd prime.

And now take the equations:

f_1 = k mod p and f_2 = 2k mod p

And let T = f_1*f_2, so T = 2k^2 mod p, and I can see k^2 in there, so k^2 = 2^{-1}*T mod p, which means that

q = 2^{-1}*T mod p, and T = 2q mod p. Easy.


z^2 - y^2 = T, then (z-y)(z+y) = T, so I have a factorization, and in fact I have simply enough:

z = (f_1 + f_2)/2, so I can substitute with f_1 and f_2 above, and get f_1 + f_2 = 3k mod p, so

z = 3k/2 mod p

and I have the implication that the factorization of T is connected with the value of k, and I have finally:

k = 3^{-1}(f_1 + f_2) mod p, and T = 2q mod p

when k^2 = q mod p.

So this simple approach has connected finding k, when k^2 = q mod p, with factoring T, where T = 2q mod p.

I'm guessing that the probability of it working is roughly 1/k.

But is this idea new? And what might be serious problems with it? Can it work well?

<< Home

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