# Understanding elliptic curve encryption

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:

1. compute m:

m = (3x_1^2)(2y_1) -1mod p

2. 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?

-
You do not have enough familiarity with modular arithmetic to tackle Elliptic Curves (much less Elliptic Curve Encryption or other forms of Elliptic Curve Cryptography), if you do not understand that $y=4$ is a solution to $1\equiv y^2\pmod 5$. Hint: apply the definition of $a\equiv b\pmod c$, which is that $c$ divides $b-a$. –  fgrieu Oct 1 '13 at 6:52
Thank you, well I do have a basic understanding of modular arithmetic, but you are right, allthough I was mostly confused by the notation, I do have a better understanding now of what is happening. I see now that 1 and 4 are solutions to 1 = y^2 (mod 5). –  SilverTear Nov 6 '13 at 22:56
$1=y^2\pmod 5$ IS a confusion in notation. Use either $1\equiv y^2\pmod 5$ or $1=y^2\bmod 5$, the former meaning that $y^2-1$ is a multiple of $5$, the later that the remainder of the division of $y^2$ by $5$ is $1$. Notice that $6\equiv y^2\pmod 5$ is true, but $6=y^2\bmod 5$ is false. –  fgrieu Nov 7 '13 at 10:32