Page 44 - Hardware Implementation of Finite-Field Arithmetic

mod m Reduction 27

Multiply the first Eq. (2.7) by 2 n − k , the second one by 2 n − k − 1 , the
third one by 2 n − k − 2 , and so on, and add up the n − k + 1 equations. The
result is

x2 n − k = (q 2 n − k + q 2 n − k − 1 + . . . + q )y + r (2.9)
1 2 n − k + 1 n − k + 1
Then, according to Eq. (2.4)

x2 n − k = (q 2 n − k + q 2 n − k − 1 + . . . + q )m2 n − k + r (2.10)
1 2 n − k + 1 n − k + 1
so that r is divisible by 2 n − k and
n − k + 1

x ≡ r /2 n − k mod m (2.11)
n − k + 1
From Eqs. (2.4) and (2.8),

− m ≤ r /2 n − k < m (2.12)
n − k + 1
Thus, if r ≥ 0 then x mod m = r /2 n − k , and if r < 0 then
n − k + 1 n − k + 1 n − k + 1
x mod m = m + r /2 n − k .
n − k + 1
Assume that a function quotient(s,y) has been defined. It generates
a solution q ∈ {−1, 0, 1} of Eq. (2.1). The following formal algorithm
computes z = x mod m.

Algorithm 2.1—Generic digit-recurrence reduction algorithm
y := m*(2**(n-k));
s := x;
for i in 0 .. n-k loop
if quotient(s,y) = 1 then r := s - y;
elsif quotient(s,y) = 0 then r := s;
else r := s + y;
end if;
s := 2*r;
end loop;
z := r /(2**(n-k));
if z < 0 then z := (z + m); end if;
Observe (Fig. 2.1) that if − y ≤ s < y, then there are two solutions for q.
The way a particular solution is chosen corresponds to the definition
of a particular digit-recurrence algorithm.

2.1.2 Nonrestoring Reducer
According to Fig. 2.1 the value of q can be defined as follows:
q = − 1 if s < 0 q = 1 if s ≥ 0 (2.13)

This definition corresponds to the classical nonrestoring algorithm
in which, at each step, the value of q only depends on the sign of s. An