Cryptography Reference
In-Depth Information
as in (10.6) and (10.7). We have the
distributive law
for gcd and lcm, namely,
gcd(
a,
lcm(
b, c
)) = lcm(gcd(
a, b
)
,
gcd(
a, c
))
,
(10.8)
lcm(
a,
gcd(
b, c
)) = gcd(lcm(
a, b
)
,
lcm(
a, c
))
,
(10.9)
and to top it all off we have (see [Schr], Section 2.4)
gcd(lcm(
a, b
)
,
lcm(
a, c
)
,
lcm(
b, c
)) = lcm(gcd(
a, b
)
,
gcd(
a, c
)
,
gcd(
b, c
))
.
(10.10)
Aside from the obvious beauty of these formulas on account of their fearful
symmetry, they also serve to provide excellent tests for functions that deal with
greatest common divisor and least common multiple, where the arithmetic
functions used are implicitly tested as well (on the subject of testing, see
Chapter 12).
Don't blame testers for finding your bugs.
—Steve Maguire
10.2 Multiplicative Inverse in Residue Class Rings
In contrast to the arithmetic of whole numbers, in residue class rings it is possible,
under certain assumptions, to calculate with multiplicative inverses. Namely,
many elements
a ∈
Z
n
, not necessarily all, possess a suitable
x ∈
Z
n
such that
a · x
= 1
. This is equivalent to the assertion that the congruence
a · x ≡
1mod
n
and the statement
a · x
mod
n
=1
hold. For example, in
Z
14
,
3
and
5
are
multiplicative inverses of each other, since
15mod14=1
.
The existence of multiplicative inverses in
Z
n
is not obvious. In Chapter
5, on page 69, it was determined only that
(
Z
n
, ·
)
is a finite commutative
semigroup with unit
1
. A sufficient condition for an element
a
∈
Z
n
to possess a
multiplicative inverse can be obtained with the help of the Euclidean algorithm:
The second-to-last equation in the Euclidean algorithm procedure on page 169,
a
m
−
2
=
a
m
−
1
· q
m
−
2
+
a
m
,
0
≤ a
m
<a
m
−
1
,
can be transformed into
a
m
=
a
m
−
2
− a
m
−
1
· q
m
−
2
.
(1)
If we continue in this fashion, then we obtain in succession
a
m
−
1
=
a
m
−
3
−
a
m
−
2
·
q
m
−
3
,
(2)
a
m
−
2
=
a
m
−
4
− a
m
−
3
· q
m
−
4
,
(3)
.
a
3
=
a
1
−
a
2
·
q
1
.
(
m
−
2)
