0

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?

Cisco Saeed
  • 109
  • 1
    You have to take a look on Modular arithmetic course, the modulus in the exercise is $23$ so for example $7^2 = 49 \mod 23 = 3 \mod 23$ so there are two possible solution $7$ or $-7 = 23-7 \mod 23 = 16$.
    another example is for $y^2 =8$ then what are the square of $y \mod 23$ that give you $8$? a table of all possible squares $a \mod23$ for $a$ from $0$ to $22$ will give you an idea.
    since the modulus is prime you can compute the square roots using any algebra software efficiently for example SageMath     – Don Freecs Feb 04 '23 at 22:48
  • @DonFreecs Thanks for your answer and advice, sure I got the idea, it's all about Mod p –  Feb 05 '23 at 12:28

1 Answers1

2

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.

user93353
  • 466
  • 2
  • 18