How to get $y_1$ and $y_2$ values from $y^2=x^3+ax+b$ in elliptic curve

Question

I am studying Elliptic curve and I am trying to solve the $y_1$ and $y_2$ values as in this document: https://www.site.uottawa.ca/~chouinar/Handout_CSI4138_ECC_2002.pdf

As in Page 2 I can find $y^2$ but in some points I can not understand why when $y^2=3$ then $y_1=7$ how to get it?

I can Understand that $y^2=16$ it's obviously $\sqrt{16} = 4$ but if $y^2=8$ or $3$ or $6$ don't know how to get $y_1$?

I don't know what I am missing?

Answer 1

since, it's $\bmod 23$, the list of possible values $x$ can have are $[0, 1, 2, 3, ...., 22]$.

If you try each value of $x$, $x=7$ & $x=16$ are the only 2 values where $y^2 = 3$.

In python

for y in range(23):
    x = y**2 % 23
    if x == 3:
        print("y = " + str(y))

This will print

y = 7
y = 16

In number theory, square roots are called Quadratic Residues. If $a = b^2$, then $a$ is a quadratic residue. You have to learn the basis of Congruences in Elementary Number Theory & also Finite Fields in Abstract Algebra before you go on to Elliptic Curves over Finite Fields.