Definition of the derivative on elliptic curves modulo n

Question

I'm trying to understand the point addition and point doubling operations on elliptic curves for the purposes of elliptic curve cryptography. I've read this Wikipedia article for the formulae:

https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

As well as this video for a derivation:

https://www.youtube.com/watch?v=XmygBPb7DPM

I now have a pretty good understanding of these operations for a regular elliptic curve. What confuses me, however, is how these formulae seem also to work when the curve is defined modulo some integer. Now the curve no longer looks like a smooth curve but rather a "cloud" of discrete points. We no longer have points on the "curve" for every $x$, but only for discrete integers. Moreover, the division operation (by $2p$) in point doubling is replaced by multiplication by the modular inverse.

So is there any kind of intuition why we can still apply the same formulae as in the continuous case? Why can the lambda still represent the derivative and why does the derivative even exist in this discontinuous case? In the continuous case, we can use these formulae and arrive at another point at the curve. In the modulo case, how do we even know that the new point satisfies the curve equation:

$$y^2 = x^3+ax+b$$

.. Now that we don't even find $y$ by taking the square root of the right hand side, but rather by finding its modular square root. All this seems very artificial, that is, we seem to simply replace all operators in the continuous case by their modulo "equivalents" and expect it to work.

Answer 1

I just noticed this good question and the fact that it has received no answer. I’m afraid that I find the comment of @Somos rather unhelpful, even misleading: the question is not all algebra, but rather if anything is all geometry. And to understand the situation, derivatives really are needed.

To understand things like this, you really must take out your pencil and paper and work some examples. I’ll work an example for you in characteristic $5$, and instead of writing (this)$\equiv$(that), I’ll write equalities, since I’ll be working in the field $\Bbb F_5$ with five elements. I’ll expect you to follow along with all my steps, pencil and paper in hand.

I’m going to take the curve $\mathcal E$ given by $Y^2=X^3+3X$. In addition to the point $\Bbb O$ at infinity, it has nine points in the finite plane, namely $(0,0),(1,2),(1,3),(2,2),(2,3),(3,1),(3,4),(4,1)$ and $(4,4)$.

I choose to double the point $P=(1,2)$. We need the equation of the line tangent to $\mathcal E$ at $P$, so we need to know the slope. Differentiate, as you learned how in Calculus: $$ \frac{dY}{dX}=\frac{3X^2+3}{2Y}=\frac{4X^2+4}Y\,, $$ and in particular at the point $(1,2)$ this has value $\frac{4+4}2=4$. So, we want the line $\mathcal L$of slope $4$ through our point. High-school algebra now, the equation is $Y=4X+3$. We know that this line is tangent to our curve, so has a double point of contact there, and since the curve is cubic, there must be exactly one other intersection. We take the two equations $Y^2=X^3+3X$ and $Y=4X+3$ and eliminate $Y$: $Y^2=(4X+3)^2=X^2+4X+4=X^3+3X$, giving $X^3+4X^2+4X+1=0$. This cubic must have a factor $(X-1)^2$, and by doing the division (or any other method) you see that $$ X^3+4X^2+4X+1=(X-1)^2(X+1)\,, $$ which says that the other intersection of $\mathcal L$ with $\mathcal E$ has $X$-coordinate equal to $-1=4$, and you get the other coordinate by using $Y=4X+3$, so the other intersection is $(4,4)$. That’s not $2P$, you have to take the negative of this, namely change the sign of the $Y$-coordinate.

Final result: $2P=(4,1)$.