F24 with Optimal Normal Basis Representation

The elements of F24 are all binary strings of length 4. Addition and subtraction are defined as with polynomial representation.

Setup for Multiplication
  1. The field F24 has a Type I Optimal Normal Basis; thus f(x)= x4 + x3 + x2+ x + 1. The set of polynomials {x,x2, x4, x8}forms a normal basis of F24over F2.


The rows of A are constructed as follows:

Row 0: x mod f(x) = x = (0 0 1 0)

Row 1: x2 mod f(x) = x2 = (0 1 0 0)

Row 2: x4 mod f(x) = x3 + x2 + x + 1 = (1 1 1 1)

Row 3: x8 mod f(x) = x3 = (1 0 0 0)

Thus



3. And the inverse of A over F2 is



4. The rows of T' are constructed as follows:

Row 0: v = x x mod f(x) = x2 = (0 1 0 0)

Row 1: v = x x2 mod f(x) = x3 = (1 0 0 0)

Row 2: v = x x4 mod f(x) = x5 mod f(x) = 1 = (0 0 0 1)

Row 3: v = x x8 mod f(x) = x9 mod f(x) = x3 + x2 + x + 1 = (1 1 1 1)

Thus



and



The product terms are:

l0,0 = T(0,0) = 0 l1,0 =T(3,3) = 0 l2,0 = T(2,2) = 1 l3,0 = T(1,1) = 0

l0,1 = T(1,0) = 0 l1,1 =T(0,3) = 0 l2,1 = T(3,2) = 1 l3,1 = T(2,1) = 1

l0,2 = T(2,0) = 1 l1,2 =T(1,3) = 1 l2,2 = T(0,2) = 0 l3,2 = T(3,1) = 0

l0,3 = T(3,0) = 0 l1,3 =T(2,3) = 1 l2,3 = T(1,2) = 0 l3,3 = T(0,1) = 1




Multiplication

Multiplication is defined by (a0 a1 a2 a3) (b0 b1 b2 b3) = (c0 c1 c2 c3), where
c 0 = a0b2 + a1(b2 + b3) + a2(b0 + b1) + a3(b1 + b3)
c1 = a1b3 + a2(b3 + b0) + a3(b1 + b2) + a0(b2 + b0)
c2 = a2b0 + a3(b0 + b1) + a0(b2 + b3) + a1(b3 + b1)
c3 = a3b1 + a0(b1 + b2) + a1(b3 + b0) + a2(b0 + b2)
.

Thus (0 1 0 0) (1 1 0 1) = (c0 c1 c2 c3), where
c 0 = 0(0) + 1(0 + 1) + 0(1 + 1) + 0(1 + 1) = 1
c1 = 1(1) + 0(1 + 1) + 0(1 + 0) + 0(0 + 1) = 1
c2 = 0(1) + 0(1 + 1) + 0(0 + 1) + 1(1 + 1) = 0
c3 = 0(1) + 0(1 + 0) + 1(1 + 1) + 0(1 + 0) = 0,
and (0 1 0 0) (1 1 0 1) = (1 1 0 0).

Exponentiation using Optimal Normal Bases

The squaring (a0 a1 a2 a3)2 = (a0 a1 a2 a3) (a0 a1 a2 a3) = (c0 c1 c2 c3), where
c 0 = a0a2 + a1(a2 + a3) + a2(a0 + a1) + a3(a1 + a3) = a32 = a3
c1 = a1a3 + a2(a3 + a0) + a3(a1 + a2) + a0(a2 + a0) = a02 = a0
c2 = a2a0 + a3(a0 + a1) + a0(a2 + a3) + a1(a3 + a1) = a12 = a1
c3 = a3a1 + a0(a1 + a2) + a1(a3 + a0) + a2(a0 + a2) = a22 = a2.


Thus (a0 a1 a2 a3)2 = (a3 a0 a1 a2) can be calculated with a simple rotation of (a0 a1 a2 a3).

Squaring is a very efficient operation when optimal normal basis representation is used. Since exponentiation typically involves many squaring operations, exponentiation is performed far more efficiently using optimal normal basis representation than using polynomial representation.