Roots in modulo field

Question

I have a point $(X,Y)$ on an elliptical curve $E(a,b)$ where $a=-3$ and $B$ is a large number that is in hexadecimal from -51BD. To compress this point oficially in a program, we know that every $X$ on the curve has two $Y$'s, one even and one odd. Therefore, we only need to store whether the corresponding $Y$ point we are storing is even or odd. So to store the point $(X,Y)$ now, we shift $X$ ridding of its most significant bit and add $1$ if the $Y$ point is odd. Therefore, one can think of the compressed point being $2 \cdot X+B$ ($B$ is the bit we added to tell if $Y$ was odd or even) since the multiplication by $2$ is implied because of the shift. I understand this completely. It's recovering the original point that has me confused.

Since a point on the curve is given by the equation $y^2=x^3+ax+b$, we can find square roots officially in $\mathrm{GF}(p)$. The following from my spec is what confuses me.

If $p$ is prime and congruent to $3$ mod $4$, one of its square roots is $z^{(p+1)/4} \bmod p$ and the other is $p-z^{(p+1)/4} \bmod p$. How would I solve this? What is $z$?

For example, I know how to extract the $x$ point so let's say I simplify the right side of the equation to be $7$ and $p$ is $11$. Would I be trying to solve for the square root that's equal to $7$ mod $11$?

Answer 1

You want to find a point $(X,Y)$ on an elliptic curve $y^2 = x^3 + ax + b$ knowing only $X$ and a single bit indicating whether $Y$ is even or odd. To find $Y$, you use the relation defining the curve: you know that $Y^2 = X^3 + aX + b$ since the point is on the curve. So you compute $X^3 + aX + b$ using your value of $X$ and the public parameters $a, b$, and you want to find values of $Y$ such that $Y^2$ is equal to that value.

If the modulus $p$ is congruent to $3$ mod $4$, that's very easy to do: for any $z$, the square roots of $z$, if they exist, are $\pm z^{(p+1)/4} \bmod{p}$. Indeed, suppose $z$ has a square root, say $a$. Let $g$ be a primitive root mod $p$, and let $a = g^x$. Then $z = (g^x)^2 = g^{2x}$. In turn,

$$(z^{(p+1)/4})^2 = z^{(p+1)/2} = (g^{2x})^{(p+1)/2} = (g^x)^{p+1} = (g^x)^{p-1}g^{2x} = g^{2x} = z$$

which shows that $z^{(p+1)/4}$ is indeed a square root of $z$.

Answer 2

If p is prime and congruent to 3 mod 4, one of its square roots is z(p+1)/4modp and the other is p−z(p+1)/4modp. How would I solve this? What is z?

If the elliptic curve equation is given by $y^2 = x^3 + ax + b$, to find the value of $y$ you would need to find the square root of the right hand side of the equation, meaning that $z = x^3 + ax + b$ in this case.

You would solve this by substituting in all of the parameters that you know -- $p$ is an elliptic curve parameter (the order of the Galois field $GF(p)$), and you have $a$ and $b$ as defined in your question.

Would I be trying to solve for the square root that's equal to 7 mod 11?

It's a little more accurate to say that you would be trying to solve for $y$ (or the two values of $y$) such that $y^2 \equiv 7 \bmod 11$.