I have tried to calculate $trace$ of a coordinate $X$ of EC in binary representation. Before that I tried to pre-calculate traces of the various bits of $X$ using formula: $$Tr(X) = Tr(\sum_{i = 0}^{m-1} c_ix_i)= \sum_{i = 0}^{m-1}(c_i Tr(x_i) )$$

For the field $F_{2^{163}}$ that i use we have only 2 cases $x_i$ that yield $Tr(x_i) = 1$ to common $trace$. This cases when $i$ - 0 and 157. With 0 is ok but for others cases squaring the polynomials and reduction by modulus lead to the performance issues.

I would be appreciated if anyone proposes a more effective approach to such calculations. Or any references to ready implementations or services which can be used to calculate traces

  • $\begingroup$ Needs a better title.. $\endgroup$
    – kelalaka
    Nov 25, 2018 at 18:02

1 Answer 1


What do you mean by trace of "bits" of $X$? How do you define $x_i$?

Since $263$ is prime, the field $\mathbb{F}_{2^{163}}$ has no subfields other than the prime field $\mathbb{F}_2.$ This means that the trace function $$Tr:\mathbb{F}_{2^{163}}\rightarrow \mathbb{F}_2$$ is the only trace which exists for this field. However, this means that the function $Tr(u)$ is equidistributed on $\mathbb{F}_{2}$, which means it is $0$ half the time and $1$ half the time as $u$ ranges over $\mathbb{F}_{2^{163}}.$

This property would also apply to any "bit" of $X$, reasonably defined as the coordinate of $X$ with respect to some basis element.

Edit: If as in my comment $u=\alpha^i$, squaring gives $u^2=\alpha^{2i}.$ So square of $e_i$ is $e_{2i}$ but if $2i\geq n=163$ it needs to be reduced mod the field defining polynomial.

In $\mathbb{F}_{2^4}$. defined by $\alpha^4+\alpha+1=0,$ $\alpha=e_1=0010,$ $\alpha^2=e_2=0100,$ but $\alpha^4=\alpha+1=e_1+e_0=0011.$

  • $\begingroup$ I mean that $trace$ is linear function and any coordinates can be separated per bits. $x_i$ are jusr $.....00000100 , ...0000001000 $ and so on $\endgroup$ Nov 25, 2018 at 19:41
  • $\begingroup$ OK but what $i=0,157$ represent is still unclear since the bits are basis dependent. What does your sentence "yield 0 to common trace" really mean? Write it mathematically. $\endgroup$
    – kodlu
    Nov 25, 2018 at 21:10
  • $\begingroup$ X coordinate for EC $F_{2^{163}} $ is bit row of 163 bits. So $x_0$ here all bits are 0 but the rightmost bit is 1, $x_{157}$ here all bits are 0 except 157-th bit that is 1 $\endgroup$ Nov 26, 2018 at 13:16
  • $\begingroup$ Oh, it seems like $x_i$ are what's usually called $e_i$, unit vectors with only one bit nonzero. $\endgroup$
    – kodlu
    Nov 26, 2018 at 19:43
  • $\begingroup$ Yes, @kodlu, but say me please what is the result of squaring such unit vector $e_i ^2$? I mean $e_i^2 = e_i$, right? $\endgroup$ Nov 27, 2018 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.