Page 61 - Hardware Implementation of Finite-Field Arithmetic

44 Cha pte r T w o

The following formal algorithm, including a function approximation
which generates an approximation q’ of ⎣x/m⎦ [see Eq. (2.37)], computes
a (k + t)-digit number r equivalent to x mod m:

Algorithm 2.7—n-digit to (k + t)-digit reduction

q := approximation(x, m);
r := ((x mod B k + t ) – (q*m mod B k + t )) mod B k + t ;

t
If a = 2 and B ≥ 3, then condition Eq. (2.40) amounts to B ≥ 3 and is
satisfied if t = 1. Thus x − q’m can be computed as mod B k + 1 . This case
corresponds to the classical Barrett algorithm.

2.4.2 An Approximation of q
Let x and m be expressed in base B, that is,

+
x = x B n − 1 + x B n − 2 . . . + x B ,
0
n − 1 n − 2 0
0
m = m B k − 1 + m B k − 2 + . . . + m B where m > 0
k − 1 k − 2 0 k − 1
The approximation q’ of q = ⎣x/m⎦ is,
q’ = ⎣ ⎣x/B k − 1 ⎦ ⎣B /m⎦/B n − k + 1 ⎦ (2.44)
n
Observe that

n
q’ ≤ ⎣(x/B k − 1 )(B /m)/B n − k + 1 ⎦ = ⎣x/m⎦ = q (2.45)
and

n
n
q =⎣(x/B k − 1 )(B /m)/B n − k + 1 ⎦ < ⎣( ⎣x/B k − 1 ⎦ + 1)( ⎣B /m⎦ + 1)/B n − k + 1 ⎦
n
n
= ⎣[( ⎣x/B k − 1 ⎦ ⎣B /m⎦ )/B n − k + 1 ] + [(⎣x/B k − 1 ⎦ + ⎣B /m⎦ + 1)/ B n − k + 1 ]⎦
n
n
≤ ⎣[( ⎣x/B k − 1 ⎦ ⎣B /m⎦ )/B n − k + 1 ]⎦ + ⎣[(⎣x/B k − 1 ⎦ + ⎣B /m⎦ + 1)/B n − k + 1 ]⎦
= q’ + ⎣[(⎣x/B k − 1 ⎦ + ⎣B /m⎦ + 1)/ B n − k + 1 ]⎦ (2.46)
n
As x < B and m ≥ B k − 1 , then
n
n
x/B k − 1 < B n − k + 1 and B /m ≤ B n − k + 1 (2.47)
so that
⎣x/B k − 1 ⎦ + ⎣B /m⎦ + 1 ≤ (B n − k + 1 –1) + B n − k + 1 + 1 = 2B n − k + 1 (2.48)
n
Thus from [Eqs. (2.46) and (2.48)],

q ≤ q’ + 2