## Choosing n and m for composite field

Referring to “Efficient Normal Basis Multipliers in Composite Fields” – Sangho Oh, Chang Han Kim, Jongin Lim, and Dong Hyeon Cheon, there is classification of hardware-applicable composite fields:

1. Type I composite field where a subfield $GF(2^n)$ in ONB2 and an extension field $GF(2^{nm})$ in ONB1
2. Type II composite field where a subfield $GF(2^n)$ in ONB1 and an extension field $GF(2^{nm})$ in ONB2
3. Type III composite field where a subfield $GF(2^n)$ in ONB2 and an extension field $GF(2^{nm})$ in ONB2

This is different with composite fields presented in “Efficient Methods for Composite Field Arithmetic” – E. Sava ̧s and C ̧. K. Koc, where the selection of $n$ and $m$  does not put their normal basis types (ONB1 or ONB2) into consideration.

Now the questions are:

1. Would it be better if we choose $n$, $m$ and $nm$ in ONB1/ONB2?
2. Which polynomial irreducible to be used? With degree = $n$, or degree = $m$ or degree = $nm$?

[pounding headache, and without answering these questions i wouldnt be able to start the hw design.]

## More on ONB1 identity element

“Application of Finite Fields”  page 98:

For a type I optimal normal basis, its minimal polynomial is obviously x $x^n + ... + x + 1$, which is irreducible over $F_q$ if and only if $n + 1$ is a prime and $q$ is primitive in $Z_{n+1}$

For n = 4,
$x^4+x^3+x^2+x = 1$
$x^5 = 1$
$x^6 = x$
$x^7 = x^2$
$x^8 = x^3$
$x^9 = x^4$

Ex :
Let’s prove that 1111 is the identity element of ONB1 n = 4.

1010 x 1111 = ($x^8+x^2$) x ($x^8+x^4+x^2+x$)
= $x^{16}+x^{12}+x^{10}+x^9+x^{10}+x^6+x^4+x^3$
= $x^{16}+x^{12}+x^9+x^6+x^4+x^3$
= $x + x^2 + x^4 + x + x^4 + x^3$
= $x^2 + x^3$
= $x^2 + x^8$
= $x^8 + x^2$
= 1010

## ONB1 identity element

Rosing wrote on page 144:

In an optimal normal basis, adding 1 is the same as taking a complement

And finally figuring this out after finding out that the identity element of ONB1 is $x^{2^{n-1}}+...+x^{2^{1}}+x^{2^{0}}$. If we have n = 4, the identity element or “1” is 1111 ($x^{8}+x^{4}+x^{2}+x$).

That’s why if we have 0011 in normal basis ($x^2+x$), adding it with “1” so it becomes 0011 + 1111 = ($(x^2+x) + (x^8+x^4+x^2+x)$ = $x^8+x^4$ = 1100.

Hoooraaaay!

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r