1
$\begingroup$

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).

enter image description here

$\endgroup$
  • 4
    $\begingroup$ 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$ $\endgroup$ – fgrieu Jul 13 '17 at 16:36
  • $\begingroup$ ohhhh, got it. I totally ignored the y^2. so 7^2≡3mod23 & 16^2≡3mod23 $\endgroup$ – adhg Jul 13 '17 at 16:38
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.