Page 93 - Hardware Implementation of Finite-Field Arithmetic

76 Cha pte r T h ree

− 1
The inverse application T is defined as follows:
T (y) = yR mod m (3.13)
− 1
− 1
Thus, T is a one-to-one and onto application.
Property 3.1 Given x and y in Z , then T((x + y) mod m) = (T(x) + T(y))
m
mod m and T((x − y) mod m) = (T(x) − T(y)) mod m.
Proof T((x ± y) mod m) = (x ± y)R mod m = ((xR mod m) ± (yR mod m))
mod m = (T(x) ± T(y)) mod m.

As regards the multiplication, observe that

−1
T(xy mod m) = xyR mod m = ((xR mod m)(yR mod m))R
− 1
mod m = T(x)T(y)R mod m (3.14)
The latter suggests the definition of a new operation on Z , the
m
so-called Montgomery product MP [Mon85]:
MP(x, y) = xyR mod m (3.15)
− 1
A straightforward consequence of Eqs. (3.14) and (3.15) is the
following property:

Property 3.2 Given x and y in Z , then
m
T(xy mod m) = MP(T(x)T(y)) (3.16)
Assume now that the value of

R = RR mod m (3.17)
2
has been previously computed. Then, given x and y in Z ,
m
2
− 1
2
T(x) = xR mod m = xR R = MP(x,R ) (3.18)
− 1
− 1
T (y) = yR mod m = MP(y,1) (3.19)
Assuming that an efficient algorithm exists for computing the
Montgomery product MP, any set of operations on Z , including
m
sums, subtractions, and multiplications, can be performed in the
following way:
2
Substitute all the operands, say x , x , . . . , by T(x ) = MP(x , R ),
1 2 1 1
T(x ) = MP(x , R ), . . .
2
2 2
Execute all the operations substituting the products by Montgomery
products
Substitute all the results, say y , y , . . . , by T (y ) = MP(y ,1),
− 1
1 2 1 1
T − 1 (y ) = MP(y ,1), . . .
2 2