The question asks to prove the (true) fact that, in order to perform point addition $R\gets P+Q$ graphically on an Elliptic Curve over the field $\mathbb F_p$ of equation
$y^2\equiv x^3+a\,x+b\pmod p\tag{1}\label{fgr1}$
with $p$ suitably small (here $p=29$, $a=4$, $b=20$) and
$4\,a^3+27\,b^2\not\equiv0\pmod p\tag{2}\label{fgr2}$
we can (except in the special case¹ of $P$ and $Q$ equal or on the same vertical line) perform the geometric construction of $R$ per the figure
- Draw on a (black) square grid of side $p$ the points of the curve (blue dots) other than the neutral².
- Draw a red line that starts from $P$ parallel to and in the direction of $\overrightarrow{PQ}$.
- As soon as the line hits a point of the curve other than $Q$, call it $R'$; then on the vertical (purple) line going thru $R'$, find another point of the curve and call it the result $R$ of $P+Q$.
- If the red line hits a side, draw an horizontal or vertical (green) line from there to the opposite side; then from that intersection keep drawing the red line parallel to and in the direction of $\overrightarrow{PQ}$, and iterate to the above bullet.
After drawing the red line for a displacement of $d$ along the $x$ axis starting from $P$, and accounting for the wraparound on the sides, the pen drawing the red line has coordinates
$\begin{align}x&=(x_P+d)&\bmod p\tag{3}\label{fgr3}\\ y&=\left(y_P+d\,\frac{y_Q-y_P}{x_Q-x_P}\right)&\bmod p\tag{4}\label{fgr4}
\end{align}$
with the computations in $\mathbb R$. Justification: What's on the left of the $\bmod$ operator³ in $\eqref{fgr3}$ and $\eqref{fgr4}$ is the position of the pen having moven by $d$ along the $x$ axis if we did not wraparound on black edges. The $\bmod$ operators capture the effects of the wraparound.
The points on the red line with both coordinates an integer (including but not limited to any point of the curve) thus have a corresponding $d$ an integer, and verify
$(y-y_P)(x_Q-x_P)\equiv(x-x_P)(y_Q-y_P)\pmod p\tag{5}\label{fgr5}$
And any $(x,y)$ matching this equation would be on the red line if we kept drawing it indefinitely; $P$ would be reached when $d=p\,(x_Q-x_P)$ (or earlier).
It follows that our graphical search procedure for $R'$ hits a point of the curve (and thus terminates), and yields a point $R'$ which coordinates $(x,y)$ involves integers that verify $\eqref{fgr1}$ and $\eqref{fgr5}$. But we have not shown yet that $R$ obtained from $R'$ is the expected point (we have not ruled out that $R'=P$ or some other unwanted point of the curve).
An intuitive argument is that when we remove the $\bmod p$ from equations, and work in the field $\mathbb R$ instead of $\mathbb F_p$, $\eqref{fgr5}$ becomes the equation of the line going thru $P$ and $Q$ in the Euclidean plane (with coordinates in $\mathbb R$). Our graphical procedure that draws the red line and finds a third point on the curve that the line intersects is thus a mere translation⁴ in field $\mathbb F_p$ of the graphical construction of point addition on the curve with the same equation in the field $\mathbb R$, and must thus "work", in the sense of yielding a commutative group law on the set of curve points and neutral.
Alternatively, we can make an analytical proof that this graphical procedure terminates and yields the same $R$ as the usual formulas for point addition on the curve of equation $\eqref{fgr1}$ with $\eqref{fgr2}$, that is when $x_P\ne x_Q$
$$\begin{align}
\lambda&\gets(x_Q-x_P)^{-1}(y_Q-y_P)&\bmod p\tag{6}\label{fgr6}\\
x_R&\gets\lambda^2-x_P-x_Q&\bmod p\tag{7}\label{fgr7}\\
y_R&\gets\lambda(x_P-x_R)-y_R&\bmod p\tag{8}\label{fgr8}
\end{align}$$
Note: In this, all quantities are elements of $\mathbb F_p$, or equivalently integers in range $[0,p)$. In particular, $(x_Q-x_P)^{-1}$ is a modular inverse.
Proof sketch, which mostly⁴ parallels a possible demonstration of the point addition formulas for the same equation in the field $\mathbb R$:
- We analytically show that $\eqref{fgr1}$ and $\eqref{fgr5}$ are verified by $(x,y)\gets(x_R,(-y_R)\bmod p)$ computed per $\eqref{fgr6}$, $\eqref{fgr7}$, $\eqref{fgr8}$.
- The condition $\eqref{fgr2}$ allows to prove $x\ne X_P$ and $x\ne X_Q$.
- Thus the point with these coordinates $(x,y)$ is on the red line drawn indefinitely, and neither $P$ nor $Q$.
- When we eliminate $y$ from equations $\eqref{fgr1}$ and $\eqref{fgr5}$, we get a cubic equation in $x$ in the field $\mathbb F_p$. It thus has at most 3 distinct solutions. Two of these are $x_P$ and $x_Q$, and the third is the above $x$, neither $x_P$ nor $x_Q$.
- Since our graphic procedure start from $P$ and skips $Q$, it must reach a point with that $x$ before reaching $P$ again.
- Hence the $R'$ of our search procedure has the $x=x_R$ of $\eqref{fgr7}$
- Points of the curve on the same vertical line share the same $x$, thus the same $y^2\bmod p$ per the curve's equation. It follows that the $R$ graphically constructed has the coordinates $(x_R,y_R)$ of $\eqref{fgr7}$, $\eqref{fgr8}$, Q.E.D.
¹ This special case subdivides into
- $P\ne Q$, in which case $P+Q$ is the neutral².
- $P=Q$. One graphical construction chooses two distinct points $S$ and $S'$ on the same vertical line, both distinct from $P$, and computes $(P+S)+(P+S')$. When $S$ can be chosen on the same horizontal line as $P$, that simplifies drawing the red line for $P+S$. I know no more direct graphical analog to the "tangent" technique used for a curve in the field $\mathbb R$.
² The neutral is an extra point of the curve, not on the figure, often noted $\infty$ or $0$, such that for any point $S$, $S+\infty=S=\infty+S$.
³ The $\bmod$ operator has a canonical extension from $\mathbb Z$ to $\mathbb R$: we can define $u\bmod m$ with $u\in\mathbb R$ and $m\in\mathbb R_+^*$ as $v\in \mathbb R_+$ with $v<m$ and $(u-v)/m\in\mathbb Z$.
⁴ The only operational difference is that for the Elliptic Curve in the field $\mathbb R$ we must draw the red line in both directions, when that's optional here because we're in a finite set and the line ultimately wraparounds back to $P$.
