![]() 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
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. |