# Multiplication and squaring the binary polynomials

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

• Needs a better title.. – kelalaka Nov 25 '18 at 18:02

## 1 Answer

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.$$

• I mean that $trace$ is linear function and any coordinates can be separated per bits. $x_i$ are jusr $.....00000100 , ...0000001000$ and so on – Rotvik Knuzich Nov 25 '18 at 19:41
• 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. – kodlu Nov 25 '18 at 21:10
• 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 – Rotvik Knuzich Nov 26 '18 at 13:16
• Oh, it seems like $x_i$ are what's usually called $e_i$, unit vectors with only one bit nonzero. – kodlu Nov 26 '18 at 19:43
• 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? – Rotvik Knuzich Nov 27 '18 at 17:05