Page 52 - Hardware Implementation of Finite-Field Arithmetic

mod m Reduction 35

k
Algorithm 2.4—Partial mod 2 − a reduction
a := 2**k - m;
r := x mod 2**k; q := x/2**k;
loop
r := r + (q*a mod 2**k); q := q*a/2**k;
if q = 0 then exit; end if;
end loop;
z := r;
Algorithm 2.4 generates a natural z smaller than x, except if r = r
1 2
k
= . . . = r = 0 in which case x = r = r < 2 . An iterative execution of
s − 1 0
Algorithm 2.4 eventually generates a natural z ≡ x mod m and smaller
k
than 2 . A final correction step generates z = r − m if r ≥ m.
Example 2.1 Assume that n = 64, k = 8, and m = 239. Thus a = 2 − 239 = 17.
8
In what follows, all numbers are represented in hexadecimal. In particular
m = (EF), 2 = (100), and 17 = (11). Compute (41C1D298F81A7296)
8
mod (EF):
(41C1D298F81A7296) = (41C1D298F81A72)(100) + (96)
(41C1D298F81A72)(11) = (45DDEFC2879C1)(100) + (92)
(45DDEFC2879C1)(11) = (4A3BCEBEB015)(100) + (D1)
(4A3BCEBEB015)(11) = (4EDF8BAA9B1)(100) + (65)
(4EDF8BAA9B1)(11) = (53CD846544)(100) + (C1)
(53CD846544)(11) = (590A5CAB9)(100) + (84)
(590A5CAB9)(11) = (5E9B0276)(100) + (49)
(5E9B0276)(11) = (6484B29)(100) + (D6)
(6484B29)(11) = (6ACCFD)(100) + (B9)
(6ACCFD)(11) = (7179C)(100) + (CD)
(7179C)(11) = (7891)(100) + (5C)
(7891)(11) = (801)(100) + (A1)
(801)(11) = (88)(100) + (11)
(88)(11) = (9)(100) + (08)
(9)(11) = (0)(100) + (99)

Thus, s = 15 and
r = (96) + (92) + (D1) + (65) + (C1) + (84) + (49) + (D6) + (B9) + (CD)
+ (5C) + (A1) + (11) + (08) + (99) = (7F7)
The same method is used for reducing (7F7):
(7F7) = (7)(100) + (F7)
(7)(11) = (0)(100) + (77)