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}$)
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 &gt; 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 &gt; n$.

Polynomials can be added together, and multiplied together, in the natural way. If we define:
\begin{eqnarray}
A &amp;=&amp; \sum_{i=0}^{\infty} a_i X^i \\
B &amp;=&amp; \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) &amp;=&amp; (a_0b_0 - a_1b_1) + i(a_0b_1 + a_1b0) \\
&amp;=&amp; (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.)