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

  • $\begingroup$ I edited your question to be more precise. If you disagree with my changes or I misunderstood something, feel free to change it back. $\endgroup$ – 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.)

| improve this answer | |

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.

     print K.modulus()
| improve this answer | |
  • $\begingroup$ 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 $\endgroup$ – per3naa Aug 25 '15 at 15:33
  • $\begingroup$ I don't think that you can have complex coordinates. I can't see how this can happen. $\endgroup$ – 111 Aug 26 '15 at 23:05
  • 1
    $\begingroup$ @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$. $\endgroup$ – 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}$

| improve this answer | |

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.