Cryptography Reference
In-Depth Information
becomes a prime number for
p
11. This problem can be solved.
If
e
is relatively prime to (
p
−
1)(
q
−
1) (a number bigger than 1 can always
be found), then there is a modular reciprocal,
d
of
e
, i.e., a
d
with
=
5 and
q
=
de = 1 mod (p-1)(q-1)
(This
d
is calculated by the so-called extended Euclidean algorithm.) This
translates to
de = k(p-1)(q-1) + 1
for any natural number,
k>
1, because
m
k
(
p
−
1
)(
q
−
1
)
=1
k
= 1 mod pq
follows from (2), and we will then still have
m
de
= m mod pq
(3)
Problem 2
: What happens with those
m<n
that are not relatively prime to
n
=
pq
? A small calculation shows that the equation (3) we are interested in
will nevertheless hold. Proving it is not difficult, so I will demonstrate it.
We know that
t
p
−
1
q
p
−
1
= 1 mod p
and
= 1 mod p
holds for each
t<p
according to Fermat's little theorem, so it also holds for
each
k>
0:
t
k
(
p
−
1
)(
q
−
1
)
q
k
(
p
−
1
)(
q
−
1
)
= 1 mod p
and
= 1 mod p.
