Page 56 - Hardware Implementation of Finite-Field Arithmetic

mod m Reduction 39

Then any natural x belonging to the interval
l s−1. l l s−1 + ... 1 l + + 0 l n
1.
0 ≤ x < W = 2 ... . 2 2 = 2 = 2
l 0
s
can be represented under the form
l
x = X W + X W + . . . + X W + X W where 0 ≤ X < 2 i ,
s − 1 s − 1 s − 2 s − 2 1 1 0 0 i
∀i = 0, 1, . . . , s − 1 (2.33)
The following values are previously computed:

b = W = 1
0 0
b = W mod m
1 1
b = W mod m
2 2
. . .
b = W mod m
s − 1 s − 1
Then
x ≡ X b + X b + . . . + X b + X b mod m (2.34)
s − 1 s − 1 s − 2 s − 2 1 1 0 0
and the problem is reduced to the computation of r mod m where
r = X b + X b + . . . + X b + X b (2.35)
s − 1 s − 1 s − 2 s − 2 1 1 0 0
Assume that 2 k − 1 ≤ m < 2 and that l ≥ k. Then
k
0
l
k
W > . . . > W = 2 0 ≥ 2 > m
s − 1 1
so that b = W mod m < W, ∀i = 1, 2, . . . , s − 1, and r is smaller than x
i i i
l
except if X = X = . . . = X = 0 in which case r = X < 2 0 . Thus, an
1 2 s − 1 0
iterative use of the preceding method eventually generates a natural
l
z ≡ x mod m and smaller than 2 0 . A final correction step generates z =
x mod m. In particular, if l = k, so that z < 2 , then x mod m is either z
k
0
or z – m.
As a particular case assume that n = sk and define l = l = l = . . . =
0 1 2
l = k. Then
s − 1
W = 1, W = 2 , W = 2 , . . . , W = 2 (s − 1)k and W = 2 = 2 n
2k
k
sk
0 1 2 s − 1 s
The corresponding representation [Eq. (2.33)] of x is
x = X · 2 (s − 1)k + X · 2 (s − 2)k + . . . + X · 2 + X where 0 ≤ X < 2 ,
k
k
s − 1 s − 2 1 0 i
∀i = 0, 1, . . . , s − 1
and the previously computed values are