Page 47 - Hardware Implementation of Finite-Field Arithmetic

30 Cha pte r T w o

the so-called stored-carry encoding. Then the operations r = s + y, r = s,
and r = s − y, are substituted by

r + r = s + s + y r + r = s + s and r + r = s + s − y (2.16)
s c s c s c s c s c s c
where r + r is the stored-carry representation of r. Assume that all
s c
integers are represented as (n + 2)-bit 2’s-complement numbers. Then
the computation of r + r = s + s + w, where w is equal to either y, 0, or
s c s c
the 2’s complement representation of − y, is performed as follows:

r (i) = s (i) + s (i) + w(i) mod 2 ∀i = 0, 1, . . . , n + 2
s s c
r (0) = 0 r (i) = (s (i − 1) + s (i − 1) + w(i − 1))/2
c c s c
∀i = 1, 2, . . . , n + 2 (2.17)

that is carry-free operations.
In the following algorithm the functions csa_sum(s , s , w) and
s c
csa_carry(s , s , w) return r and r according to Eq. (2.17).
s c s c
Algorithm 2.2—Generic digit-recurrence carry-save reduction algorithm

y := m*(2**(n-k));
--2’s complement representation of -y and x
minus_y := (2**(n+2)) - y;
if x >= 0 then ss := x; sc := 0; else ss := (2**(n+2))+ x;
sc := 0; end if;
--main loop
for i in 0 .. n-k loop
if quotient(ss, sc, y) = 1 then
rs := csa_sum(ss, sc, minus_y);
rc := csa_carry(ss, sc, minus_y);
elsif quotient(ss, sc, y) = 0 then rs := csa_sum(ss, sc, 0);
rc := csa_carry(ss, sc, 0);
else rs := csa_sum(ss, sc, y); rc := csa_carry(ss, sc, y);
end if;
ss := 2*rs; sc := 2*rc;
end loop;
--final step
z := ((rs+rc) mod (2**(n+1)))/(2**(n-k));
--correction if z < 0
if z >= 2**k then z := (z+m) mod 2**k; end if;
In order to get an executable algorithm it remains to define the quotient
function. It has been shown ([Par00], [EL04], [DBS06]) that the
decision can be taken without computing the exact value of s = s + s ,
s c
but just an approximation of s (the so-called SRT algorithm, after
Sweeney, Robertson, and Tocher). Actually, it is enough to know the
four most significant bits of s + s (Table 6.3 of [DBS06]). Let s ’ and s ’
s c s c