Cryptography Reference
In-Depth Information
Figure 3.5
where the
s
n
and
t
n
are defined recursively as
s
j
=
s
j
2
q
j
1
s
j
1
for
j
= 2, . . . ,
n
s
0
= 1
s
1
= 0
t
j
=
t
j
2
q
j
1
t
j
1
for
j
= 2, . . . ,
n
t
0
= 0
t
1
= 1
and the
r
i
are as in the Euclidean algorithm.
Rather than produce a proof right away for this, we do an example to clarify what is
going on. Suppose we wish to express the gcd of 252 and 198 as a linear combination of 252
and 198. We can apply the Euclidean algorithm, and while keeping track of the quotients
and remainders, we shall also compute the two values
q
j
and
s
j
and
t
j
during the
j
th step. This is
perhaps best done in a table. (See Table 3.3.)
The fourth remainder is the last nonzero remainder, so we need not compute the fifth
row in the table. The two numbers desired are 4, and
5; that is,
5) · 198
Now, we can show a proof to you that this always works.
18 = (252, 198) = 4 · 252 + (
Proof.
First note that (
x
,
y
) =
r
n
, where
r
n
is the last nonzero remainder generated in the
Euclidean algorithm. If we show then that
r
j
=
s
j
x
+
t
j
y
(*)
(for all)
j
= 0, 1, . . . ,
k
<
n
, the result then follows by induction. First, note (*) is true
when
j
= 0, and when
j
= 1, since
r
0
= 1 ·
x
+ 0 ·
y
=
s
0
x
+
t
0
y
, and
r
1
= 0 ·
x
+ 1 ·
y
=
s
1
x
+
t
1
y.
Search WWH ::
Custom Search