Page 60 - Hardware Implementation of Finite-Field Arithmetic

mod m Reduction 43

end process register_r;
end_of_computation <= ‘1’ when r(D-1 downto K)=SHORT_ZERO
else ‘0’;
r_minus_m <= (‘0’ & r(K-1 downto 0)) - (‘0’ & m);
with r_minus_m(K) select z <= r(K-1 downto 0) when ‘1’,
r_minus_m(K-1 downto 0) when others;
The complete model additionally includes a control unit generating
the load, reload, sel, and done signals.

2.4 Barrett Reduction Algorithm
A generalized version of the Barrett algorithm ([MOV96], [HMV04])
is presented.

2.4.1 n-Digit to (k + t)-Digit Reduction
k
Assume that m belongs to the range B k − 1 < m < B where B is the base of
the chosen numeration system (usually 2 or a power of 2). Observe that
if m is a power of B the computation is trivial: x mod m is the number
represented by the k less significant digits of x. The value of z = x mod m
is the remainder of the integer division of x by m, that is,
x = qm + z, z < m

The Barrett algorithm starts with the computation of an approxima-
tion q’ of q = ⎣x/m⎦ such that
q − a ≤ q’ ≤ q (2.37)

(a method for computing an approximation q’ of q is given in Sec.
2.4.2). First compute
r’ = x – q’m (2.38)

As z = x – qm, then [Eq. (2.37)]
z ≤ r’ ≤ z + am (2.39)

Let t be the minimum integer such that
B ≥ a + 1 (2.40)
t
Then,

t
k
r’ ≤ z + am < m + am = (a + 1)m < B B = B k + t (2.41)
Thus,
0 ≤ z ≤ r’< B k + t (2.42)
and [Eq. (2.38)]

r’ mod m = x mod m = z (2.43)