I'm having a hard time understanding the elliptic curve encryption. One thing thing I don't understand is listing all the points on the curve mod p. Suppose I have the following elliptic curve: $y^2 = x^3 + 2x + 3 \pmod 5$. To find the list of all the points you run through $0 < x \leq 4$ and solve for $y$.
I know the output is the following:
x = 0 => $y^2 = 3$ => no solution mod 5
x = 1 => $y^2 = 6$ = 1 => y = 1,4 mod 5
x = 2 => $y^2 = 15$ = 0 => y = 0 mod 5
x = 3 => $y^2 = 36$ = 1 => y = 1,4 mod 5
x = 4 => $y^2 = 75$ = 0 => y = 0 mod 5
So the points are: (1,1) (1,4) (2,0) (3,1) (3,4) (4,0) and the point at infinity. But I have no idea what is happening here, for example at x=1 solving $y^2$ becomes 6 (mod 5) is one. But why does it say y = 1 and 4 for x=1?
I'm also having trouble understanding point doubling, I'm using the following algorithm:
$$m \equiv (3x_1^2)(2y_1) -1 \pmod p$$
for the new x and y:
$$x_3 = m^2 - x_1 - x_2 \pmod p$$
$$y_3 = m(x_1 - x_3) - y_1 \pmod p$$
Though this doesn't seem to work. Can someone give me an example of point doubling for e.g. the following equation $y^2 = x^3 + 2x + 1 \pmod 5$ with point P(1, 3) and compute 2P?