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