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 \pmod 5$.  To find the list of all the points you run through $0 &lt; 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:


compute $m$:

$$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?
Note: For $y^2 \equiv x^3 + ax + b$, you want $$m\equiv(3x^2+a)*(2y)^{-1}$$ which is a shortcut that only makes sense once you understand how elliptic curves work.

&quot;Why does it say y=1 and 4 for x=1?&quot;

Like you said, plug in &amp; solve: $$y^2 \equiv 1^3 + 2(1) + 3 \equiv 6 \equiv 1\space(mod\space5)$$
Ask yourself &quot;Is there a square such that it is $\equiv 1 \space(mod\space 5)$?&quot;
$$1^2\equiv1 \space \space and\space\space 4^2\equiv16\equiv1\space (mod \space5).$$
This means (1,1) and (1,4) are points on the discrete version (mod 5) of the curve.
If we weren't working (mod 5), plugging in 1 would give us (1,2) and (1,-2), which are points on the continuous version of the elliptic curve.
Below on the left is the continuous version of an arbitrary elliptic curve; on the right is what happens when you start working mod a number.


Example: Find 2P on the curve $E: y^2 \equiv x^3 + 2x + 3 \space(mod\space5)$ where P = (1,3)

2P = (1,3) + (1,3).  When adding two points on an elliptic curve, there are two cases:
Case 1: The points are not the same: Find the line that includes both of the points on the curve.  This line will have a third point on the curve.  Find that point and reflect about the x-axis to have the final point.
Case 2: The points are the same: Find the line tangent to our point on the curve.  This line will intersect the curve at one more point.  Find that point and reflect about the x-axis to have the final point.
Now what is the line tangent to (1,3) on E?
Use implicit differentiation (simple calculus):
$$dy/dx = (3x^2 + 2)/(2y)$$.
Now at our point (1,3): $$dy/dx = 5/6 = 5*6^{-1} (mod \space5)$$
It is easy to see (and find) that $6^{-1} \equiv 1 \space(mod\space 5)$
So m = 5 is the slope for our line tangent to (1,3): $$L: y-3 = 5(x - 1)$$
So $$y = 5x - 2.$$
Now where else do E and L intersect?
We have

$E: y^2 \equiv x^3 + 2x + 3 \space(mod\space5)$

$L: y = 5x - 2$


Plug L into E: $$(5x-2)^2 \equiv x^3 + 2x + 3$$
Expand: $$25x^2 - 20x + 4 \equiv x^3 + 2x + 3$$
There is a useful algebraic property for cubic polynomials that is fun and not hard to prove:  The summation of the polynomial's roots equal the negative of the $x^2$ term's coefficient.  That is,
$$\sum roots = -(coeff.\space of\space x^2\space term)$$
So in rearranging the polynomial further, we care only about the $x^2$ terms:
$$0 \equiv x^3 - 25x^2 ...$$
We already added (1,3) to itself, so it must be that 1 is a root of multiplicity 2.
$$1 + 1 + r_3 = -(-25) = 25$$ implies the last root is 23.  Recall we are working (mod 5) though, so our last root is 23 $\equiv 3$
Now plug $r_3$ into our linear equation: $$y = 5(3) - 2 = 13 \equiv 3\space(mod\space5)$$
Reflect
Lastly, reflect our point (3,3) about the x-axis to get (3,-3).  Recall again we're working (mod 5), so add the modulus to -3 until is it in the range $[0,4]$.
$\therefore$ 2P = (3,2)