3
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ He's working over a quadratic extension, and the formulas work exactly the same as over any finite field. $\endgroup$ – Watson Ladd Jun 1 '13 at 19:40
  • 3
    $\begingroup$ Watson is correct. Here's the example you mention spelled out in Sage. $\endgroup$ – Samuel Neves Jun 1 '13 at 20:06
2
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.