Re: ECC point compression trick

Pubkeybreaker wrote:
Please tell me which one is the postive root and which one is the
negative?

Of course there is no notion of positive in a finite field, I don't see
what the problem here is. It sounds like all the person was really asking
for was for was a way to pick out a canonical square root of a value y,
so that taking the squareroot of y always yields the same thing back
every time. (This is by analogy to working in the reals, where we often
use "positivity" as a way to specify a canonical square root, more for the
canonical property rather than for anything special about being positive.)

Let ~ be the equivalence relation such that x ~ y iff x^2 = y^2. Pick one
representative for each resulting equivalence class (it doesn't really
matter how you do it). If you really want, we can arbitrarily call the
representative the "positive root". (If every equivalence class has size
two, we can arbitrarily call the other, non-representative the "negative
root".) It's an abuse of the term "positive", but if all you want is
to select out one particular square root as the canonical square root,
it works. It doesn't really matter that you don't have any meaningful
notion of "positive" in a finite field; you can still arrange that taking
sqrt(z) always gives you the representative of the equivalence class {x :
x^2 = z}, and thus always gives you the same thing back.

When working in Z/nZ where n is a Blum modulus, the square roots of y
have the property that there is exactly one square root of y that is
itself a square. One typically takes that particular square root as
the "canonical" square root. This yields the nice property that if you
start with any square, you can repeatedly take "canonical" square roots
and you won't ever get stuck.
.