Page 203 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 183

− 1
where r (x) is the inverse of r(x) modulo f(x). These two polynomials
can be calculated with the extended Euclidean algorithm. The Mont-
m
gomery multiplication over GF(2 ) given in Eq. (7.31) can therefore be
computed using the following algorithm:
Algorithm 7.6—Montgomery multiplication
Input: a(x), b(x), r(x), and f’(x)
-1
Output: c(x) = a(x)b(x)r (x) mod f(x)
1. t(x) := a(x)b(x)
2. u(x) := t(x)f’(x) mod r(x)
3. c(x) := [t(x) + u(x)f(x)]/r(x)
The correctness of the above algorithm can be found in [KA98],
where it was noted also that efficient multiplication can be obtained
if r(x) is properly chosen. In fact, r(x) was chosen to be the monomial
m
r(x) = x . Thus, r is the element of the finite field represented by the
+
m
m
polynomial r(x) mod f(x). If f(x) = x + f x m − 1 . . . + f x + f ⇒ x = f
m − 1 1 0 m − 1
x m − 1 + . . . + f x + f , that is, r = (f , f , . . . , f , f ), where f s are the
1 0 m − 1 m − 2 1 0 i
coefficients of the irreducible polynomial f(x). Montgomery multipli-
m
cation method requires that gcd(r(x), f(x)) = 1, which in GF(2 ) is
always true because the polynomial f(x) is irreducible over GF(2).
The computation of c(x) in Algorithm 7.6 requires a polynomial
multiplication, in step 1, a modulo r(x) operation in step 2, and finally
an addition, a polynomial multiplication, and a division by r(x) in
step 3. The modular multiplication and division operations in steps 2
m
and 3 are very fast because r(x) = x . The remainder operation using
m
modulus r(x) = x can be performed by simply ignoring the terms that
have powers greater or equal to m, and the division of an arbitrary
m
polynomial by r(x) = x is accomplished by just shifting the polynomial
to the right by m places. It also turns out that the computation of f’(x)
can be completely avoided if the coefficients of a(x) are scanned one
bit at a time. From the above remarks, the following bit-level algorithm
for Montgomery multiplication in GF(2 ) was given in [KA98]:
m
Algorithm 7.7—Bit-level algorithm for Montgomery multiplication
Input: a(x), b(x), f(x)
-m
Output: c(x) = a(x)b(x)x mod f(x)
1. c(x) := 0
2. for i = 0 to m – 1 do
3. c(x) := c(x) + a b(x)
i
4. c(x) := c(x) + c f(x)
0
5. c(x) := c(x)/x
Algorithm 7.7 needs m identical rounds to come up with the correct
result in its output. In step 3, the polynomial c(x) is added to the
polynomial b(x) if the appropriate coefficient a of the polynomial a(x)
i
is 1. In step 4, if the coefficient c of c(x) is 1 then the irreducible
0
polynomial f(x) is added to c(x). Finally, the polynomial c(x), is divided