Page 220 - Hardware Implementation of Finite-Field Arithmetic

200 Cha pte r Se v e n

ˆ
1. b = 1 . r
2. ˆ a= a . r
3. for i = 0 to m – 1 do
b ×
ˆ
:
4. if e = 1 then b = ˆ ˆ a
i
ˆ
ˆ := b × ˆ
5. b b
b := ˆ
b × 1
6.
The difference of Algorithm 7.17 from the binary method using
standard multiplication and squaring is that in steps 4 and 5,
Montgomery multiplication and squaring are performed, respectively.
When a Montgomery operation is performed, the multiplicative
⋅
⋅
factor r remains in place, that is, ˆ c c× = (cr⋅⋅⋅⋅ −1 = (cc r and
ˆ
)
) (cr r
)
⋅
⋅
ˆ ca× = (c r⋅⋅ ⋅⋅ −1 = (c a r . This multiplicative factor r is removed
ˆ
)
)
) (a r r
ˆ
from ˆ in step 6, because b ×= (b r 1 r −1 = b , therefore obtaining
)⋅ ⋅
⋅
1
b
e
the final result b = a .
Montgomery exponentiation method given above can be implemented
in the following algorithm:
Algorithm 7.18—Bit-level montgomery exponentiation
for i in 0 .. m-1 loop b(i) := 0; one(i) := 0; end loop;
one(0) := 1;
c := LSBfirst(f,f,f);
c := bmult_montgomery(a,c,f);
b:= f;
for i in 0 .. m-1 loop
if e(i) = 1 then b := bmult_montgomery(b,c,f); end if;
c := bsquarer_montgomery(c,f);
end loop;
b := bmult_montgomery(b,one,f);
where the Montgomery multiplication and squaring operations are
computed with the functions bmult_montgomery and bsquarer_
montgomery given in Algorithms 7.8 and 7.11, respectively, and where
the standard multiplication modulo f(x) has been computed with the
function LSBfirst given in Algorithm 7.3. Step 1 in Algorithm 7.17 is
implemented in Algorithm 7.18 with the assignment b := f because
m
the fixed element r(x) was chosen to be r(x) = x . Therefore r is the
element of the finite field represented by the polynomial r(x) mod
m
f(x). If f(x) = x + f x m − 1 + . . . + f x + f ⇒ x = f x m − 1 + . . . + f x + f ,
m
m − 1 1 0 m − 1 1 0
that is, r = (f , f , . . . , f , f ), where f s are the coefficients of the
m − 1 m − 2 1 0 i
irreducible polyno-mial f(x). In a similar way, step 2 (Algorithm 7.17)
is implemented with c := LSBfirst(a,f,f) in Algorithm 7.18. The result
of the exponentiation is finally loaded at the bit vector b. An
executable Ada file Exp_montgomery.adb, including Algorithm 7.18,
is available at www.arithmetic-circuits.org.