Cryptography Reference
In-Depth Information
in
x
. If gcd(
e
,
ϕ
(
n
))
=
1, we know that
e
is invertible in
Z
ϕ
(
n
)
, so we can compute
e
−
1
(
n
). Now we can raise the equation to the power
d
and get
x
ed
y
d
d
=
mod
ϕ
≡
(
n
)),
x
ed
mod
n
can be written
x
1
+
k
ϕ
(
n
)
(mod
n
). But since
ed
≡
1 (mod
ϕ
mod
n
y
e
−
1
mod
ϕ
(
n
)
mod
n
. Conversely, we check that this
x
is
a solution of the equation by raising it, modulo
n
, to the power
e
.
which is equal to
x
. Thus
x
≡
6.2.5 Exponentiation
We notice that a modular exponentiation
x
e
mod
n
does not necessarily require to per-
form
e
multiplications. We have much more efficient algorithms. Note that
x
e
mod
n
can be defined by
x
x
(
e
times) where the multiplications are performed
modulo
n
, so we can adapt the multiplication algorithm of Figs. 6.2 and 6.3 to the expo-
nentiation in
Z
n
by replacing the regular addition by a multiplication modulo
n
. Fig. 6.5
is an algorithm which computes the exponentiation “from right to left” because it reads
all exponent bits in this direction. Conversely, Fig. 6.6 computes the exponentiation
“from left to right.” Both algorithms require
O
(log
e
) modular multiplications, thus a
complexity of
O
(
×
x
×···×
2
log
e
). We have many possible improvements of these algorithms.
For instance we can read the exponent from left to right in basis
B
instead of a binary
basis. We then need to precompute all
a
j
mod
n
for
j
=
0
,...,
B
−
1 prior to the loop.
6.2.6 Z
mn
: The Chinese Remainder Theorem
Exponentiation in
Z
mn
can also be accelerated by using the following theorem.
Theorem 6.4 (Chinese Remainder Theorem).
Let m and n be two integers such that
gcd(
m
,
=
n
)
1
. We have
1.
f
:
Z
mn
→
Z
m
×
Z
n
defined by f
(
x
)
=
(
x
mod
m
,
x
mod
n
)
is a ring isomor-
phism
2.
ϕ
(
mn
)
= ϕ
(
m
)
ϕ
(
n
)
f
−
1
(
a
an
(
n
−
1
bm
(
m
−
1
3.
,
b
)
≡
mod
m
)
+
mod
n
) (mod
mn
)
Input
:
a
and
n
, two integers of at most
bits, an integer
e
a
e
Output
:
x
=
mod
n
O
2
log
e
)
Complexity
:
(
←
1:
x
1
2:
y
←
a
3:
for
i
=
0to
−
1
do
if
e
i
=
1
then
4:
x
←
x
×
y
mod
n
5:
end if
6:
y
←
y
×
y
mod
n
7:
8:
end for
Figure 6.5.
Exponentiation from right to left (Square-and-Multiply).
Search WWH ::
Custom Search