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 '18 at 18:02

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$ – Rotvik Knuzich Nov 25 '18 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 '18 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$ – Rotvik Knuzich Nov 26 '18 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 '18 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$ – Rotvik Knuzich Nov 27 '18 at 17:05

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.