# Calculating $\mathbb F_{p^2}$-rational points of an elliptic curve defined over $\mathbb F_p$

How can I calculate points on an elliptic curve defined over $\mathbb F_p$, for example $y^2 \equiv x^3 + 1 \pmod p$, with coordinates in $\mathbb F_{p^2}$? (points might have complex number format in $\mathbb F_{p^2}$)

• I edited your question to be more precise. If you disagree with my changes or I misunderstood something, feel free to change it back. – yyyyyyy Aug 19 '15 at 18:53

The general case is that of field extension. Given a field $\mathbb{F}_q$ of $q$ elements (in your case, the field is $\mathbb{Z}_p$, the integers modulo a prime $p$), you want to define and do computations in a field $\mathbb{F}_{q^k}$ of $q^k$ elements for some integer $k > 1$. To do so, one first considers $\mathbb{F}_q[X]$ which is the ring of polynomials with coefficients in $\mathbb{F}_q$: a polynomial is the formal sum: $$A = \sum_{i=0}^{\infty} a_i X^i$$ for some values $a_i$ (the "coefficients") in the field $\mathbb{F_q}$, such that only a finite number of $a_i$ are distinct from $0$. The degree of the polynomial is the integer $n$ such that $a_n \neq 0$ but $a_i = 0$ for all $i > n$.

Polynomials can be added together, and multiplied together, in the natural way. If we define: \begin{eqnarray} A &=& \sum_{i=0}^{\infty} a_i X^i \\ B &=& \sum_{i=0}^{\infty} b_i X^i \\ \end{eqnarray} then the sum of $A$ and $B$ is: $$A + B = \sum_{i=0}^{\infty} (a_i+b_i) X^i$$ and the product is: $$AB = \sum_{i=0}^{\infty} \left(\sum_{j=0}^{i} a_j b_{i-j}\right) X^i$$

There is a well-defined Euclidian division of polynomials: given polynomials $A$ and $B$, with $B$ being non-zero (the "zero polynomial" is the polynomial whose coefficients are all equal to zero), then there exist unique polynomial $Q$ and $R$ such that $A = BQ + R$, and the degree of $R$ is strictly less than the degree of $B$. (For this definition to work, we formally define the zero polynomial to have degree $-1$.)

If we can compute additions and multiplications, and we have an Euclidian division, then we can define a modulo operation: "$A$ modulo $B$" is the value $R$ in the equation $A = BQ + R$.

Now let's choose an polynomial $M$ of degree $k$ in $\mathbb{F}_q[X]$. To make things simpler, we choose a unitary polynomial, i.e. such that its highest non-zero coefficient $m_k = 1$. We then define $\mathbb{F}_{q^k}$ to be the quotient of $\mathbb{F}_q[X]$ by $M$: this is the set of polynomials of degree strictly less than $k$, and all operations (additions and multiplications) are taken modulo $M$. In other words, when adding and multiplying polynomials, we do as described above, with the additional rule that $M$ is zero, i.e. $$X^k = \sum_{i=0}^{k-1} -m_i X^i$$

This defines a ring. The beauty of the construction is that IF the polynomial $M$ is irreducible in $\mathbb{F}_q[X]$ (meaning that there exists no polynomials $U$ and $V$ of degree strictly greater than $1$ and strictly lower than $k$ such that $M = UV$), then that ring is a field. Another additional (and unobvious) property is that the choice of $M$ does not actually matters much, in that all fields $\mathbb{F}_{q^k}$ are isomorphic to each other, i.e. they describe the same inner structure. This is why we may talk of "the" field $\mathbb{F}_{q^k}$.

The field $\mathbb{F}_{q^k}$ is called the field extension of $\mathbb{F}_q$ of degree $k$. We formally map elements of $\mathbb{F}_q$ to the polynomials of degree $0$ in $\mathbb{F}_{q^k}$, which allows us to say that $\mathbb{F}_q$ is a subset of $\mathbb{F}_{q^k}$.

