1
$\begingroup$

Here's my issue and someone can help me understand it so I can program it correctly.

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 hexidecimal 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 it's most significant bit and add 1 if the Y point is odd. Therefore, one can think of the compressed point being 2*X+B(B is the bit we added if it 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 GF(p). The following is from my spec which confuses me

If p is prime and congruent to 3 mod 4, one of it's square roots is z^((p+1)/4) mod p and the other is p-z^((p+1)/4) mod 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?

I tried to be very detailed to express my difficulty. Thanks for any help

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
0
$\begingroup$

My educated guess is that $z=x^3+ax+b$. After all, $y$ satisfies $y^2=z$.

The reason as to why that formula works comes from Fermat's little theorem. If $u\not\equiv0\pmod p$, then we have $u^{p-1}\equiv1\pmod p$. Because we are working in $GF(p)$ where equality is defined via congruence modulo $p$ I keep it simpler and write this as $u^{p-1}=1$ for all $u\in GF(p), u\neq0$.

Here $z=y^2$, so $z^{(p-1)/2}=y^{p-1}=1$. This means that $$ (z^{(p+1)/4})^2=z^{(p+1)/2}=z^{(p-1)/2}z=1\cdot z=z. $$ In other words $z^{(p+1)/4}$ is one of the square roots of $z$. The other is then $-z^{(p+1)/4}$ or, if you prefer, $p-z^{(p+1)/4}$.

So for example with $p=11$ we have $(p+1)/4=3$. The above calculation means that IF $y\in GF(11)$ has a square root in $GF(11)$ then $y^3$ is one of the square roots. Let's check $z=7$. We have $$ z^3=7^3=7^2\cdot7=49\cdot7=5\cdot7=35=2. $$ But $2$ is not a square root of $7$ modulo $11$. This simply means that $7$ has no square root in $GF(11)$. Let's try $z=5$. We have $$ z^3=5^3=125=4\in GF(11). $$ This time the luck was with us. Indeed, $4^2=16=5$.

Not all elements of $GF(p)$ have square roots in there.

Improve this answer
$\endgroup$