Page 51 - Hardware Implementation of Finite-Field Arithmetic

34 Cha pte r T w o

Then
m = 2 – a (2.22)
k
where

1 ≤ a ≤ 2 k − 1 (2.23)
Given a natural x belonging to the range
0 ≤ x < 2 n (2.24)
compute the following quotients q and remainders r :
i i
k
x = q 2 + r
0 0
q a = q 2 + r
k
0 1 1
(2.25)
k
q a = q 2 + r
1 2 2
. . .
q a = q 2 + r
k
s − 2 s − 1 s − 1
k
k
2
Multiply the second Eq. (2.25) by (2 /a), the third one by (2 /a) , . . . ,
the last one by (2 /a) s − 1 , and sum up the s equations; the result is
k
2
k
k
k
x = r + r (2 /a) + r (2 /a) + . . . + r (2 /a) s − 1 + q 2 (2 /a) s − 1 (2.26)
k
k
0 1 2 s − 1 s − 1
k
where [Eq.(2.23)] 2 /a ≥ 2. Observe that if s > n − k, then q = 0. In the
s − 1
k
n
k
contrary case, x ≥ 2 (2 /a) s − 1 ≥ 2 k + s − 1 ≥ 2 k + (n − k + 1) − 1 = 2 . Thus, after a
finite number s of steps, with s ≤ n − k + 1, a kind of base (2 /a) expres-
k
sion is obtained:
2
x = r + r (2 /a) + r (2 /a) + . . . + r (2 /a) s − 1 with r > 0 (2.27)
k
k
k
0 1 2 s − 1 s − 1
k
in which every remainder r is smaller than 2 . By summing up the s
i
equations (2.25), assuming that q = 0, the following relation is
s − 1
obtained:
k
k
k
x = q (2 − a) + q (2 − a) + . . . + q (2 − a) + r + r + . . . + r (2.28)
0 1 s − 2 0 1 s − 1
Thus,
x ≡ r mod m = 2 − a with r = r + r + . . . + r (2.29)
k
0 1 s − 1
As every remainder r is smaller than 2 , the maximum value of r is
k
i
k
r < s2 ≤ (n − k + 1)2 (2.30)
k
so that r can be expressed as a t-bit natural where t = k +⎡log (n − k + 1)⎤.
2
The same method could then be used for generating a t’-bit number
r’ ≡ x mod m where t’ = k +⎡log (t − k + 1)⎤, and so on.
2
The following algorithm ([MOV96]) generates a t-bit natural z
such that
z ≡ x mod m, z < 2 , t ≤ k +⎡log (n − k + 1)⎤ (2.31)
t
2