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

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.

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.

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.