Cryptology 401the greatest common divisor (GCD) of two numbers. The larger of the two
numbers is divided by the smaller number, paying attention only to the
remainder. Then, the smaller number is divided by the remainder, and
the process is repeated until the remainder is zero. The last value for the
remainder before it reaches zero is the greatest common divisor of the two
original numbers. This algorithm is quite fast, with a run time of O(log 10 N).
That means that it should take about as many steps to find the answer as
the number of digits in the larger number.
In the table below, the GCD of 7253 and 120, written as gcd(7253, 120),
will be calculated. The table starts by putting the two numbers in the columns
A and B, with the larger number in column A. Then A is divided by B, and
the remainder is put in column R. On the next line, the old B becomes the
new A, and the old R becomes the new B. R is calculated again, and this
process is repeated until the remainder is zero. The last value of R before
zero is the greatest common divisor.
So, the greatest common divisor of 7243 and 120 is 1. That means that
7250 and 120 are relatively prime to each other.
The extended Euclidean algorithm deals with finding two integers, J and K,
such that
J ·A +K ·B =R
when gcd(A, B) = R.
This is done by working the Euclidean algorithm backward. In this case,
though, the quotients are important. Here is the math from the prior
example, with the quotients:
7253 = 60 · 120 + 53
120 = 2 · 53 + 14
53 = 3 · 14 + 11
14 = 1 · 11 + 3
11 = 3 · 3 + 2
3 =1·2+ 1
gcd(7253, 120)