In your specific case, let's see what the above becomes. Your base field $\mathbb{F}_q$ is $\mathbb{Z}_p$, the integers modulo a prime integer $p$. You want a field extension of degree $2$, so you need an irreducible polynomial $M$ of degree $2$. To make computations easier, you would prefer $M$ to be as "simple" as possible, i.e.: $$M = X^2 + \alpha$$ with $\alpha$ chosen such that multiplications by $\alpha$ are easy. You also need $M$ to be irreducible (since you want a field), which here means that $-\alpha$ must NOT admit any square root in $\mathbb{Z}_p$. A very common choice here is to choose $p$ such that $p = 3 \pmod 4$, because then we can set $\alpha = 1$. If you do that, then $M = X^2 + 1$. In application of the rules above, this defines $\mathbb{F}_{p^2}$ to consist in polynomials $A = a_1X + a_0$ for all values $a_0$ and $a_1$ in $\mathbb{Z}_p$, and the additions and multiplications are done "naturally" with the extra rule that $X^2 = -1$.

If instead of writing $X$ you call it $i$, then you get the same construction as complex numbers $\mathbb{C}$ from real numbers $\mathbb{R}$, and the easy computation rules that @Cryptostatis lists in his answer. There is, notably, a possible extra optimization when implementing: \begin{eqnarray} (a_0+ia_1)(b_0+ib_1) &=& (a_0b_0 - a_1b_1) + i(a_0b_1 + a_1b0) \\ &=& (a_0b_0 - a_1b_1) + i((a_0+a_1)(b_0+b_1) - a_0b_0 - a_1b_1) \end{eqnarray} That is, the product of two values in $\mathbb{Z}_{p^2}$, with the modulus $M = X^2+1$, can be computed with only three multiplications in $\mathbb{Z}_p$.

For further information on finite fields, and details on the construction of field extensions, the very classic read is A Course in Number Theory and Cryptography by Neal Koblitz.

(From your question, I suppose that you want to dabble in Weil and Tate pairings; thus, you need to be able to navigate through somewhat hairy mathematics, and Koblitz' book is almost a must-read for that. When you master field extensions, proceed with Ben Lynn's PhD thesis, which I found to be a nice read on that subject.)

I provide a specific example. Say $p=11.$ You want to find the points of the elliptic curve $y^2=x^3+1$ over the finite field $L=GF(p^2).$ Also set $K=GF(p).$ Then a defining polynomial of the quadratic extension $L/K,$ will be an irreducible quadratic polynomial over $K.$ Suffices to take $f(z)=z^2+7z+2.$ Now you have to take every element of $L$ as the $x-$coordinate and compute y-coordinate. For example set for $x-$ coordinate $x=z.$ Then we get the equation $y^2=z^3+1.$ But $$z^3+1=z(-7z-2)+1=-7z^2-2z+1=-7(-7z-2)-2z+1=$$ $$49z+14-2z+1=47z+15=3z+4.$$ On the other hand $(3z)^2=9z^2=9(-7z-2)=-63z-18=3z+4.$ So we get the points (in projective coordinates) $(z:3z:1),(z:-3z:1)=(z:8z:1).$ If you let $x$ runs in the set $L$ you will get all the points over $L$ (there are $144$ points).

In sagemath you can write the following code.

sage:p=11;K.<x>=GF(p**2,'a');
print K.modulus()
E1=EllipticCurve(K,[0,0,0,0,1])
E1.points()

• Thank you for your answer. still didn't get it how it would be complex number in the format you mentioned. I need points that have complex format specifically. thank you – per3naa Aug 25 '15 at 15:33
• I don't think that you can have complex coordinates. I can't see how this can happen. – 111 Aug 26 '15 at 23:05
• @111: In the field $GF(p^2)$, we often use a representation $ai + b$, where $i$ is one of the field elements with $i^2 = -1$ (and it turns out not to matter which, as they are isomorphic). In your representation, $i$ is one of two values $4z+3$ and $7z+8$. – poncho Aug 28 '15 at 12:41

If you use a prime $p \equiv 3 \pmod 4$, then an element from $\mathbb{F}_{p^2}$ can be written as $a+ib$, where one has the following rules of calculus:

$(a_1+ib_1)+(a_2+ib_2) = (a_1+a_2)+i(b_1+b_2)$ $(a_1+ib_1)\cdot(a_2+ib_2) = (a_1 a_2 - b_1 b_2)+ i (a_1 b_2+ a_2 b_1)$
$(a+ib)^{-1} = (a-i b) / (a^2+b^2)$

Sine $i^2 = -1$, those rules resemble arithmetic of the complex numbers.
Taking square roots is a bit more tricky, but you can use the fact that $\sqrt{x} = x^{(p+1)/4}$ in $\mathbb{F}_{p}$