How to calculate Trace function for a point on an elliptic curve

Question

I encountered trouble with calculating Tr (trace function) for points on an elliptic curve in polynomial basis ( $GF(2^m), m = 431$). Maybe there are any assumptions that can simplify and allow efficiently to calculate Tr operation? I used the Seroussi approach to decompress points but it seems like I need some basic knowledge.

Answer 1

For a point $p = (x, y)$ on a curve $E(F_{q^k})$, where $q$ is prime and $k$ is the embedding degree of $E$, the trace map is defined by $$ \mathbf{Tr}(p) = \sum_{i=0}^{k - 1}(x^{q^i}, y^{q^i}). $$

I am not sure how that maps to curves with a polynomial basis, though.

There is a very good discussion of the r-torsion and the trace map in section 4.1 of Craig Costello's book Pairings for Beginners, which is very similar to section 2.3.1 of his PhD thesis.

Answer 2

Let $E$ be an elliptic curve defined over $F_q$, and let $\#E(F_q ) = q +1−t$. In this case, $t$ is called the trace of $E$.

Also, $\#E(F_{q^n} ) = q^n + 1 − V_n$ for all $n ≥ 2$, where $\{V_n\}$ is the sequence defined recursively by $$V_0 = 2, V_1 = t,\text{ and }V_n = V_1V_{n−1}−qV_{n−2}$$ for $n ≥ 2$. In your question it's enough to compute $V_{431}$.

For more details, see Guide to Elliptic Curve Cryptography.