17.2 THE MULTIPLICATION ALGORITHM IN GF(2m)
Let A(x) and B(x) be two field elements in the finite field GF(2m), 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
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 shift-and-add field multiplication
Require: Input: Binary polynomials A(x) and B(x) of degree at most m − 1 and R(x) of degree m
1: C(x) = 0
2: for i = m − 1 : 0 do
3: C(x) = xC(x) mod R(x)
4: C(x) = C(x) + biA(x)
5: end for
6: RETURN C(x) // = A(x)B(x) mod R(x)
A few things must be noted in Algorithm 17.1:
1. The left shift operation xC(x) in line 3 could result in a polynomial larger than R(x), and hence the modulo operation in that step might be necessary. Specifically, if the coefficient c(m − 1) = 1, then we must subtract R(x) from the polynomial xC(x).
2. Bitwise add or subtract in GF(2) is equivalent to a bitwise exclusive OR (XOR)operation.
3. The addition operation in line 4 is a bitwise XOR operation over the m terms of the polynomials.
4. From Eq. 17.4, we can write line 3 as
(17.7)
The above equation ensures that the modulo operation, which is accomplished by adding f(x), only takes place when c(m − 1) = 1.
Algorithm 17.1 can be modified to express it as a regular iterative algorithm (RIA). This is done by explicitly writing the iterations required at the bit level. Algorithm 17.2 is the bit-level implementation of Algorithm 17.1.
Algorithm 17.2
Bit-level left-to-right shift-and-add field multiplication. ∧ represents logical AND operation and ⊗ represents logical XOR operation
Require:
1: Binary polynomials A(x) and B(x) of degree at most m − 1 and R(x) of degree m
2: for j = 0 : m − 1 do
3: c(0, j) = 0
4: end for
5: for i = 1 : m − 1 do
6: c(i, 0) = [a(0) ∧ b(m − i)] ⊗ c(i − 1, m − 1)
7: for j = 1 : m − 1 do
8: c(i, j) = [a(j) ∧ b(m − 1 − i)] ⊗ c(i − 1, j − 1) ⊗ [c(i − 1, m − 1) ∧ r(j)]
9: end for
10: end for
11: RETURN C(x) // = A(x)B(x) mod R(x)
Note that the index values of iterations in line 5 are increasing, while in Algorithm 17.1 the index in line 2 is decreasing. However, in both algorithms, the order of the operations is still preserved.