Cryptography Reference
In-Depth Information
Input
:
a
and
n
, two integers of at most
bits, an integer
e
Output
:
x
=
a
e
mod
n
Complexity
:
O
(
2
log
e
)
1:
x
←
1
2:
for
i
=
−
1 downto 0
do
x
←
x
×
x
mod
n
3:
if
e
i
=
1
then
4:
x
←
x
×
a
mod
n
5:
6:
end if
7:
end for
Figure 6.6.
Exponentiation from left to right (Square-and-Multiply).
To prove the first property, we first observe that
Z
m
×
Z
n
is a product ring with unit
element (1
,
1). The
f
function then fulfills
f
(
xy
mod
mn
)
=
f
(
x
)
f
(
y
)
and
f
(1)
=
(1
,
1), which are the ring morphism properties. Finally,
f
(
x
)
=
(0
,
0) im-
plies
x
mod
m
0, which means that
x
is a multiple of
m
and
n
simultaneously. Since
m
and
n
have no common prime factor, this means that
x
is a mul-
tiple of
mn
, so that
x
mod
mn
=
0 and
x
mod
n
=
=
0. Thus the preimage of zero by
f
in
Z
mn
is
{
0
}
, which
means that
f
is injective. Now since the cardinalities of
Z
mn
and
Z
m
×
Z
n
are equal,
f
must be a bijection, hence a ring isomorphism. For the second property, we can see that
invertible elements of
Z
m
×
Z
n
are elements of
Z
m
×
Z
n
, so there are
ϕ
(
m
)
ϕ
(
n
) many.
We h av e
ϕ
(
mn
) invertible elements in
Z
mn
. Since
Z
mn
and
Z
m
×
Z
n
are isomorphic
rings, the number of invertible elements must be the same, hence
(
n
).
Finally, we check the last property by computing the
f
of the right-hand term. We first
reduce it modulo
m
. We know that for any
x
,(
x
mod
mn
) mod
m
ϕ
(
mn
)
= ϕ
(
m
)
ϕ
x
mod
m
, thus
we can remove the final reduction modulo
mn
. Next, the modulo
m
reduction cancels
the second term of the sum
bm
(
m
−
1
mod
n
) which is a factor of
m
. The remainder is
an
(
n
−
1
mod
m
) mod
m
which is
a
. The modulo
n
reduction similarly outputs
b
. Hence
the right-hand term of the last property is actually the preimage of (
a
=
,
b
).
As an example in
Z
35
, we can let
m
=
5 and
n
=
7. If we want to solve
x
mod 5
=
3
and
x
mod 7
=
4 simultaneously, we compute
=
3
mod 7)
mod 35
f
−
1
(3
(7
−
1
(5
−
1
,
4)
×
7
×
mod 5)
+
4
×
5
×
.
The Extended Euclid Algorithm gives us the following Bezout relationship.
=
−
×
+
×
.
1
(
2)
7
3
5
Thus 5
−
1
3 and 7
−
1
2 which gives us 7
−
1
mod 7
=
mod 5
≡−
mod 5
=
3. Hence
f
−
1
(3
,
4)
=
(3
×
7
×
3
+
4
×
5
×
3) mod 35
=
123 mod 35
=
18
.
Search WWH ::
Custom Search