Introduction to Cryptography with Coding Theory, 3rd Edition

21.2 Elliptic Curves Mod p

If $p$ is a prime, we can work with elliptic curves mod $p$ using the aforementioned ideas. For example, consider

$$\begin{array}{cc}E:y^2\equiv x^3+4x+4& \left(\mathrm{mod}5\right)\text{.}\end{array}$$

The points on $E$ are the pairs $(x\text{,}y)$ mod 5 that satisfy the equation, along with the point at infinity. These can be listed as follows. The possibilities for $x$ mod 5 are 0, 1, 2, 3, 4. Substitute each of these into the equation and find the values of $y$ that solve the equation:

$$\begin{array}{ll}x\equiv 0⟹y^2\equiv 4& ⟹y\equiv 2\text{,}3(\mathrm{m}\mathrm{o}\mathrm{d}5)\\ x\equiv 1⟹y^2\equiv 9\equiv 4& ⟹y\equiv 2\text{,}3(\mathrm{m}\mathrm{o}\mathrm{d}5)\\ x\equiv 2⟹y^2\equiv 20\equiv 0& ⟹y\equiv 0\phantom{\text{,}3}(\mathrm{m}\mathrm{o}\mathrm{d}5)\\ x\equiv 3⟹y^2\equiv 43\equiv 3& ⟹\text{no solutions}\\ x\equiv 4⟹y^2\equiv 84\equiv 4& ⟹y\equiv 2\text{,}3(\mathrm{m}\mathrm{o}\mathrm{d}5)\\ x=\text{∞}⟹y=\text{∞}\text{.}\end{array}$$

The points on $E$ are $(0\text{,}2)\text{,}(0\text{,}3)\text{,}(1\text{,}2)\text{,}(1\text{,}3)\text{,}(2\text{,}0)\text{,}(4\text{,}2)\text{,}(4\text{,}3)\text{,}(\text{∞}\text{,}\text{∞})\text{.}$

The addition of points on an elliptic curve mod $p$ is done via the same formulas as ...