Cryptography Reference
In-Depth Information
Z
n
,
Z
n
.If
n
is prime,
·
is a commutative group that is frequently written as
Z
n
, and hence
then
Z
n
\{
0
}
=
Z
n
\{
0
}
,
·
is a group. Furthermore, the order of
Z
n
(i.e.,
|
Z
n
|
) is equal to
φ
(
n
). This means that it can be computed using Euler's
totient function (see Section 3.2.6).
3.3.2
Modular Exponentiation
A frequently used computation in cryptography is modular exponentiation. If, for
example, we want to compute
a
b
(mod
n
)
for
a
, then the simplest algorithm is to iteratively multiply
a
modulo
nb
times. If
b
=23, then the following sequence of equations yields the
correct result with 22 modular multiplications:
∈
Z
n
and
b
∈
N
R
n
(
a
2
)=
R
n
(
a
·
a
)
R
n
(
a
3
)=
R
n
(
a
R
n
(
a
2
))
·
R
n
(
a
4
)=
R
n
(
a
R
n
(
a
3
))
·
...
R
n
(
a
23
)=
R
n
(
a
R
n
(
a
22
))
·
This can be simplified considerably, and the following sequence of equations
yields the correct result but requires only 7 modular multiplications:
R
n
(
a
2
)=
R
n
(
a
a
)
R
n
(
a
4
)=
R
n
(
R
n
(
a
2
)
·
R
n
(
a
2
))
·
R
n
(
a
4
))
R
n
(
a
10
)=
R
n
(
R
n
(
a
5
)
R
n
(
a
5
)=
R
n
(
a
·
R
n
(
a
5
))
·
R
n
(
a
11
)=
R
n
(
a
R
n
(
a
10
))
R
n
(
a
22
)=
R
n
(
R
n
(
a
11
)
·
R
n
(
a
11
))
·
R
n
(
a
23
)=
R
n
(
a
R
n
(
a
22
))
·