# Find points that are on two elliptic curves in $F_p$

I have some basic cryptography question but I don't know if my calculations are not overcomplicated and if there's some simpler solution. Following algorithm is explained here.

## Problem

There are two elliptic curves in $$F_5$$ with equations:

a) $$y^2 = x^3 + 2x + 1 \pmod{5}$$

b) $$y^2 = x^3 + x + 1 \pmod{5}$$

Find points that are in these two eliptic curves.

My approach is to determine points on these eliptic curves separately and then check for duplicates.

## Determining quadratic residue in $$\mod{5}$$

For every value in $$\mod{5}$$ calculate square for it, so

$$(\pm 1)^2 \pmod{5} = 1 \\ (\pm 2)^2 \pmod{5} = 4 \\ (\pm 3)^2 \pmod{5} = 9 \pmod{5} = 4 \\ (\pm 4)^2 \pmod{5} = 16 \pmod{5} = 1 \\$$

So our quadratic residue set is $$QR = \{1, 4 \}$$

## Determining points in a)

Equation is: $$y^2 = x^3 + 2x + 1 \pmod{5}$$

Let's build table:

1. In column $$x$$ we have all possible $$x$$.
2. In second column we calculate curve equation.
3. In third column we check if value is quadratic residue. So we check if its in $$QR$$. There is also option to check this with Euler theorem. For $$y=3$$ we check if $$y^{(p-1)/2} \equiv 1 \pmod{p}$$ so $$3^2 \equiv 1 \pmod{5}$$ is false because $$3^2 \pmod{5} = 4$$.
4. For all quadratic residues we calculate square roots. We can get them from step where we determined quadratic residues. For example we have $$1$$ for $$1^2$$ and $$4^2$$. So $$1$$ and $$4$$ are square roots of $$1$$.

So points on this elliptic curve are:

$$(0, 1)$$, $$(0, 4)$$, $$(1, 2)$$, $$(1, 3)$$, $$(3, 2)$$, $$(3, 3)$$

## Determining points in b)

Equation is: $$y^2 = x^3 + x + 1 \pmod{5}$$

Let's build table:

So points on this eliptic curve are:

$$(0, 1)$$, $$(0, 4)$$, $$(2, 1)$$, $$(2, 4)$$, $$(3, 1)$$, $$(3, 4)$$, $$(4, 2)$$, $$(4, 3)$$.

## Result

Points $$(0, 1)$$ and $$(0, 4)$$ are on these two functions.

### Checking if correct

I've found website that generate points for given EC. Solution that I've found is correct. Is there faster way to found these points?

### EC b)

Since you are working on the same field for both the curves. To get the common points $$(x_0,y_0)$$ that lie on both the curves, you just need to to equate the following (think in terms of intersection of two curves) \begin{align*} y_0^2 =x_0^3+2x_0+1 &\equiv x_0^3+x_0+1 \pmod{5}\\ x_0 & \equiv 0 \pmod{5}. \end{align*} Thus $$x_0=0$$. Now this gives us that $$y_0^2 \equiv 1 \pmod{5}$$, which has only two solutions, namely $$y_0=1,4$$. Thus the common points are $$(0,1)$$ and $$(0,4)$$ and $$\color{blue}{\text{the point at infinity } \mathcal{O}}$$.