Page 57 - Hardware Implementation of Finite-Field Arithmetic

40 Cha pte r T w o

b = 1
0
k
b = 2 mod m
1
2k
b = 2 mod m
2
. . .
b = 2 (s − 1)k mod m
s − 1
Example 2.2 Assume again that n = 64, k = 8, and m = 239, so that s = 8.
The values of b to b have been previously calculated. They are
0 7
expressed in hexadecimal:
b = (01), b = (11), b = (32), b = (85), b = (6E), b = (C5),
0 1 2 3 4 5
b = (03), b = (33)
6 7
Compute x mod (EF) where x = (41C1D298F81A7296):

(41)(33) + (C1)(03) + (D2)(C5) + (98)(6E) + (F8)(85) + (1A)(32)
+ (72) (11) + (96)(01) = (18034)
(1)(32) + (80)(11) + (34)(01) = (8E6)
(8)(11) + (E6)(01) = (16E)
(1)(11) + (6E)(01) = (7F)

In the following Algorithm 2.6 vector_r is the base-2 representation
k
of r and b_table(m,i) returns 2 mod m.
ik
ik
Algorithm 2.6—Precomputation of 2 mod m
r := x;
loop
vector_r(0) := r mod 2**k; q := r/2**k;
for i in 1 .. s-1 loop
vector_r(i) := q mod 2**k; q := q/2**k;
end loop;
r := vector_r(0);
for i in 1 .. s-1 loop
r := r + vector_r(i)*b_table(m)(i);
end loop;
if r < 2**k then exit; end if;
end loop;
if r >= m then z := r-m; else z := r; end if;
An executable Ada file precomputation_reducer.adb is available
at www.arithmetic-circuits.org.
The datapath corresponding to Algorithm 2.6 is shown in Fig. 2.7.
If only the arithmetic circuit delays are taken into account, the minimum
period of the clock signal is the delay of a k-bit by k-bit multiplier
followed by a d-bit adder. Assume that a carry-save multiplier and
carry-ripple adders are used (Fig. 2.8, with k = 3 and d = 8), then the