Understanding the elliptic curve equation by example

I'm trying to follow this tutorial and wonder how the author get the list of points in the elliptic curve. For example, why when you input x=1 you'll get y=7 in point (1,7) and (1,16)?

on intuitive level, I'll do:

x=1, 1^3+1+1 mod 23


= 3mod23 = 3 so why we get (1,7) & (1,16).

• What's wrong with the obvious: because $y^2=3\bmod23$ has two solutions: $y=7$ and $y=16$, as verified by $7^2\equiv49\equiv3\pmod{23}$ (the other follows by taking the opposite, $-7\bmod23=23-7=16$)?. If you want a method to solve that other than by trial and error, in the general case there's Tonelli-Shanks; or since here we have $23\equiv3\pmod4$ you can use $y=\pm3^{(23+1)/4}\bmod23$
– fgrieu
Jul 13, 2017 at 16:36
• ohhhh, got it. I totally ignored the y^2. so 7^2≡3mod23 & 16^2≡3mod23
As fgrieu already mentioned, you forgot that the $y$ term in the elliptic curve equation is squared, so for $x= 1$ you have $y^2 = 1^3 + 1 + 1 = 3 \text{ mod } 23$. In order to solve the congruence $y^2 = n \text{ mod } p$ (where $p$ is a prime) you can use the following algorithm (Tonelli-Shanks):
1. Factor the powers of $2$ out of $p-1$, so in your case write $p-1 = 22 = Q2^S = 11 * 2^1$
2. Pick a value $z$ that is not a quadratic residue modulo $p$ i.e. there exists no $x$ such that $z = x^2 \text{ mod } p$. I picked $7$ at random and verified it's not a quadratic residue via Euler's criterion ($7^{\frac{23-1}{2}} = 22 = -1 \text{ mod } 23$)
3. Set the following values (all calculations done modulo $p$): $$M \gets S(=1)$$ $$c \gets z^Q(7^{11}=22)$$ $$t \gets n^Q(3^{11}=1)$$ $$R \gets n^{\frac{Q+1}{2}}(3^{\frac{11+1}{2}}=16)$$
4. This step involves looping until $t = 1$, which in our case is already true going into this step, so we have $y = R = 16$ as one of our solutions. The other solution can be found by computing $p - R = 23 - 16 = 7$.
Hence we have the two solutions $y = 16, y = 7$ when $x = 1$, yielding the points $(1, 16), (1, 7)$ as expected.