Page 95 - Hardware Implementation of Finite-Field Arithmetic

78 Cha pte r T h ree

Example 3.4 Assume again that m = 239, R = 256, then compute
MP(202, 236).

202 × 236 = 47672; thus (example 3.3) MP(202,236) = 119
An executable Ada file Montgomery_product.adb, including
Algorithm 3.10, is available at www.arithmetic-circuits.org.
If m is odd, then there exists an element 2 of Z such that 2 · 2
−1
−1
m
mod m = 1. Assuming that m is a k-bit number, choose R = 2 . Given
k
0
x = x · 2 k − 1 + x · 2 k − 2 + . . . + x · 2 and y in Z , then
k − 1 k − 2 0 m
MP(x,y) = xy(2 ) mod m = (x y2 k − 1 + x y2 k − 2
k − 1
k − 1 k − 2
+ . . . + x y2 )(2 ) mod m = (( . . . (((0 + x y)2 + x y)2 + x y)2
k − 1
− 1
− 1
− 1
0
0 0 1 2
+ . . . )2 − 1 + x y)2 mod m (3.22)
− 1
k − 1
−1
The multiplication of a natural a by 2 can be performed as follows:
− 1
−1
if a is even then a2 ≡ a/2 mod m; if a is odd then a2
≡ (a + m)/2 mod m (3.23)
The following algorithm is deduced from Eqs. (3.22) and (3.23):
Algorithm 3.11
p := 0;
for i in 0 .. k-1 loop
a := p + x(i)*y;
if (a mod 2) = 0 then p := a/2; else p := (a + m)/2;
end if;
end loop;
z := p mod m;
In the preceding algorithm p is always smaller than 2m (by
induction):
If p < 2m, then a = p + x y < 2m + y < 3m, a/2 < (3/2)m < 2m,
i
(a + m)/2 < 4m/2 = 2m
Thus, at the last step z is either p or p − m.
Algorithm 3.12—Binary Montgomery product

p := 0;
for i in 0 .. k-1 loop
a := p + vector_x(i)*y;
if (a mod 2) = 0 then p := a/2; else p := (a + m)/2;
end if;
end loop;
if p >= m then z := p-m; else z := p; end if;

Example 3.5 Same example as before, that is, m = 239, R = 2 = 256,
8
compute MP(202, 236).