Cryptography Reference
In-Depth Information
(a)
Figure 3.4
(b)
(c)
There is a test applet for computing greatest common divisors on the topic's website
under the class name TestGCDApplet. It uses the gcd() method supplied with the BigInte-
ger class. Figure 3.5 shows a screen shot of a sample run.
The following development will be very useful to us later on, for it will help us solve spe-
cial equations called diophantine equations, and congruences. It also reveals something
interesting about the gcd. Recall that the gcd of two numbers is the least positive integer that
can be expressed as a linear combination of those two numbers; that is,
x
y
mx
ny
(
,
) =
+
for some integers
m
and
n
. What are the values of
m
and
n
? The next proposition shows us
exactly how these two quantities can be computed.
PROPOSITION 12
(Extended Euclidean Algorithm). Let
x
and
y
be positive integers such
that
x
≥
y
> 0. Then
(
x
,
y
) =
s
n
x
+
t
n
y
Search WWH ::
Custom Search