Page 258 - Hardware Implementation of Finite-Field Arithmetic

238 Cha pte r Ei g h t

8.2 Squaring
Suppose that N = {β 2 0 ,β 2 1 , ... , β 2 m − 1 } is a normal basis of GF(2 ) over
m
2
2
m
2
GF(2). As given above, for any A and B ∈ GF(2 ), (A + B) = A + B is
m
true because 2AB = 0. From Fermat’s theorem, that is, A 2 − 1 = 1,
A 2 m = A holds. Therefore, if A = a β 2 0 + a β 2 1 + ... + a β 2 m − 1 then
0 1 m − 1
A = a β 2 1 + a β 2 2 + ... + a β 2 m = a β 2 0 + a β 2 1 + .... + a β 2 m − 1 (8.5)
2
−
−
0 1 m 1 m 1 0 m − 2
Therefore, in normal basis, when A = (a , a , . . . , a ), A = (a ,
2
0 1 m − 1 m − 1
a , . . . , a ). In other words, squaring is carried out by a simple cyclic
0 m − 2
right shift, and thus in arithmetic hardware it is almost free of cost.
Assuming that the function
function rshift(x: poly_vector) return poly_vector
performing 1-bit right shift is available, the normal basis squaring in
m
GF(2 ) of an element A = (a , a , . . . , a ) is easily given in the follow-
0 1 m − 1
ing algorithm:
Algorithm 8.1—Normal basis squaring

a0 := a(m-1);
a := rshift(a);
a(0) := a0;

An executable Ada file NB_sq.adb, including Algorithm 8.1, is avai-
lable at www.arithmetic-circuits.org. This algorithm has been also
implemented in the function
function NB_sq(a: poly_vector) return poly_vector
for its use in the remaining arithmetic operations in normal basis.

8.3 Multiplication
In this section, the work originally described by Massey and Omura
[MO86] is reviewed. Let {β 2 0 ,β 2 1 ,... ,β 2 m− 1 } be a normal basis of GF(2 )
m
over GF(2) and let A and B be any two elements represented in the
normal basis as A =∑ m−1 a β and B =∑ m−1 b β , respectively. Let A
j
i
2
2
i=0 i j=0 j

and B be represented in vector notation by A = (a , a , . . . , a ) and B =
0 1 m-1
(b , b , . . . , b ), respectively. Then the product C = AB = (c , c , . . . ,
0 1 m − 1 0 1
c ) in vector notation. The last term c of the product is some binary
m−1 m − 1
function of the components of A and B
c = h(a , a , . . . , a ; b , b , . . . , b ) (8.6)
m − 1 0 1 m − 1 0 1 m − 1