Trace function

Target : to embed plaintext to points in elliptic curve

What to do first : solving quadratic equation of the elliptic curve.

Problems : a quadratic equations only has a solution when the Trace of c is 0

Example:
E=y^{2}+xy=x^{3}+x^{2}+1

by converting the right-hand side to a simple form, say f\left (x \right ) , then bring that over to the left-hand side to become :
y^{2}+xy+f\left (x \right )=0

Now let
y = xz

then substitute it to the previous equation so it becomes:
\left (xz \right )^{2}+x^{2}z+f\left (x \right )=0

Multiply the entire equation by x^{-2} , so we get:
z^{2}+z+c=0

where:
c=f\left (x \right ).x^{-2}

Once we know the Trace\left (c \right )=0 , we can solve for z . It turns out z+1 is also a solution. So let z be one solution and z{}' be another solution. After we find one solution, the other one is trivial. After the two solutions are recovered, then our data can be embedded on the curve.

[rewrite from this book]

Advertisements