Page 111 - Hardware Implementation of Finite-Field Arithmetic

94 Cha pte r F o u r

that is, according to Eq. (4.10),

a = (q · 2 k − 2 + q · 2 k − 3 + q · 2 k − 4 + . . . + q · 2 )b + (r /2 k − 2 )
0
1 2 3 k − 1 k − 1
Thus the quotient q and the remainder r are
+
0
q = q · 2 k − 2 + q · 2 k − 3 + q · 2 k − 4 . . . + q · 2 and
1 2 3 k − 1
r = r /2 k − 2 (4.12)
k − 1
with
− b ≤ r < b (4.13)
Then define

q ’ = (q + 1)/2 (4.14)
i i
so that q = 2q ’− 1 and
i i
q = (q ’ · 2 k − 1 + q ’ · 2 k − 2 + q ’ · 2 k − 3 + . . . + q ’ · 2) − (2 k − 1 − 1)
1 2 3 k − 1
= (q ’− 1) · 2 k − 1 + q ’ · 2 k − 2 + q ’ · 2 k − 3 + . . . + q ’ · 2 + 1 · 2 (4.15)
0
1 2 3 k − 1
According to Eq. (4.14) q ’ ∈ {0, 1} and the k-bit binary vector
i
(1 − q ’) q ’q ’ . . . q ’ 1
1 2 3 k − 1
is the 2’s complement representation of q. Nevertheless, as r could be
negative [Eq (4.13)], a final correction step could be necessary:

If r < 0, then substitute q by q − 1 and r by r + b

According to the definition Eq. (4.14) of q ’, its value is defined as
i
follows:
If s < 0 then q ’ = 0 and r = s + y, and if s ≥ 0 then q ’ = 1 and
i − 1 i i i − 1 i − 1 i
r = s − y
i i − 1

Algorithm 4.2—Nonrestoring algorithm

y := b*(2**(k-2)); s := a;
for i in 1 .. k-1 loop
if s < 0 then q(k-i) := 0; r := s + y;
else q(k-i) := 1; r := s - y; end if;
s := 2*r;
end loop;
remainder := r / (2**(k-2)); q(k-1) := 1 - q(k-1);
q(0) := 1;