Algorithms and Parallel Computing

17.2 THE MULTIPLICATION ALGORITHM IN GF(2^m)

Let A(x) and B(x) be two field elements in the finite field GF(2^m), where m is an integer that typically has the values 163, 233, 283, 409, or 571. The two elements A(x) and B(x) can be written as the order m − 1 polynomials

(17.1)

(17.2)

where a(i) and b(i) could have the values 0 or 1.

The elements of the finite field are generated by a primitive polynomial R(x) of order m,

(17.3)

where r(m) must have the value r(m) = 1, and we can express the above equation as the sum

(17.4)

where f (x) is a polynomial of order m − 1.

The product of the field elements A(x) and B(x) is written as

(17.5)

We can evaluate the above double summation as

(17.6)

The above equation can be evaluated using the so-called “left-to-right shift-and-add” field multiplication method [110]. This algorithm is shown as follows:

Algorithm =17.1

Left-to-right ...