Page 62 - Hardware Implementation of Finite-Field Arithmetic

mod m Reduction 45

that is,
a = 2 (2.49)
According to Eqs. (2.40) and (2.49) the value of t must be chosen
t
in such a way that B ≥ 3. Thus
if B = 2, then t = 2 (the computation is performed mod B k + 2 ),
if B > 2, then t = 1 (the computation is performed mod B k + 1 ).
To summarize, the following algorithm computes z = x mod p.
The constant
c =⎣B /m⎦ (2.50)
n
must have been previously calculated.
Algorithm 2.8—Barrett reduction (complete Ada source code available)

y := x/B**(k-1); w := y*c; q := (w/B**(n-k+1)) mod B**(k+t);
r := ((x mod B**(k+t)) - ((q*m) mod B**(k+t))) mod B**(k+t);
while r >= m loop r := r-m; end loop;
z := r;

The division by B k − 1 or B n − k + 1 and the mod B k + t reduction are
trivial operations. The only nontrivial operations are multiplications
by c and m, and subtractions. An executable Ada file Barrett_reducer.
adb is available at www.arithmetic-circuits.org.
Example 2.3 As before assume that x is a 64-bit number and m = 239.
All numbers will be represented in hexadecimal, so that B = 16, n = 16,
16
k = 2, t = 1, c = ⎣16 /239⎦ = (112358E75D30336), m = (EF). Compute
(41C1D298F81A7296) mod (EF):
y = x/16 = (41C1D298F81A729)
w = yc = (41C1D298F81A729)(112358E75D30336)
= (. . . 15958562734E19BDA6)
15
3
3
q = w/16 mod 16 = (. . .159) mod 16 = (159)
product = qm = (159)(EF) = (14217)
3
3
r = (x mod 16 ) – (product mod 16 ) = (296) – (217) = (7F)
z = (7F)
If B = 2, and thus t = 2, then
2 k − 1 < m < 2 , 2 n − k <2 /m < 2 n − k + 1 , 2 n − k ≤ c < 2 n − k + 1 , that is,
n
k
c = c(n − k..0)
x/2 k − 1 = x(n − 1 .. k − 1) = y(n − k..0)
(w/2 n − k + 1 ) mod 2 k + 2 = w[(n − k + 1) + (k + 1) .. n − k + 1]
= w(n + 2 .. n − k + 1) = q(k + 1..0)
and an equivalent version of Algorithm 2.8 is the following.