Cryptography Reference
In-Depth Information
exponentiation (cf. page 100). In the following steps we shall calculate the power
1234
667
mod 18577
:
1.
Precomputations
The exponent
e
= 667
is represented to the base
2
k
with
k
=2
(cf. the
algorithm for Montgomery exponentiation on page 114). The exponent
e
thereby has the representation
e
= (10 10 01 10 11)
2
2
.
The value
r
for Montgomery reduction is
r
=2
16
=
B
= 65536
.
The value
n
0
(cf. page 110) is now calculated as
n
0
= 34703
.
The transformation of the base
a
into the residue system
R
(
r, n
)
(cf.
page 107) follows from
65536 mod 18577 = 5743
.
The power
a
3
in
R
(
r, n
)
has the value
a
3
= 9227
. Because of the small
exponent, further powers of
a
do not arise in the precomputation.
a
=
ar
mod
n
= 1234
·
2.
Exponentiation loop
exponent digit
e
i
=2
t
u
2
1
1
0
1
0
·
1
·
1
·
1
·
1
·
3
p ← p
2
-
16994
3682
14511
11066
p
2
2
p
←
-
-
6646
-
12834
a
u
p
←
p
×
5743
15740
8707
16923
1583
p ← p
2
9025
11105
-
1628
-
3.
Result
The value of the power
p
after normalization:
p
=
p ×
1=
pr
−
1
mod
n
= 1583
r
−
1
mod
n
= 4445
.
Those interested in reconstructing the coding details of the functions
mexp5m_l()
and
mexpkm_l()
and the calculational steps of the example related to
the function
mexpkm_l()
are referred to the FLINT/C source code.
At the start of this chapter we developed the function
wmexp_l()
, which has
the advantage for small bases that only multiplications
p
pa
mod
m
of the
type
CLINT * USHORT
mod
CLINT
occur. In order to profit from the Montgomery
procedure in this function, too, we adjust the modular squaring to Montgomery
squaring, as in
mexpkm_l()
, with the use of the fast inverse function
invmon_l()
,
though we leave the multiplication unchanged. We can do this because with the
calculational steps for Montgomery squaring and for conventional multiplication
modulo
n
,
←
a
2
r
−
1
b ≡
a
2
b
r
−
1
mod
n,
