Cryptography Reference
In-Depth Information
If in (1) we replace
a
m
−
1
by the right side of equation (2), then we obtain
a
m
=
a
m
−
2
−
q
m
−
2
(
a
m
−
3
−
q
m
−
3
·
a
m
−
2
)
,
or
a
m
=(1+
q
m
−
3
· q
m
−
2
)
a
m
−
2
− q
m
−
2
· a
m
−
3
.
Proceeding thus one obtains in equation
(
m −
2)
an expression for
a
m
as a
linear combination of the starting values
a
1
and
a
2
with factors composed of the
quotients
q
i
of the Euclidean algorithm.
In this way we obtain a representation of
gcd(
a, b
) =
u
b
=:
g
as
a linear combination of
a
and
b
with integer factors
u
and
v
, where
u
modulo
a/g
and
v
modulo
b/g
are uniquely determined. If for an element
¯
a ∈
Z
n
we
now have
gcd(
a, n
) = 1 =
u · a
+
v · n
, then it follows immediately that
1
≡ u · a
mod
n
, or, equivalently,
¯
a ·
¯
u
=
¯
1
. In this case
u
modulo
n
is uniquely
determined, and
¯
u
is consequently the inverse of
¯
a
in
·
a
+
v
·
Z
n
. We have thus found a
condition for the existence of a multiplicative inverse of an element in the residue
class ring
Z
n
, and we have simultaneously obtained a procedure for constructing
such an inverse, which shall demonstrate with the following example. From the
calculation above of
gcd(723
,
288)
we obtain by rearrangement
3 = 141
−
6
·
23
,
6 = 147
−
141
·
1
,
141 = 288
−
147
·
1
,
147 = 723
−
288
·
2
.
From this we obtain our representation of the greatest common divisor:
3 = 141
147
=24
·
(288
−
147)
−
23
·
147 =
−
47
·
147 + 24
·
288
=
−
47
·
(723
−
2
·
288) + 24
·
288 =
−
47
·
723 + 118
·
288
.
−
23
·
(147
−
141) = 24
·
141
−
23
·
A fast procedure for calculating this representation of the greatest common
divisor would consist in storing the quotients
q
i
(as is done here on the page)
so that they would be available for the backward calculation of the desired
factors. Because of the high memory requirement, such a procedure would
not be practicable. It is necessary to find a compromise between memory
requirements and computational time, which is a typical tradeoff in the design
and implementation of algorithms. To obtain a realistic procedure we shall
further alter the Euclidean algorithm in such a way that the representation of the
greatest common divisor as a linear combination can be calculated along with
the greatest common divisor itself. For
¯
a
in
Z
n
there exists an inverse
¯
x ∈
Z
n
if
gcd(
a, n
)=1
. The converse of this statement can also be demonstrated: If
¯
a
in
Z
n
has a multiplicative inverse, then
gcd(
a, n
)=1
(one may find a mathematical
proof of this statement in [Nive], the proof to Theorem 2.13). We see, then, that
