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 (mod 5). To find the list of all the points you run through 0 < x <= 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 = (3x_1^2)(2y_1) -1mod p
for the new x and y:
x_3 = m^2 - x_1 - x_2 mod p
y_3 = m(x_1 - x_3) - y_1 mod 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 (mod 5) with point P(1, 3) and compute 2P?