1

If I take the following elliptic formula over a finite field of size $17$:

$$y^2 = x^3 + 2x + 3$$

The solutions for $x = 2$ would be $7$ and $10$.

Because

$7^2=49$ and $49 \equiv 15 \bmod 17$

$10^2=100$ and $100 \equiv 15 \bmod 17$

My question is when I take a number larger than $17^2$ I will still only get the solutions $7$ and $10$. For instance $24^2 = 576$ and $576 \equiv 15 \bmod 17$ and $24 \equiv 7 \bmod 17$.

Does this go on until $\infty$... OR does anything larger than $17$ just not exist

Niels
  • 131
  • 5
    You’re trying to run before you’ve learned to walk. You must familiarize yourself with the principles and methods of computation in and over finite fields. – Lubin Jan 14 '14 at 20:31
  • You may be interested in googling "Hensel's Lemma" – DonAntonio Jan 14 '14 at 21:08
  • @Lubin Well I am trying. Could you suggest any literature that might help. – Niels Jan 14 '14 at 21:23

1 Answers1

1

enter image description here

As you said, points $(x_1,y_1)=(2,7)$ and $(x_2,y_2)=(2,10)$ belong to the curve, plotted just above.

Because - e.g. - $24\equiv_{17}7$, then $(2,24)\equiv(2,7)$ belongs to the curve.

Keep in mind that domains of $x$ and $y$ have $17$ elements each and, hence, $17$ labels $0,1,\ldots,15,16$.

MattAllegro
  • 3,316