Normal basis: squaring is fast

Yes, right. ONB (Optimal Normal Basis) is so appealing 😀

If we take some element \beta in the field F_{p^{m}} , the polynomial representation is:
\beta =a_{n}x^{n}+ ... + a_{1}x + a_{0}
where n < m

A normal basis can be formed using the set:
\left \{\beta ^{p^{m-1}},... \beta ^{p^{2}}, \beta ^{p}, \beta  \right \}

Any element in a field F_{p^{m}} can be represented in a normal basis format. An element e , can be written in a normal basis as:
e = e_{m-1}\beta ^{2^{m-1}} + ... + e_{2}\beta ^{2^{2}} + e_{1}\beta ^{2} + e_{0}\beta

It seems complex but the implementation in the computer is as simple as using only AND, OR and ROTATE!

The most interesting thing is that this representation allow squaring with just a number amounts of rotation!

Here are some proves:

  1. \left (\beta ^{2^{i}} \right )^{2}=\beta ^{2^{i+1}}
  2. \beta ^{2^{m}}=\beta

That’s why squaring is very fast in normal basis! Will post more about this.