Complex Numbers on Elliptic Curves & Usage in Tate Pairing

Question

I'm working with understanding the internals of the Tate Pairing. I was going through an example of the curve $E: y^2 = x^3 + 3x$ over $\mathbb{F_{11}}$. The author is showing the computation of $e(P,Q)$, where $P=(1,9)$ and $Q = \phi (P) = (10,9i)$ using Miller's Algorithm. Through this algorithm, the author chose a point $Q' = (6,6)$ and then computes $S = Q + Q' = (8+7i, 10+6i)$. This is where I'm having an issue, I can't seem to determine how the complex addition of points occurs in elliptic curves, and I'm looking for an explanation in the usage for the Tate pairing.

Paper being referenced : http://www.win.tue.nl/~bdeweger/downloads/MT%20Martijn%20Maas.pdf , Section 4.3.1

Answer 1

Fix a field $k$. Consider the polynomial $x^2 + 1$ in $k[x]$. If $x^2 + 1$ is irreducible over $k$, then obviously the quotient $k[x]/(x^2 + 1)$ is also a field, of $\#k^2$ elements if $k$ is finite. Note that $x^2 + 1 \equiv 0 \pmod{x^2 + 1}$, so $x^2 \equiv -1 \pmod{x^2 + 1}$; hence if we take any linear polynomials $f_0 = a_0 x + b_0$ and $f_1 = a_1 x + b_1$, we can work out the product modulo $x^2 + 1$ by the standard rules of arithmetic, substituting $-1$ wherever we see $x^2$:

\begin{align} f_0 \cdot f_1 &\equiv (a_0 x + b_0) \cdot (a_1 x + b_1) \\ &\equiv a_0 a_1 x^2 + a_0 b_1 x + b_0 a_1 x + b_0 b_1 \\ &\equiv a_0 a_1 \cdot (-1) + a_0 b_1 x + b_0 a_1 x + b_0 b_1 \\ &\equiv (a_0 b_1 + b_0 a_1) x + b_0 b_1 - a_0 a_1 \pmod{x^2 + 1}, \end{align}

which, as it happens, is exactly the same arithmetic as for the familiar complex numbers, because $\mathbb C \cong \mathbb R[x]/(x^2 + 1)$ can be constructed exactly this way. Drawing on the analogy, we name the indeterminate variable $i$ rather than $x$ for the polynomials in $\mathbb F_{11}[i]$ so that we can write $i^2 = -1$ in the field $\mathbb F_{11^2} \cong \mathbb F_{11}[i]/(i^2 + 1)$.