Page 94 - Hardware Implementation of Finite-Field Arithmetic

mod m Operations 77

3.4.3.2 Montgomery Product
First define the Montgomery reduction MR ([Mon85]): given a natural
number x, then
− 1
MR(x) = xR mod m (3.20)
As gcd(m, R) = 1, there exists an element − m − 1 of Z such that
R
m(−m ) mod R = −1. Assuming that the value minus_inv_m of −m
− 1
− 1
has been previously computed, and that x < mR, the following
algorithm computes MR(x):
Algorithm 3.9—Montgomery reduction
q := (x + ((x*minus_inv_m) mod r)*m) / r;
if q >= m then z := q-m; else z := q; end if;
The correctness of Algorithm 3.9 is deduced from the following
facts:
x + (x( −m ) mod R)m ≡ 0 mod R , so that
− 1
− 1
x + (x( −m ) mod R)m = qR
x + (x( −m ) mod R)m < 2mR, so that q < 2m
− 1
q mod m = qRR mod m = (x + (x(−m ) mod R)m)R
− 1
− 1
− 1
mod m = xR mod m = MR(x)
− 1
Example 3.3 Assume that m = 239, R = 256, and compute MR(47672).
− 1
− 1
First check that R mod m = 225 and −m mod R = 241. Then
compute
47672 + (((47672 × 241) mod 256) × 239) = 47672 + (184 × 239) = 91648
91648/256 = 358
358 – 239 = 119

and check that 47672 × 225 = (44879) × 239 + 119.

Given x and y in Z , their product p = xy is smaller than mm < mR,
m
so that their Montgomery product [Eq. (3.15)] can be computed as
follows:
MP(x, y) = MR(xy) (3.21)

The corresponding algorithm is the following ([Mon85]):

Algorithm 3.10—Montgomery product
product := x*y;
q := (product + ((product*minus_inv_m) mod r)*m) / r;
if q >= m then z := q-m; else z := q; end if;